Title: A hybrid heuristic, based on Iterated Local Search and GENIUS, for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

Authors: Marcone Jamilson Freitas Souza; Marcio Tadayuki Mine; Matheus de Souza Alves Silva; Luiz Satoru Ochi; Anand Subramanian

Addresses: Universidade Federal de Ouro Preto, Campus Universitario, Morro do Cruzeiro 35.400-000 Ouro Preto, Minas Gerais, Brazil. ' Universidade Federal Fluminense, Rua Passo da Patria, 156 – Bloco E – 3° andar, 24.210-240 Niteroi, Rio de Janeiro, Brazil. ' Universidade Federal Fluminense, Rua Passo da Patria, 156 – Bloco E – 3° andar, 24.210-240 Niteroi, Rio de Janeiro, Brazil. ' Universidade Federal Fluminense, Rua Passo da Patria, 156 – Bloco E – 3° andar, 24.210-240 Niteroi, Rio de Janeiro, Brazil. ' Universidade Federal Fluminense, Rua Passo da Patria, 156 – Bloco E – 3° andar, 24.210-240 Niteroi, Rio de Janeiro, Brazil

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.

Keywords: VRPSPD; vehicle routing problem; simultaneous pickup delivery; metaheuristics; ILS; iterated local search; GENIUS; variable neighbourhood descent; reverse logistics.

DOI: 10.1504/IJLSM.2011.042625

International Journal of Logistics Systems and Management, 2011 Vol.10 No.2, pp.142 - 157

Published online: 06 May 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article