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

We address in this paper the one-commodity pickup-and-delivery traveling salesman problem, which is characterized by a set of customers, each of them supplying (pickup customer) or demanding (delivery customer) a given amount of a single product. The objective is to design a minimum cost Hamiltonian...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2009-05, Vol.36 (5), p.1639-1645
Main Authors: Hernández-Pérez, Hipólito, Rodríguez-Martín, Inmaculada, Salazar-González, Juan José
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Benchmarks
Commodities
Exact sciences and technology
GRASP
Heuristic
Hybrid heuristic
Logistics
Operational research and scientific management
Operational research. Management science
Pickup and delivery
Studies
Traveling salesman problem
VND
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We address in this paper the one-commodity pickup-and-delivery traveling salesman problem, which is characterized by a set of customers, each of 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 Hernández-Pérez and Salazar-González [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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2008.03.008