Fifty Years of Vehicle Routing

被引：634

作者：

Laporte, Gilbert ^{[1
]}

机构：

[1] HEC Montreal, CIRRELT, Montreal, PQ H3T 2A7, Canada

来源：

TRANSPORTATION SCIENCE | 2009年 / 43卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

vehicle routing problem; traveling salesman problem; exact algorithms; heuristics; metaheuristics; survey; GUIDED EVOLUTION STRATEGIES; EXACT ALGORITHM; TABU SEARCH; BRANCH; OPTIMIZATION; HEURISTICS; EXTENSIONS; PATHS; DEPOT;

D O I：

10.1287/trsc.1090.0301

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The Vehicle Routing Problem (VRP) was introduced 50 years ago by Dantzig and Ramser under the title "The Truck Dispatching Problem." The study of the VRP has given rise to major developments in the fields of exact algorithms and heuristics. In particular, highly sophisticated exact mathematical programming decomposition algorithms and powerful metaheuristics for the VRP have been put forward in recent years. The purpose of this article is to provide a brief account of this development.

引用

页码：408 / 416

页数：9

共 89 条

[1] A SET-PARTITIONING BASED EXACT ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM [J].

AGARWAL, Y ;

MATHUR, K ;

SALKIN, HM .

NETWORKS, 1989, 19 (07) :731-749

[2] PARALLEL SAVINGS BASED HEURISTICS FOR THE DELIVERY PROBLEM [J].

ALTINKEMER, K ;

GAVISH, B .

OPERATIONS RESEARCH, 1991, 39 (03) :456-469

[3]

[Anonymous], 2003, Handbook of rnetaheuristics

[4]

[Anonymous], 1987, Surveys in Combinatorial Optimization, North-Holland Mathematics Studies

[5]

Applegate D., 2007, TRAVELING SALESMAN P

[6] Extensions to the generalised assignment heuristic for vehicle routing [J].

Baker, BM ;

Sheasby, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 119 (01) :147-157

[7] SET PARTITIONING - SURVEY [J].

BALAS, E ;

PADBERG, MW .

SIAM REVIEW, 1976, 18 (04) :710-760

[8] An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation [J].

Baldacci, R ;

Hadjiconstantinou, E ;

Mingozzi, A .

OPERATIONS RESEARCH, 2004, 52 (05) :723-738

[9] An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts [J].

Baldacci, Roberto ;

Christofides, Nicos ;

Mingozzi, Aristide .

MATHEMATICAL PROGRAMMING, 2008, 115 (02) :351-385

[10] ON INTEGER-PROGRAM FOR DELIVERY PROBLEM [J].

BALINSKI, ML ;

QUANDT, RE .

OPERATIONS RESEARCH, 1964, 12 (02) :300-&

← 1 2 3 4 5 6 7 8 9 →