GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots

被引：90

作者：

Villegas, Juan G. ^{[1
,2
,3
]}

Prins, Christian ^{[2
]}

Prodhon, Caroline ^{[2
]}

Medaglia, Andres L. ^{[3
]}

Velasco, Nubia ^{[3
]}

机构：

[1] Univ Antioquia, Dept Ingn Ind, Medellin 1226, Colombia

[2] Univ Technol Troyes, Inst Charles Delaunay, LOSI, F-10010 Troyes, France

[3] Univ Los Andes, Dept Ingn Ind, COPA, Bogota 4976, Colombia

来源：

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE | 2010年 / 23卷 / 05期

关键词：

Truck and trailer routing problem (TTRP); Multi-depot vehicle routing problem (MDVRP); Greedy randomized adaptive search procedures (GRASP); Evolutionary local search (ELS); Variable neighborhood descent (VND); Iterated local search (ILS); ALGORITHM;

D O I：

10.1016/j.engappai.2010.01.013

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In the single truck and trailer routing problem with satellite depots (STTRPSD) a vehicle composed of a truck with a detachable trailer serves the demand of a set of customers reachable only by the truck without the trailer. This accessibility constraint implies the selection of locations to park the trailer before performing the trips to the customers. We propose two metaheuristics based on greedy randomized adaptive search procedures (GRASP), variable neighborhood descent (VND) and evolutionary local search (ELS) to solve this problem. To evaluate these metaheuristics we test them on a set of 32 randomly generated problems. The computational experiment shows that a multi-start evolutionary local search outperforms a GRASP/VND. Moreover, it obtains competitive results when applied to the multi-depot vehicle routing problem (MDVRP), that can be seen as a special case of the STTRPSD. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：780 / 794

页数：15

共 42 条

[1] TTT plots: a perl program to create time-to-target plots [J].

Aiex, Renata M. ;

Resende, Mauricio G. C. ;

Ribeiro, Celso C. .

OPTIMIZATION LETTERS, 2007, 1 (04) :355-366

[2] Recent advances in vehicle routing exact algorithms [J].

Baldacci, Roberto ;

Toth, Paolo ;

Vigo, Daniele .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2007, 5 (04) :269-298

[3] A unified exact method for solving different classes of vehicle routing problems [J].

Baldacci, Roberto ;

Mingozzi, Aristide .

MATHEMATICAL PROGRAMMING, 2009, 120 (02) :347-380

[4]

BELENGUER JM, 2009, TRANSPORTAT IN PRESS

[5] A heuristic approach for the truck and trailer routing problem [J].

Caramia, M. ;

Guerriero, F. .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2010, 61 (07) :1168-1180

[6] A tabu search method for the truck and trailer routing problem [J].

Chao, IM .

COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (01) :33-51

[7] An application of Special Ordered Sets to a periodic milk collection problem [J].

Claassen, G. D. H. ;

Hendriks, Th. H. B. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 180 (02) :754-769

[8]

Conover W. J., 1999, Wiley Series in Probability and Statistics

[9]

Cordeau JF, 2002, SIAM MONOG DISCR MAT, P157

[10]

Cordeau JF, 1997, NETWORKS, V30, P105, DOI 10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO

← 1 2 3 4 5 →