Metaheuristics for the single vehicle routing problem with deliveries and selective pickups

In this work we propose some metaheuristics to solve a routing problem with mandatory deliveries and selective pickups. There are two integer programming formulations proposed in the literature but they are able to solve to optimality only small-sized instances. Some greedy heuristics and metaheuris...

Full description

Saved in:
Bibliographic Details
Main Authors: Bruck, B. P., dos Santos, Andre Gustavo, Arroyo, J. E. C.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
evolutionary algorithm
Evolutionary computation
Maintenance engineering
metaheuristics
Routing
Sociology
Statistics
vehicle routing
Vehicles
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work we propose some metaheuristics to solve a routing problem with mandatory deliveries and selective pickups. There are two integer programming formulations proposed in the literature but they are able to solve to optimality only small-sized instances. Some greedy heuristics and metaheuristics have also been proposed: Tabu Search, General Variable Neighborhood Search and Evolutionary Algorithm. Here we proposed an Iterated Local Search and a Variable Neighborhood Search algorithms, and improve the performance of the previous Evolutionary Algorithm. We present experimental results on 68 instances and show that our methods outperforms the others in several cases, finding better solutions for 21 of them. Using a theoretical lower bound we prove the optimality of the solutions for 8 instances.
ISSN:2164-7143
2164-7151
DOI:10.1109/ISDA.2012.6416626