A hybrid algorithm for vehicle routing problem with time windows

被引：98

作者：

Yu, B. ^{[1
]}

Yang, Z. Z. ^{[1
]}

Yao, B. Z. ^{[2
]}

机构：

[1] Dalian Maritime Univ, Transportat Management Coll, Dalian 116026, Peoples R China

[2] Beijing Jiaotong Univ, Sch Civil Engn & Architecture, Beijing 100044, Peoples R China

来源：

EXPERT SYSTEMS WITH APPLICATIONS | 2011年 / 38卷 / 01期

基金：

美国国家科学基金会;

关键词：

VRPTW; Ant colony optimization; Neighborhood search; Tabu search; GENETIC ALGORITHM; ANT SYSTEM; SEARCH; OPTIMIZATION; COLONY;

D O I：

10.1016/j.eswa.2010.06.082

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Vehicle routing problem with time windows (VRPTVV) is a well-known combinatorial problem. Many researches have presented meta-heuristics are effective approaches for VRPTW. This paper proposes a hybrid approach, which consists of ant colony optimization (ACO) and Tabu search, to solve the problem. To improve the performance of ACO, a neighborhood search is introduced. Furthermore, when ACO is close to the convergence Tabu search is used to maintain the diversity of ACO and explore new solutions. Computational experiments are reported for a set of the Solomon's 56 VRPTW and the approach is compared with some meta-heuristic published in literature. Results show that considering the tradeoff of quality and computation time, the hybrid algorithm is a competitive approach for VRPTVV. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：435 / 441

页数：7

共 26 条

[1] A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows [J].

Alvarenga, G. B. ;

Mateus, G. R. ;

de Tomi, G. .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (06) :1561-1584

[2] An evolutionary parallel tabu search approach for distribution systems reinforcement planning [J].

Augugliaro, A ;

Dusonchet, L ;

Sanseverino, ER .

ADVANCED ENGINEERING INFORMATICS, 2002, 16 (03) :205-215

[3] Solving vehicle routing problems using constraint programming and metaheuristics [J].

Backer, BD ;

Furnon, V ;

Shaw, P ;

Kilby, P ;

Prosser, P .

JOURNAL OF HEURISTICS, 2000, 6 (04) :501-523

[4] A two-stage hybrid local search for the vehicle routing problem with time windows [J].

Bent, R ;

Van Hentenryck, P .

TRANSPORTATION SCIENCE, 2004, 38 (04) :515-530

[5] A parallel hybrid genetic algorithm for the vehicle routing problem with time windows [J].

Berger, J ;

Barkaoui, M .

COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (12) :2037-2053

[6] A parallel tabu search algorithm for solving the container loading problem [J].

Bortfeldt, A ;

Gehring, H ;

Mack, D .

PARALLEL COMPUTING, 2003, 29 (05) :641-662

[7] Tabu Search heuristics for the Vehicle Routing Problem with Time Windows [J].

Olli Bräysy ;

Michel Gendreau .

Top, 2002, 10 (2) :211-237

[8]

BRAYSY O, 2001, STF42A01021

[9] An improved ant system algorithm for the vehicle routing problem [J].

Bullnheimer, B ;

Hartl, RF ;

Strauss, C .

ANNALS OF OPERATIONS RESEARCH, 1999, 89 (0) :319-328

[10]

Chen T.K., 2001, ASIA PACIFIC J OPERA, V18, P121

← 1 2 3 →