The pickup and delivery traveling salesman problem with first-in-first-out loading

被引：33
作者：
Erdogan, Guenes [1 ,2 ,3 ]
Cordeau, Jean-Francois [2 ,3 ]
Laporte, Gilbert [1 ,2 ]
机构：
[1] HEC Montreal, Canada Res Chair Distribut Management, 3000 Chem Cote St Catherine, Montreal, PQ H3T 2A7, Canada
[2] HEC Montreal, CIRRELT, Montreal, PQ H3T 2A7, Canada
[3] HEC Montreal, Canada Res Chair Logist & Transportat, Montreal, PQ H3T 2A7, Canada
来源：
COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 06期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Traveling salesman problem; Pickup and delivery; First-in-first-out; Integer programming; Tabu search; Iterated local search; HEURISTICS; ALGORITHM; SEARCH; LIFO;
D O I：
10.1016/j.cor.2008.05.005
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
This paper addresses a variation of the traveling salesman problem with pickup and delivery in which loading and unloading operations have to be executed in a first-in-first-out fashion. It provides an integer programming formulation of the problem. It also describes five operators for improving a feasible solution, and two heuristics that utilize these operators: a probabilistic tabu search algorithm, and an iterated local search algorithm. The heuristics are evaluated on data adapted from TSPLIB instances. (C) 2008 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1800 / 1808
页数：9
相关论文
共 26 条
  • [1] Static pickup and delivery problems: a classification scheme and survey
    Berbeglia, Gerardo
    Cordeau, Jean-Francois
    Gribkovskaia, Irina
    Laporte, Gilbert
    [J]. TOP, 2007, 15 (01) : 1 - 31
  • [2] An additive branch-and-bound algorithm for the pickup and delivery traveling salesman problem with LIFO or FIFO loading
    Carrabs, Francesco
    Cerulli, Raffaele
    Cordeau, Jean-Francois
    [J]. INFOR, 2007, 45 (04) : 223 - 238
  • [3] Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading
    Carrabs, Francesco
    Cordeau, Jean-Francois
    Laporte, Gilbert
    [J]. INFORMS JOURNAL ON COMPUTING, 2007, 19 (04) : 618 - 632
  • [4] CASSANI L, 2004, THESIS U MILANO ITAL
  • [5] Cordeau JF, 2007, HBK OPERAT RES MANAG, V14, P429, DOI 10.1016/S0927-0507(06)14007-4
  • [6] CORDEAU JF, 2008, NETWORKS IN PRESS
  • [7] CORDEAU JF, 2008, VEHICLE ROUTING LATE
  • [8] DUMITRESCU I, 2007, CIRRELT200801
  • [9] FICARELLI F, 2005, THESIS U MILANO ITAL
  • [10] AN ADDITIVE BOUNDING PROCEDURE FOR COMBINATORIAL OPTIMIZATION PROBLEMS
    FISCHETTI, M
    TOTH, P
    [J]. OPERATIONS RESEARCH, 1989, 37 (02) : 319 - 328
123