A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem
| Autor: | Inmaculada Rodríguez-Martín, Hipólito Hernández-Pérez, Juan-José Salazar-González |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Traveling purchaser problem
Mathematical optimization General Computer Science Heuristic (computer science) Heuristic Computer science GRASP Management Science and Operations Research 2-opt Travelling salesman problem Hybrid algorithm Modeling and Simulation Heuristics Bottleneck traveling salesman problem Metaheuristic |
| Zdroj: | Computers & Operations Research. 36:1639-1645 |
| ISSN: | 0305-0548 |
| DOI: | 10.1016/j.cor.2008.03.008 |
| Popis: | 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 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect