Erstellung von Linienfahrplänen in Hub-and-Spoke-Netzwerken (timetabling in hub-and-spoke networks)
\(\large (\text{TTP})~~\left\{~~ \begin{align*} & \text{Min.} && \sum_{i\in V}\sum_{l\in L_i}c_lz_i^l+\varepsilon\cdot\sum_{t=1,\ldots,T}\sum_{(i,j)\in A}\sum_{l\in L_{ij}}y_{ij}^{lt} \\ & \text{u. d. N.} && \sum_{t'=1}^t\sum_{(h, i)\in A_{hk}}\sum_{l\in L_{hi}}x^{hklt'}_{hi}\le \sum_{t'=1}^t b_h^{kt'} && (h, k\in D;~t=1, \ldots, T)\\ & && \sum_{t'=1}^t\sum_{(j, k)\in A_{hk}}\sum_{l\in L_{jk}}x^{hkl(t'-p^l_{jk})}_{jk}\ge \sum_{t'=1}^t \hat{b}_h^{kt'} && (h, k\in D;~t=1, \ldots, T)\\ & && \sum_{t'=1}^t\sum_{(j, i)\in A_{hk}}\sum_{l\in L_{ji}}x^{hkl(t'-p^l_{ji}-q_i^l)}_{ji} \ge \sum_{t'=1}^t\sum_{(i, j)\in A_{hk}}\sum_{l\in L_{ij}} x^{hklt'}_{ij} && (i\in H;~h, k\in D;~t=1, \ldots, T)\\ & && \sum_{h, k\in D: (i, j)\in A_{hk}}x^{hklt}_{ij} \le v_l\cdot y_{ij}^{lt} && ((i, j)\in A;~l\in L_{ij};~t=1, \ldots, T) \\ & && \sum_{t=1}^T\sum_{(i, j)\in A_l} y_{ij}^{lt} = \sum_{t=1}^T\sum_{(j, i)\in A_l} y_{ji}^{l(t-p_{ji}^l-q_i^l)} && (i\in V;~l\in L) \\ & && \sum_{l\in L_i}r_{il}\sum_{(j, i)\in A_l}\sum_{t'=0}^{q_i^l-1}y_{ji}^{l(t-p^l_{ji}-t')}\le u^t_i && (i\in H;~t=1, \ldots, T)\\ & && z_i^l\ge \sum_{t'=1}^t\sum_{(i,j)\in A_l} y_{ij}^{lt'}-\sum_{t'=1}^t\sum_{(j,i)\in A_l} y_{ji}^{l(t'-p^l_{ji}-q_i^l)} && (i\in V;~l\in L_i;~t=1, \ldots, T)\\ & && x^{hklt}_{ij}\ge 0 && (h, k\in D;~(i, j)\in A_{hk};~l\in L_{ij};~t=1, \ldots, T) \\ & && y^{lt}_{ij}\in\mathbb{Z}_{\ge 0} && ((i, j)\in A;~l\in L_{ij};~t=1, \ldots, T) \end{align*}\right. \) |
\(\varepsilon\) | Kleine positive Konstante | |
\(A\) | Menge der Relationen \((i, j)\) im Hub-and-Spoke-Netzwerk | |
\(A_{hk}\) | Menge der Relationen \((i, j)\) auf Wegen von Depot \(h\) zu Depot \(k\) | |
\(A_l\) | Menge der Relationen \((i, j)\), auf denen Fahrzeuge vom Typ \(l\) eingesetzt werden | |
\(b^{kt}_h\) | Im Depot \(h\) in Periode \(t\) durchschnittlich zum Versand an Depot \(k\) bereitgestellte Menge | |
\(\hat{b}^{kt}_h\) | Von Depot \(k\) aus in Periode \(t\) durchschnittlich an Empfänger verteilte Menge aus Depot \(h\) | |
\(c_l\) | Kosten für den Einsatz eines Fahrzeugs vom Typ \(l\) pro Zyklus | |
\(D\subset V\) | Menge der Depots \(h, k\) | |
\(H\subset V\) | Menge der Hubs \(i, j\) | |
\(L_i\) | In Knoten \(i\) eingesetzte Fahrzeugtypen | |
\(L_{ij}\) | Fahrzeugtypen auf Relation \((i, j)\) | |
\(p^l_{ij}\) | Fahrzeit in Perioden von Knoten \(i\) zu Knoten \(j\) mit Fahrzeugtyp \(l\) | |
\(q^l_i\) | Umschlagsdauer in Perioden der Ladung von Fahrzeugtyp \(l\) | |
\(r^l_i\) | Kapazitätsbedarf pro Periode für Umschlag der Ladung von Fahrzeugtyp \(l\) in Hub \(i\) | |
\(T\) | Anzahl der Perioden \(t\) | |
\(u^t_i\) | Umschlagskapazität von Hub \(i\) in Periode \(t\) | |
\(V\) | Menge der Knoten \(i\) des Hub-and-Spoke-Netzwerks | |
\(v_l\) | Ladekapazität von Fahrzeugtyp \(l\) | |
\(\ast\) | \(x^{hklt}_{ij}\ge 0\) | Zu Beginn von Periode \(t\) mit Fahrzeugen des Typs \(l\) von Knoten \(i\) zu Knoten \(j\) versandte Menge aus Depot \(h\) für Depot \(k\) |
\(\ast\) | \(y^{lt}_{ij}\in\mathbb{Z}_{\ge 0}\) | Anzahl der Fahrzeuge des Typs \(l\), die zu Beginn von Periode \(t\) von Knoten \(i\) aus zu Knoten \(j\) starten |
\(\ast\) | \(z_i^l\ge 0\) | Anzahl der Fahrzeuge des Typs \(l\), die in Knoten \(i\) benötigt werden |