Optimal solution of vehicle routing problems using minimum K-trees

Optimal solution of vehicle routing problems using minimum K-trees

0.00 Avg rating0 Votes
Article ID: iaor1995149
Country: United States
Volume: 42
Issue: 4
Start Page Number: 626
End Page Number: 642
Publication Date: Jul 1994
Journal: Operations Research
Authors:
Keywords: programming: integer
Abstract:

The paper considers 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. The paper shows 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 Lagrangean 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.

Reviews

Required fields are marked *. Your email address will not be published.