A hybrid heuristic, based on Iterated Local Search and GENIUS, for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Issue 2 (1st January 2011)

• Record Type: Journal Article
• Authors: Souza, Marcone Jamilson Freitas; Mine, Marcio Tadayuki; Silva, Matheus de Souza Alves; Ochi, Luiz Satoru; Subramanian, Anand
• Is Part Of: International journal of logistics systems and management. Volume 10:Issue 2(2011)
• Page Start: 142
• Page End: 157
• Publication Date: 2011-01-01
• Subjects: VRPSPD -- vehicle routing problem with simultaneous pickup and delivery -- metaheuristics -- ILS -- iterated local search -- GENIUS -- variable neighbourhood descent -- reverse logistics; Business logistics -- Periodicals; 658.5005
• Languages: English
• ISSNs: 1742-7967

Abstract

This work deals with the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). The VRPSPD is a common problem in the area of reverse logistics, which aims to plan the transportation of products to customers, as well as the return of leavings or products used by them for recycling or to special depots. The VRPSPD is NP-hard, since it can be reduced to the classical Vehicle Routing Problem (VRP) when no client needs the pickup service. To solve it, we propose a hybrid heuristic algorithm, called GENILS, based on Iterated Local Search (ILS), Variable Neighbourhood Descent and GENIUS. The proposed algorithm was tested on three well-known sets of instances found in literature and it was competitive with the best existing approaches. Among the 72 test-problems of these sets, the GENILS was capable to improve the result of nine instances and to equal another 49.