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?