A NETWORK FLOW BASED HEURISTIC FOR BULK PICKUP AND DELIVERY ROUTING

We consider a problem in which a fleet of vehicles must be scheduled t o pickup and deliver a set of orders in truckload quantities. We descr ibe a new algorithm based on a network flow relaxation which imposes n ecessary 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 s ome 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 p roblems obtained from the Shanghai Truck Transportation Corporation. O n. real problems and on random problems generated using real pickup an d delivery points, the algorithm consistently produces solutions withi n 1% of optimality.