Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees

Marshall L. Fisher
Additional contact information
Marshall L. Fisher: University of Pennsylvania, Philadelphia, Pennsylvania

Operations Research, 1994, vol. 42, issue 4, 626-642

Abstract: We consider the problem of optimally scheduling a fleet of K vehicles to make deliveries to n customers subject to vehicle capacity constraints. Given a graph with n + 1 nodes, a K-tree is defined to be a set of n + K edges that span the graph. We show that the vehicle routing problem can be modeled as the problem of finding a minimum cost K-tree with two K edges incident on the depot and subject to some side constraints that impose vehicle capacity and the requirement that each customer be visited exactly once. The side constraints are dualized to obtain a Lagrangian problem that provides lower bounds in a branch-and-bound algorithm. This algorithm has produced proven optimal solutions for a number of difficult problems, including a well-known problem with 100 customers and several real problems with 25–71 customers.

Keywords: programming; integer; algorithms; relaxation/subgradient: k-tree based; transportation; vehicle routing; optimization algorithm (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (72)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.4.626 (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:oropre:v:42:y:1994:i:4:p:626-642

Access Statistics for this article

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