Shipment Routing Algorithms with Tree Constraints

Warren B. Powell and Ioannis A. Koskosidis
Additional contact information
Warren B. Powell: Princeton University, School of Engineering and Applied Science, Princeton, New Jersey 08544
Ioannis A. Koskosidis: Department of Civil Engineering and The Institute for Transportation Systems, The City College of New York, New York, New York 10031

Transportation Science, 1992, vol. 26, issue 3, 230-245

Abstract: Routing shipments efficiently on less-than-truckload trucking networks represents an important subproblem of the general network design problem that arises when designing a service network. The objective of the LTL shipment routing problem is to minimize the total transportation and handling costs subject to two key constraints: (i) service between two terminals must always satisfy a given minimum frequency (measured in trailers per week) and (ii) the paths from all origins into a destination should form a tree. This second constraint reflects a practical limitation on the types of instructions that can be implemented in the field. A solution approach is developed using a shortest path based formulation with additional routing constraints imposed to refine the routing in response to minimum frequency constraints. A local improvement heuristic is presented which manipulates the routing constraints. A separate set of primal-dual algorithms are also developed which provide both upper and lower bounds. Numerical experiments are presented to evaluate the effectiveness of both the local improvement heuristic and the primal-dual algorithms.

Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.26.3.230 (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:26:y:1992:i:3:p:230-245

Access Statistics for this article

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