A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks

被引：22

作者：

Cote, Jean-Francois ^{[1
,2
]}

Archetti, Claudia ^{[3
]}

Speranza, Maria Grazia ^{[3
]}

Gendreau, Michel ^{[2
,4
]}

Potvin, Jean-Yves ^{[1
,2
]}

机构：

[1] Univ Montreal, Dept Informat & Rech Operat, CP 6128,Succ Ctr Ville, Montreal, PQ H3C 3J7, Canada

[2] Univ Montreal, Ctr Interuniv Rech Reseaux Entreprise Logist & Tr, Montreal, PQ H3C 3J7, Canada

[3] Univ Brescia, Dipartimento Metodi Quantitat, I-25122 Brescia, Italy

[4] Ecole Polytech, Dept Math & Genie Ind, Montreal, PQ H3C 3A7, Canada

来源：

NETWORKS | 2012年 / 60卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

traveling salesman; pickup; delivery; loading; multiple stacks; VEHICLE-ROUTING PROBLEM; 2-DIMENSIONAL LOADING CONSTRAINTS; VARIABLE NEIGHBORHOOD SEARCH; TIME WINDOWS; BOUND ALGORITHM; LIFO; FORMULATION; TSP;

D O I：

10.1002/net.21459

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This article studies the pickup and delivery traveling salesman problem with multiple stacks. The vehicle contains a number of (horizontal) stacks of finite capacity for loading items from the rear of the vehicle. Each stack must satisfy the last-in-first-out constraint that states that any new item must be loaded on top of a stack and any unloaded item must be on top of its stack. A branch-and-cut algorithm is proposed for solving this problem. Computational results are reported on different types of randomly generated instances as well as on classical instances for some well-known special cases of the problem. (c) 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 60(4), 212-226 2012

引用

页码：212 / 226

页数：15

共 34 条

[1] THE PRECEDENCE-CONSTRAINED ASYMMETRIC TRAVELING SALESMAN POLYTOPE [J].

BALAS, E ;

FISCHETTI, M ;

PULLEYBLANK, WR .

MATHEMATICAL PROGRAMMING, 1995, 68 (03) :241-265

[2] The Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs [J].

Battarra, Maria ;

Erdogan, Guenes ;

Laporte, Gilbert ;

Vigo, Daniele .

TRANSPORTATION SCIENCE, 2010, 44 (03) :383-399

[3] 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

[4] 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

[5] A branch-and-bound algorithm for the double travelling salesman problem with two stacks [J].

Carrabs, Francesco ;

Cerulli, Raffaele ;

Speranza, Maria Grazia .

NETWORKS, 2013, 61 (01) :58-75

[6]

Casazza M., 2009, COL TWENT WORKSH GRA, P7

[7] A branch-and-cut algorithm for the dial-a-ride problem [J].

Cordeau, Jean-Francois .

OPERATIONS RESEARCH, 2006, 54 (03) :573-586

[8] A Branch-and-Cut Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading [J].

Cordeau, Jean-Francois ;

Iori, Manuel ;

Laporte, Gilbert ;

Salazar Gonzalez, Juan Jose .

NETWORKS, 2010, 55 (01) :46-59

[9] Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading [J].

Cordeau, Jean-Francois ;

Dell'Amico, Mauro ;

Iori, Manuel .

COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (05) :970-980

[10]

Cote J.-F., IN PRESS

← 1 2 3 4 →