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.

Location of the customers in the map of Brooklyn, USA

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.

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 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]

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

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

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

Simultaneous pickup and delivery problem.html

MBA, IIM Shillong