Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics

Janny M. Y. Leung, Thomas L. Magnanti and Vijay Singhal
Additional contact information
Janny M. Y. Leung: Yale University, New Haven, Connecticut
Thomas L. Magnanti: MIT, Cambridge, Massachusetts
Vijay Singhal: Resource Management Systems, Cambridge, Massachusetts

Transportation Science, 1990, vol. 24, issue 4, 245-260

Abstract: We develop an optimization-based approach for a point-to-point route planning problem that arises in many large scale delivery systems (for example, less-than-truckload freight, rail, mail and package delivery, communications). In these settings, a firm which must ship goods between many origin and destination pairs on a network needs to specify a route for each origin–destination pair so as to minimize transportation costs and/or transit times. Typically, the cost structure is very complicated. The approach discussed in this paper exploits the structure of the problem to decompose it into two smaller subproblems, each amenable to solution by a combination of optimization and heuristic techniques. One subproblem is an “assignment” problem with capacity constraints. The other subproblem is a mixed-integer multicommodity flow problem. We propose solution methods based on Lagrangian relaxation for each subproblem. Computational results with these methods and with a heuristic procedure for the multicommodity flow problem on a problem met in practice are encouraging and suggest that mathematical programming methods can be successfully applied to large-scale problems in delivery systems planning and other problems in logistical system design.

Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.24.4.245 (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:24:y:1990:i:4:p:245-260

Access Statistics for this article

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