A multi-start local search algorithm for the vehicle routing problem with time windows

被引：30
|
作者：
Bräysy, O
Hasle, G
Dullaert, W
机构：
[1] SINTEF Applied Math, Dept Optimisat, N-0314 Oslo, Norway
[2] Univ Antwerp, Ufsia Ruca Fac Appl Econ, B-2000 Antwerp, Belgium
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2004年 / 159卷 / 03期
关键词：
routing; time windows; metaheuristics;
D O I：
10.1016/s0377-2217(03)00435-1
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper a multi-start local search (MSLS) heuristic is proposed for the vehicle routing problem with time windows (VRPTW). In VRPTW the objective is to design least cost routes for a fleet of identical capacitated vehicles to service geographically scattered customers within pre-specified service time windows. The suggested approach is based on a MSLS framework and several new improvement heuristics. A new speedup technique is introduced for the construction heuristics, and the results of the MSLS are post-optimized by a threshold accepting post-processor. Experimental results on 358 benchmark problems from the literature show that the suggested method is highly efficient and competitive. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：586 / 605
页数：20
相关论文
共 50 条
  • [1] Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services
    Michallet, Julien
    Prins, Christian
    Amodeo, Lionel
    Yalaoui, Farouk
    Vitry, Gregoire
    COMPUTERS & OPERATIONS RESEARCH, 2014, 41 : 196 - 207
  • [2] A multi-start local search heuristic for the Green Vehicle Routing Problem based on a multigraph reformulation
    Andelmin, J.
    Bartolini, E.
    COMPUTERS & OPERATIONS RESEARCH, 2019, 109 : 43 - 63
  • [3] Reducing traveled distance in the Vehicle Routing Problem with Time Windows using a multi-start simulated annealing
    de Oliveira, Humberto Cesar Brandao
    Vasconcelos, Germano Crispim
    Alvarenga, Guilherme Bastos
    2006 IEEE INTERNATIONAL JOINT CONFERENCE ON NEURAL NETWORK PROCEEDINGS, VOLS 1-10, 2006, : 3013 - +
  • [4] A Multi Start Iterated Local Search algorithm for the multi compartment vehicle routing problem
    Joseph, Cadet David
    Prins, Christian
    Amodeo, Lionel
    Yalaoui, Farouk
    10TH INTERNATIONAL INDUSTRIAL SIMULATION CONFERENCE 2012 (ISC 2012), 2012, : 125 - 129
  • [5] Multi-start Iterated Local Search for the Mixed Fleet Vehicle Routing Problem with Heterogenous Electric Vehicles
    Sassi, Ons
    Cherif-Khettaf, W. Ramdane
    Oulamara, Ammar
    EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, EVOCOP 2015, 2015, 9026 : 138 - 149
  • [6] A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem
    Duhamel, Christophe
    Lacomme, Philippe
    Quilliot, Alain
    Toussaint, Helene
    COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (03) : 617 - 640
  • [7] Evolutionary Local Search Algorithm to Solve the Multi-Compartment Vehicle Routing Problem with Time Windows
    Melechovsky, Jan
    PROCEEDINGS OF 30TH INTERNATIONAL CONFERENCE MATHEMATICAL METHODS IN ECONOMICS, PTS I AND II, 2012, : 564 - 568
  • [8] Three multi-start data-driven evolutionary heuristics for the vehicle routing problem with multiple time windows
    Slim Belhaiza
    Rym M’Hallah
    Ghassen Ben Brahim
    Gilbert Laporte
    Journal of Heuristics, 2019, 25 : 485 - 515
  • [9] Three multi-start data-driven evolutionary heuristics for the vehicle routing problem with multiple time windows
    Belhaiza, Slim
    M'Hallah, Rym
    Ben Brahim, Ghassen
    Laporte, Gilbert
    JOURNAL OF HEURISTICS, 2019, 25 (03) : 485 - 515
  • [10] A Multi-Start Algorithm and a Large Neighborhood Search for a Maritime Inventory Routing Problem
    Friske, Marcelo W.
    Buriol, Luciana S.
    2020 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2020,
12345