I have this problem right here

There are N passengers whose are at places 1,2,...,N respectively. The i-th passenger, who is currently at place i, wants to go to place i+N. There are K buses are currently at place 0. Bus k can only contains q(k) number of passengers at the same time. Given the 2-dimensional array distance matrix d, where d[i][j] is the distance of place i to place j. Make an optimal route plan so that the total distance traveled by all buses is the shortest.

Input data:

  • number of passengers: N
  • number of buses: K
  • distance matrix: 2D matrix d, d[i][j] is the distance from i to j
  • List of buses' capacity: 1D matrix q, where q[k] is the capacity of bus k

Output data:

  • Route plan for K buses
  • Total distances traveled

The progress is:

  • place 0: depot
  • place 1 -> N: pickup places
  • place N+1 -> 2N: drop places

I came up with some constraints also, but I think these are not enough:

  • The number of passengers <= the capacity of the bus
  • Buses start with 0 passengers and end with 0 passengers
  • Each bus go through a place ONCE
  • ... And some more, for instance: constraint for avoiding subtours

Can anybody help me out with this problem?


1 Answer 1


The below is what I put in in another answer. It has additional LiFO constreaint- last load pickup, first to be dropped.

Basically it says after the last pickup vehicle $k$ doesn't visit any other node unless the node is a delivery point $\in D$ for the last picked up request.

Hierarchical Objective - minimize travel time and number of unserved customers. Other objectives could be minimize number of vehicles needed and transport cost.

N = $O \cup P \cup D$ where O=$\{0,2n+1\}$:depot; P=$\{1,2,...n\}$ Pickup points and
$D=\{n+1,n+2,...2n\}$ Delivery points: basically pickup and delivery points are paired\

Arcs: $A_{ij}$
Open/Close time for each point $e_i, l_i $
Vehicles: $K = \{1,2,...v\}$: with capacity $Q_k$

Parameters Request: $q_i$: it's the load from pickup $i$ to delivery $n+i$
$q_{n+i}+q_i = 0$
Customers $≡ $Pickup point request, so number of customers = $ \vert P \vert = n$

$x_{ijk} \in \{0,1\}$ indicates if vehicle $k$ is used on trip $i,j$
$T_{ik}$: Total travel time for vehicle $k$ from node $i$
$L_{ik}$: total load for vehicle $k$ from node $i$

obj = $\min w_1 (\sum_{k\in K}\sum_{i,j\in A}t_{ij}x_{ijk}) + w_2\frac{(n-\sum_k\sum_{i,j \in A}x_{ijk}-v)}2 $

$T_{ik}+ t_{ij} - M(1-x_{ijk}) \le T_{jk} \ \ \forall i,j \in A \ \forall k \in K$
$L_{ik}+ q_{j} - M(1-x_{ijk}) \le L_{jk} \ \ \forall i,j \in A \ \forall k \in K$
$e_i \le T_{ik} \le l_i \ \ i \in O$

Pairing & Precedence
$\sum_{j\in N}x_{ijk} = \sum_{j\in N}x_{j,n+i,k} \ \ \forall i \in P \ \ \forall k$
$T_i + t_{i,n+i} \le T_{n+i} \ \ \forall i \in P \ \forall k$

Enure each vehicle leaves & returns to depot: Subtour prevention $\sum_j x_{0,j,k}=\sum_i x_{i,2n+1,k}\ \ \forall k$
$\sum_j x_{0,j,k}=1 \ \ \forall k$
$1 \le \sum_k\sum_j x_{ijk} \ \ \forall i \in N$

$q_i \le L_{i,k} \ \ \forall k \ \forall i \in P$

LIFO Policy-basically after a pickup vehicle cant travel to another unpaired delivery point
$L_{n+i,k} = L_{i,k}-q_i \ \ \forall i \in P \ \forall k$
$\sum_{j\in D-\{n+i\}}x_{ijk} = 0 \ \ \forall i \in P \ \ \forall k$

$0 \le L_{i,k}; 0\le T_{i,k} \ \forall i \in N $

$w_1,w_2$ are objective weights for significance or priority.

References that explain it better
U of Montreal,


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.