OPTIMAL SOLUTION OF VEHICLE-ROUTING PROBLEMS USING MINIMUM K-TREES
成果类型：
Article
署名作者：
FISHER, ML
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.4.626
发表日期：
1994
页码：
626-642
关键词：
摘要：
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.