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 条

[21] A heuristic for the pickup and delivery traveling salesman problem
Renaud, J
Boctor, FF
Ouenniche, J
[J]. COMPUTERS & OPERATIONS RESEARCH, 2000, 27 (09) : 905 - 916
[22] Perturbation heuristics for the pickup and delivery traveling salesman problem
Renaud, J
Boctor, FF
Laporte, G
[J]. COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (09) : 1129 - 1141
[23] Rosenkrantz D. H., 1977, SIAM Journal on Computing, V6, P563, DOI 10.1137/0206041
[24] The pickup and delivery problem: Faces and branch-and-cut algorithm
Ruland, KS
Rodin, EY
[J]. COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1997, 33 (12) : 1 - 13
[25] AN EFFICIENT IMPLEMENTATION OF LOCAL SEARCH ALGORITHMS FOR CONSTRAINED ROUTING-PROBLEMS
SAVELSBERGH, MWP
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 47 (01) : 75 - 85
[26] Wong R. T., 1980, Proceedings of the IEEE International Conference on Circuits and Computers ICCC 80, P149

← 1 2 3 →