A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

被引：191

作者：

Subramanian, A. ^{[1
]}

Drummond, L. M. A. ^{[1
]}

Bentes, C. ^{[2
]}

Ochi, L. S. ^{[1
]}

Farias, R. ^{[3
]}

机构：

[1] Univ Fed Fluminense, Inst Computacao, BR-24210240 Niteroi, RJ, Brazil

[2] Univ Estado Rio de Janeiro, Dept Engn Sistemas, BR-20550900 Rio De Janeiro, Brazil

[3] Univ Fed Rio de Janeiro, Ctr Tecnol, BR-21945970 Rio De Janeiro, Brazil

来源：

COMPUTERS & OPERATIONS RESEARCH | 2010年 / 37卷 / 11期

关键词：

Parallel computing; Metaheuristic; Vehicle routing; Pickup and delivery; TABU SEARCH ALGORITHM; SINGLE; BRANCH; PRICE;

D O I：

10.1016/j.cor.2009.10.011

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper presents a parallel approach for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). The parallel algorithm is embedded with a multi-start heuristic which consists of a variable neighborhood descent procedure, with a random neighborhood ordering (RVND), integrated in an iterated local search (ILS) framework. The experiments were performed in a cluster with a multi-core architecture using up to 256 cores. The results obtained on the benchmark problems, available in the literature, show that the proposed algorithm not only improved several of the known solutions, but also presented a very satisfying scalability. (C) 2009 Elsevier Ltd. All rights reserved.

引用

页码：1899 / 1911

页数：13

共 45 条

[1]

Alba E, 2004, LECT NOTES COMPUT SC, V3004, P11

[2]

Angelelli E., 2002, Quantitative approaches to distribution logistics and supply chain management, P249

[3]

Attanasio A, 2004, PARALLEL COMPUT, V30, P377, DOI [10.1016/j.parco.2003.12.001, 10.1016/j.parco.2004.12.001]

[4] A parallel hybrid genetic algorithm for the vehicle routing problem with time windows [J].

Berger, J ;

Barkaoui, M .

COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (12) :2037-2053

[5] Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery [J].

Bianchessi, Nicola ;

Righini, Giovanni .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (02) :578-594

[6] Parallel tabu search for a pickup and delivery problem under track contention [J].

Caricato, P ;

Ghiani, G ;

Grieco, A ;

Guerriero, E .

PARALLEL COMPUTING, 2003, 29 (05) :631-639

[7] Vehicle routing problem with simultaneous deliveries and pickups [J].

Chen, JF ;

Wu, TH .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2006, 57 (05) :579-587

[8]

Cordeau JF, 2005, OPERAT RES COMP SCI, V30, P145

[9]

CRAINIC TG, 2008, PARALLEL SOLUTION ME, P171

[10] Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls [J].

Crispim, J ;

Brandao, J .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2005, 56 (11) :1296-1302

← 1 2 3 4 5 →