Solution of a Min-Max Vehicle Routing Problem
Solution of a Min-Max Vehicle Routing Problem
复制标题
DOI：
10.1287/ijoc.14.2.132.118
复制
发表时间：
2002-04
影响因子：
2.1
通讯作者：
D. Applegate;W. Cook;S. Dash;André Rohe
中科院分区：
文献类型：
--
作者：
D. Applegate;W. Cook;S. Dash;André Rohe
我们使用分支和切割搜索解决Whizzkids'96车辆路径问题，证明在1996年的比赛中获胜的解决方案实际上是最优的。我们的算法框架结合了Applegate，Bixby，ChvAital和Cook的基于LP的旅行推销员代码，具有专门的切割平面和分布式搜索算法，允许使用位于Rice，Princeton，AT&T和Bonn的计算网络。1996年的问题实例是由E. AartsandJ. K. Lenstra，该比赛由信息技术公司CMG和De Telegraaf报纸赞助。
We use a branch-and-cut search to solve the Whizzkids'96 vehicle routing problem, demonstrating that the winning solution in the 1996 competition is in fact optimal. Our algorithmic framework combines the LP-based traveling salesman code of Applegate, Bixby, ChvAital, and Cook, with specialized cutting planes and a distributed search algorithm, permitting the use of a computing network located across Rice, Princeton, AT&T, and Bonn. The 1996 problem instance wasdeveloped by E. Aartsand J. K. Lenstra, and the competition was sponsored by the information technology firm CMG and the newspaper De Telegraaf.