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 [J].
Berbeglia, Gerardo ;
Cordeau, Jean-Francois ;
Gribkovskaia, Irina ;
Laporte, Gilbert .
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 [J].
Carrabs, Francesco ;
Cerulli, Raffaele ;
Cordeau, Jean-Francois .
INFOR, 2007, 45 (04) :223-238
[3]   Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading [J].
Carrabs, Francesco ;
Cordeau, Jean-Francois ;
Laporte, Gilbert .
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 [J].
FISCHETTI, M ;
TOTH, P .
OPERATIONS RESEARCH, 1989, 37 (02) :319-328
123