Shipment routing algorithms with tree constraints

Warren Buckler Powell, Ioannis A. Koskosidis

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)230-245
Number of pages16
JournalTransportation Science
Issue number3
StatePublished - 1992

All Science Journal Classification (ASJC) codes

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'Shipment routing algorithms with tree constraints'. Together they form a unique fingerprint.

Cite this