A Network Flow Based Heuristic for Bulk Pickup and Delivery Routing

We consider a problem in which a fleet of vehicles must be scheduled to pickup and deliver a set of orders in truckload quantities. We describe a new algorithm based on a network flow relaxation which imposes necessary conditions on the flow of empty vehicles from order delivery points to order pickup points. The network flow model provides a lower bound and a nearly feasible solution that can be made feasible with some simple heuristics. Our algorithm is fast and has performed well on a set of more than 430 test problems which include a number of real problems obtained from the Shanghai Truck Transportation Corporation. On real problems and on random problems generated using real pickup and delivery points, the algorithm consistently produces solutions within 1% of optimality.