A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem

被引：61

作者：

Hernandez-Perez, Hipolito ^{[1
]}

Rodriguez-Martin, Inmaculada ^{[1
]}

Jose Salazar-Gonzalez, Juan ^{[1
]}

机构：

[1] Univ La Laguna, Fac Matemat, DEIOC, Tenerife 38271, Spain

来源：

COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 05期

关键词：

Pickup and delivery; Traveling salesman problem; Hybrid heuristic; GRASP; VND; ALGORITHM;

D O I：

10.1016/j.cor.2008.03.008

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We address in this paper the one-commodity pickup-and-delivery traveling salesman problem, which is characterized by a set of customers, each or them Supplying (pickup customer) or demanding (delivery customer) a given amount of a single product. The objective is to design a minimum cost Hamiltonian route for a capacitated vehicle in order to transport the product from the pickup to the delivery customers, The vehicle starts the route from a depot, and its initial load also has to be determined. We propose a hybrid algorithm that combines the GRASP and VND metaheuristics. Our heuristic is compared with other approximate algorithms described in Hernandez-Perez and Salazar-Gonzalez Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science 2004:38:245-55]. Computational experiments on benchmark instances reveal that Our hybrid method yields better results than the previously proposed approaches. (c) 2008 Elsevier Ltd. All rights reserved.

引用

页码：1639 / 1645

页数：7