取送貨問題及其變體

廣義取送貨問題（General Pickup and Delivery Problems，GPDP）可以分為兩類：

• Vehicle Routing Problems with
  Backhauls，VRPB：從配送中心（depot）取貨運輸貨物到客戶點，再從客戶點取貨運輸至配送中心交付（backhoul）。

  transportation of goods from the depot to linehaul customers and from backhaul customers to the depot

• Vehicle Routing Problems with Pickups and Deliveries
  ，VRPPD：貨物在取貨點和送貨點之間流轉。按照取貨點和交貨點是否是成對的，可以進一步分為兩類：

  • unpaired：對于貨物，從某一取貨點取貨，可以交付至任意送貨點。如果只有一輛車，那么問題簡化為Pickup and Delivery Traveling Salesman Problem，PDTSP。如果是多輛車，Pickup and Delivery Vehicle Routing Problem，PDVRP。
  • paired：對于某一訂單，從某一指定取貨點取貨，只能交付至指定的送貨點。如果研究的對象是貨物，則有Single Pickup and Deleivery Problem，SPDP（一輛車）和PDP兩個問題。如果研究的對象是乘客，則有e Dial-A-Ride Problem，DARP問題，對于一輛車的情況為the single vehicle case of the DARP as SDARP.

本文研究的取送貨問題為PDP，如圖：

接下來，本文所說的取送貨問題，均為同車型，多輛車的Pickup and Delivery Problem，Homogeneous Multi vehicle pickup and delivery problem用PDP表示。

Parragh S N, Doerner K F, Hartl R F. A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations[J/OL]. Journal für Betriebswirtschaft, 2008, 58(2): 81-117. https://doi.org/10.1007/s11301-008-0036-4.

取送貨問題數學模型（Homogeneous Multi vehicle pickup and delivery problem formulations）

參數

• $n$：取貨點數量。
• $\tilde{n}$：送貨點數量，因為這里是Paired PDP問題，故$n=\tilde{n}$。
• $P$：取貨點集合， P = { 1 , . . . , n } P = \{1,..., n\} P={1,...,n}
• $D$：送貨點集合， D = { n + 1 , . . . , n + n ~ } D = \{n +1,..., n +\tilde{n}\} D={n+1,...,n+n~}
• $K$：車輛集合

決策變量

• $x_{ijk}$：車輛路徑決策變量，$x_{ijk}=1$，車輛$k$經過弧$(i,j)$；
• $Q_i^k$：車輛$k$離開節點$i$時的裝載量；
• $B_i^k$：車輛$k$服務$i$點的開始時刻；

混合整數規劃模型
min ? ∑ k ∈ K ∑ ( i , j ) ∈ A c i j k x i j k subject?to. ∑ k ∈ K ∑ j : ( i , j ) ∈ A x i j k = 1 ? i ∈ P ∪ D , ∑ j : ( 0 , j ) ∈ A x 0 j k = 1 ? k ∈ K , ∑ i : ( i , n + n ~ + 1 ) ∈ A x i , n + n ~ + 1 k = 1 ? k ∈ K , ∑ i : ( i , j ) ∈ A x i j k ? ∑ i : ( j , i ) ∈ A x j i k = 0 ? j ∈ P ∪ D , k ∈ K , x i j k = 1 ? B j k ≥ B i k + d i + t i j k ? ( i , j ) ∈ A , k ∈ K , x i j k = 1 ? Q j k = Q i k + q j ? ( i , j ) ∈ A , k ∈ K , max ? { 0 , q i } ≤ Q i k ≤ min ? { C k , C k + q i } ? i ∈ V , k ∈ K , e i ≤ B i k ≤ l i ? i ∈ V , k ∈ K , B n + n ~ + 1 k ? B 0 k ≤ T k ? k ∈ K , x i j k ∈ { 0 , 1 } ? ( i , j ) ∈ A , k ∈ K . \begin{align} \min \quad & \sum_{k\in K}\sum_{(i,j) \in A} c_{ij}^k x_{ij}^k \\ \text{subject to.} \quad &\sum_{k \in K} \sum_{j:(i, j) \in A} x_{i j}^{k} =1 & \forall i \in P \cup D, \\ &\sum_{j:(0, j) \in A} x_{0 j}^{k}=1 & \forall k \in K, \\ &\sum_{i:(i, n+\tilde{n}+1) \in A} x_{i, n+\tilde{n}+1}^{k} =1 & \forall k \in K, \\ &\sum_{i:(i, j) \in A} x_{i j}^{k}-\sum_{i:(j, i) \in A} x_{j i}^{k} =0 &\forall j \in P \cup D, k \in K, \\ &x_{i j}^{k}=1 \Rightarrow B_{j}^{k} \geq B_{i}^{k}+d_{i}+t_{i j}^{k} & \forall(i, j) \in A, k \in K, \\ &x_{i j}^{k}=1 \Rightarrow Q_{j}^{k} =Q_{i}^{k}+q_{j} & \forall(i, j) \in A, k \in K, \\ &\max \left\{0, q_{i}\right\} \leq Q_{i}^{k} \leq \min \left\{C^{k}, C^{k}+q_{i}\right\} & \forall i \in V, k \in K, \\ & e_i \leq B_i^k \leq l_i & \forall i \in V, k \in K,\\ & B_{n+\tilde{n}+1}^k -B_{0}^k \leq T^k &\forall k \in K,\\ &x_{i j}^{k} \in\{0,1\} & \forall(i, j) \in A, k \in K . \end{align} minsubject?to.?k∈K∑?(i,j)∈A∑?cijk?xijk?k∈K∑?j:(i,j)∈A∑?xijk?=1j:(0,j)∈A∑?x0jk?=1i:(i,n+n~+1)∈A∑?xi,n+n~+1k?=1i:(i,j)∈A∑?xijk??i:(j,i)∈A∑?xjik?=0xijk?=1?Bjk?≥Bik?+di?+tijk?xijk?=1?Qjk?=Qik?+qj?max{0,qi?}≤Qik?≤min{Ck,Ck+qi?}ei?≤Bik?≤li?Bn+n~+1k??B0k?≤Tkxijk?∈{0,1}??i∈P∪D,?k∈K,?k∈K,?j∈P∪D,k∈K,?(i,j)∈A,k∈K,?(i,j)∈A,k∈K,?i∈V,k∈K,?i∈V,k∈K,?k∈K,?(i,j)∈A,k∈K.??

• 目標函數（1）最小化總體行駛成本；
• 約束（2）保證了每個客戶點都被訪問了一次；
• 約束（3-5）分別保證了每輛車必須從始發站出發，到達并離開每個客戶點，并最終回到終點站；
• 約束（6）消除子回路，
• 約束（7-8）車輛容量約束

【注】約束（6）和（7）是非線性的，可以用大M進行線性化

參考：
Parragh S N, Doerner K F, Hartl R F. A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations[J/OL]. Journal für Betriebswirtschaft, 2008, 58(2): 81-117. https://doi.org/10.1007/s11301-008-0036-4.