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

作者：Hernandez Perez Hipolito; Rodrguez Martn Inmaculada; Jose Salazar Gonzalez Juan

来源：Computers & Operations Research, 2009, 36(5): 1639-1645.

DOI：10.1016/j.cor.2008.03.008

• Pickup and delivery
• Traveling salesman problem
• Hybrid heuristic
• GRASP
• VND

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.

• 出版日期2009-5