Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading

被引：89

作者：

Carrabs, Francesco ^{[1
]}

Cordeau, Jean-Francois

Laporte, Gilbert

机构：

[1] Univ Salerno, Dipartimento Matemat & Informat, I-84084 Fisciano, Italy

[2] HEC Montreal, Ctr Res Transportat, Quebec City, PQ H3T 2A7, Canada

来源：

INFORMS JOURNAL ON COMPUTING | 2007年 / 19卷 / 04期

关键词：

traveling salesman problem; pickup and delivery; LIFO loading; variable neighborhood search;

D O I：

10.1287/ijoc.1060.0202

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

T his 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 last-in-first-out (LIFO) order. We introduce three new local search operators for this problem, which are then embedded within a variable neighborhood search heuristic. We evaluate the performance of the heuristic on data adapted from TSPLIB instances.

引用

页码：618 / 632

页数：15

共 23 条

[1]

CARRABS F, 2005, THESIS U SALERNO FIS

[2]

Cassani L., 2004, 35 ANN C ITALIAN OPE

[3]

Cordeau JF, 2007, HBK OPERAT RES MANAG, V14, P429, DOI 10.1016/S0927-0507(06)14007-4

[4] AN ADDITIVE BOUNDING PROCEDURE FOR COMBINATORIAL OPTIMIZATION PROBLEMS [J].

FISCHETTI, M ;

TOTH, P .

OPERATIONS RESEARCH, 1989, 37 (02) :319-328

[5]

Hansen P., 2005, VARIABLE NEIGHBORHOO, P211, DOI DOI 10.1007/0-387-28356-0_8

[6] A NEW EXTENSION OF LOCAL SEARCH APPLIED TO THE DIAL-A-RIDE PROBLEM [J].

HEALY, P ;

MOLL, R .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 83 (01) :83-104

[7] AN ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM WITH PICKUP AND DELIVERY CUSTOMERS [J].

KALANTARI, B ;

HILL, AV ;

ARORA, SR .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1985, 22 (03) :377-386

[8]

Ladany S. P., 1984, Transport Planning and Technology, V8, P301, DOI 10.1080/03081068408717261

[9] Optimal routing of multiple-load AGV subject to LIFO loading constraints [J].

Levitin, G ;

Abezgaouz, R .

COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (03) :397-410

[10]

LEVITIN H, 1986, SOVIET J COMPUT SYST, V24, P151

← 1 2 3 →