Hybrid approach for the Multiple Vehicle Routing Problem with Deliveries and Selective Pickups

We propose the Multiple Vehicle Routing Problem with Delivery and Selective Pickups (MVRPDSP) along with a mixed integer linear programming formulation and a hybrid cluster-first heuristic. We show that it is possible to divide the cluster-first heuristic in sub problems which can be solved exactly...

Full description

Saved in:
Bibliographic Details
Main Authors: Bruck, B. P., dos Santos, Andre Gustavo
Format: Conference Proceeding
Language:English
Subjects:
Analysis of variance
combinatorial optimization
Context
Hybrid intelligent systems
hybrid methods
Mathematical model
Routing
vehicle routing
Vehicles
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose the Multiple Vehicle Routing Problem with Delivery and Selective Pickups (MVRPDSP) along with a mixed integer linear programming formulation and a hybrid cluster-first heuristic. We show that it is possible to divide the cluster-first heuristic in sub problems which can be solved exactly and their solutions combined in a semi-greedy way to generate good solutions. The results show that while the model is not able to find even a feasible solution for several instances the heuristic finds, for most cases, better or equal solutions in a matter of milliseconds, including 4 optimal solutions, what proves its efficiency. We also tested a combined approach, using the heuristic to generate an initial solution for the model, which improved even more the results of the heuristic.
DOI:10.1109/HIS.2012.6421345