A powerful route minimization heuristic for the vehicle routing problem with time windows

被引：69

作者：

Nagata, Yuichi ^{[1
]}

Braysy, Olli ^{[2
]}

机构：

[1] Tokyo Inst Technol, Interdisciplinary Grad Sch Sci & Engn, Midori Ku, Kanagawa 2268502, Japan

[2] Univ Jyvaskyla, Agora Ctr, Agora Innoroad Lab, FI-40014 Jyvaskyla, Finland

来源：

OPERATIONS RESEARCH LETTERS | 2009年 / 37卷 / 05期

关键词：

Vehicle routing; Heuristics; Time windows; Guided local search; LOCAL SEARCH;

D O I：

10.1016/j.orl.2009.04.006

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We suggest an efficient route minimization heuristic for the vehicle routing problem with time windows. The heuristic is based on the ejection pool, powerful insertion and guided local search strategies. Experimental results on the Gehring and Homberger's benchmarks demonstrate that our algorithm outperforms previous approaches and found 18 new best-known solutions. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：333 / 338

页数：6

共 14 条

[1] 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

[2] Vehicle routing problem with time windows, part 1:: Route construction and local search algorithms [J].

Bräysy, I ;

Gendreau, M .

TRANSPORTATION SCIENCE, 2005, 39 (01) :104-118

[3] Vehicle routing problem with time windows, part II:: Metaheuristics [J].

Bräysy, I ;

Gendreau, M .

TRANSPORTATION SCIENCE, 2005, 39 (01) :119-139

[4]

Gehring H, 2001, ASIA PAC J OPER RES, V18, P35

[5]

GEHRING H, 1999, P EUROPEAN, V99, P57

[6] An iterated local search algorithm for the vehicle routing problem with convex time penalty functions [J].

Ibaraki, Toshihide ;

Imahori, Shinji ;

Nonobe, Koji ;

Sobue, Kensuke ;

Uno, Takeaki ;

Yagiura, Mutsunori .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (11) :2050-2069

[7] A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows [J].

Lim, Andrew ;

Zhang, Xingwen .

INFORMS JOURNAL ON COMPUTING, 2007, 19 (03) :443-457

[8]

Nagata Y, 2007, IEEE C EVOL COMPUTAT, P1175

[9]

P Kindervater GA., 1997, LOCAL SEARCH COMBINA, P337

[10] A general heuristic for vehicle routing problems [J].

Pisinger, David ;

Ropke, Stefan .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (08) :2403-2435

← 1 2 →