Solution of a min-max vehicle routing problem

被引：88

作者：

Applegate, D

Cook, W

Dash, S

Rohe, A

机构：

[1] AT&T Labs Res, Algorithms & Optimizat Dept, Florham Pk, NJ 07932 USA

[2] Princeton Univ, Program Appl & Computat Math, Princeton, NJ 08544 USA

[3] Univ Bonn, Forsch Inst Diskrete Math, D-53113 Bonn, Germany

来源：

INFORMS JOURNAL ON COMPUTING | 2002年 / 14卷 / 02期

关键词：

D O I：

10.1287/ijoc.14.2.132.118

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

W e 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, Chvatal, 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 was developed by E. Aarts and J. K. Lenstra, and the competition was sponsored by the information technology firm CMG and the newspaper De Telegraaf.

引用

页码：132 / 143

页数：12

共 30 条

[1]

AARTS E. H. L., 2000, ICIAM 99 P 4 INT C I, P141

[2]

[Anonymous], 2001, TION ENGRG

[3]

[Anonymous], 1996, WHIZZKIDS 96

[4] Solving large quadratic assignment problems on computational grids [J].

Anstreicher, K ;

Brixius, N ;

Goux, JP ;

Linderoth, J .

MATHEMATICAL PROGRAMMING, 2002, 91 (03) :563-588

[5]

Applegate D., 1998, DOC MATH J DTSCH MAT, P645

[6]

APPLEGATE D, 2001, IN PRESS COMPUTATION

[7] Separating capacity constraints in the CVRP using tabu search [J].

Augerat, P ;

Belenguer, JM ;

Benavent, E ;

Corberan, A ;

Naddef, D .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 106 (2-3) :546-557

[8]

Ball M.O., 1995, Network Routing

[9]

BLASUM U, 2000, ZPR2000386 ZENTR ANG

[10]

Cook W., 1999, CAAM TECHNICAL REPOR

← 1 2 3 →