A Network Flow Based Heuristic for Bulk Pickup and Delivery Routing

Marshall L. Fisher, Baoxing Tang and Zhang Zheng
Additional contact information
Marshall L. Fisher: Department of Decision Sciences, The Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania 19104-6366
Baoxing Tang: United Airlines, Executive Offices-EXOEB, Chicago, Illinois 60666
Zhang Zheng: Department of Industrial Engineering Management, Shanghai Jiao Tong University, Shanghai 20030, Peoples Republic of China

Transportation Science, 1995, vol. 29, issue 1, 45-55

Abstract: 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.

Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.29.1.45 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:29:y:1995:i:1:p:45-55

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().