Vehicle Root Optimization for simultaneous pick up and delivery: A mixed integer formulation
Problem
There are n customers locations and a depot location. At the customer’s locations, there are delivery and pickup demands. A depot has m vehicles and all the vehicles have capacity C. Rij is the delivery amount on board between the nodes i and j and Pij is the pickup amount on board between the nodes i and j. cost for each of the vehicles is $1000 per km. With help of this model following Questions can be answered.
(1) What should be the optimum number of vehicles to be used?
(2) What should be the optimum route map for each vehicles?
(3) What should be the delivery amount for each vehicles at each of the customer nodes the vehicles visit.
(4) Pick up amount of each vehicles at each nodes the vehicles visit.
Formulation of the problem into mixed integer programming
The objective function is given by
Here, dij is the cost of travel from node i to j.
and xij ={0,1}, 1 if path is chosen between i and j otherwise 0.
Decision Variables
Rij: amount of delivery goods on board between nodes i and j
Pij: amount of pick up goods on board between nodes i and j
Constraints
Constraints 1:
The first constraints for the problem is :
and
Constraints 2:
The second constraint of the problem is
Rij : The amount of delivery goods on board between nodes i and j
Constraints 3:
The third constraint of the problem is
Where Pij : The amount of pick up goods on board between nodes i and j
Constraints 4:
The fourth constraints of the problem are given by:
and
Constraints 5:
Constraints 6:
Constraints 7:
Pickup and delivery demand at each customers nodes
The pickup demand in units at each customer location is given by the following array.
pick up demand = [1209, 866, 867, 1442, 1015, 904, 1272, 1176, 984, 1289, 973,
1368]
delivery demand = [0, 1551, 1371, 1759, 1454, 1591, 1163, 1491, 1219, 1013, 1716, 1961]
Costs of travel between nodes
The costs of travel between nodes are given by the following table. Here node 0 represents depot and nodes 1 to 11 represents customers
The location of each node is given in the following table
Results
Optimum number of vehicle is 3. The total optimum cost for vehicle 1 is $ 19144.484. The optimum path for each vehicles is given by the following figures
Optimum path for vehicle 1
Optimum path for vehicle 2
Optimum path for vehicle 3
Conclusion
The problem is successfully implemented in mixed integer programming. The model can be useful in public transport in which vehicles deliver and pick passenger simultaneously. Also it can be used to optimize the delivery logistics of a firm or factory.
Following is the link of the full code for the above problem
