The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates

被引：106
作者：
Cattaruzza, Diego [1 ,2 ,3 ]
Absi, Nabil [1 ,2 ]
Feillet, Dominique [1 ,2 ]
机构：
[1] Ecole Mines St Etienne, F-13541 Gardanne, France
[2] LIMOS UMR CNRS 6158, F-13541 Gardanne, France
[3] Univ Lille, CNRS, Ctr Rech Informat Signal & Automat Lille, Centrale Lille,CRIStAL,UMR 9189, F-59000 Lille, France
来源：
TRANSPORTATION SCIENCE | 2016年 / 50卷 / 02期
关键词：
vehicle routing; multi-trip; release dates; genetic algorithm; split; EXACT ALGORITHM; LOCAL SEARCH;
D O I：
10.1287/trsc.2015.0608
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The multi-trip vehicle routing problem with time windows and release dates is a variant of the multi-trip vehicle routing problem where a time window and a release date are associated with each customer. The release date represents the date when the merchandise requested by a customer becomes available at the depot. The interest for this problem comes from the field of city logistics and the study of delivery systems involving City Distribution Centers (CDC). In these systems, goods are first delivered to a CDC before being transferred to eco-friendly vehicles for final delivery. We propose to address the problem through a population-based algorithm, with a giant tour representation for individuals. An efficient labeling procedure allows turning giant tours into solutions. Experiments demonstrate the effectiveness of the method.
引用
收藏
页码：676 / 693
页数：18
相关论文
共 37 条
  • [1] Multi-period vehicle loading with stochastic release dates
    Arda, Yasemin
    Crama, Yves
    Kronus, David
    Pironet, Thierry
    Van Hentenryck, Pascal
    [J]. EURO JOURNAL ON TRANSPORTATION AND LOGISTICS, 2014, 3 (02) : 93 - 119
  • [2] An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles
    Azi, Nabila
    Gendreau, Michel
    Potvin, Jean-Yves
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 202 (03) : 756 - 763
  • [3] An exact algorithm for a single-vehicle routing problem with time windows and multiple routes
    Azi, Nabila
    Gendreau, Michel
    Potvin, Jean-Yves
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 178 (03) : 755 - 766
  • [4] An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem
    Battarra, M.
    Monaci, M.
    Vigo, D.
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (11) : 3041 - 3050
  • [5] Blazewicz J, 2007, INT HDB INFORM SYSTE, P73
  • [6] Vehicle routing problem with time windows, part 1:: Route construction and local search algorithms
    Bräysy, I
    Gendreau, M
    [J]. TRANSPORTATION SCIENCE, 2005, 39 (01) : 104 - 118
  • [7] Vehicle routing problem with time windows, part II:: Metaheuristics
    Bräysy, I
    Gendreau, M
    [J]. TRANSPORTATION SCIENCE, 2005, 39 (01) : 119 - 139
  • [8] An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows
    Cattaruzza, Diego
    Absi, Nabil
    Feillet, Dominique
    Vigo, Daniele
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2014, 51 : 257 - 267
  • [9] A memetic algorithm for the Multi Trip Vehicle Routing Problem
    Cattaruzza, Diego
    Absi, Nabil
    Feillet, Dominique
    Vidal, Thibaut
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 236 (03) : 833 - 848
  • [10] Crainic T. G., 2008, State-of-the-Art Decision-Making Tools in the InformationIntensive Age, P181
1234