A cooperative strategy for a vehicle routing problem with pickup and delivery time windows

A vehicle routing problem with pickup and delivery time windows is studied with the objective of determining resource requirements and daily routing by minimizing the sum of vehicle fixed costs and travelling costs. The multiple use of vehicles can reduce costs. Such a cooperative strategy, which has received little attention in past literature but which occurs in practice, may generate further savings. The strategy is studied here, with the single or multiple use of vehicles. Vehicles are allowed to travel to transfer items to another vehicle returning to the depot, provided no time window constraint is violated. This is modelled by an exact integer programming formulation which includes the solutions of the independent strategy. The proposed models are compared with a construction heuristic [Lu, Q. & Dessouky, M. M. (2006). A new insertion-based construction heuristic for solving pickup and delivery problem with time windows. European Journal of Operational Research, 175 (2) 672-687] which was applied to this problem. Experiments with instances generated from real-life data and simulated data show (i) significant savings over the construction heuristic as problem size grows: and (ii) multiple use of vehicles with a cooperative strategy may achieve cost savings over the independent strategy. (C) 2008 Elsevier Ltd. All rights reserved.