Optimization Online


A cluster-first route-second approach for the Swap Body Vehicle Routing Problem

Juan Jose Miranda-Bront (jmiranda***at***dc.uba.ar)
Brian Curcio (bcurcio***at***dc.uba.ar)
Isabel Méndez-Díaz (imendez***at***dc.uba.ar)
Agustin Montero (aimontero***at***dc.uba.ar)
Federico Pousa (fpousa***at***dc.uba.ar)
Paula Zabala (pzabala***at***dc.uba.ar)

Abstract: The Swap Body Vehicle Routing Problem (SB-VRP) is a generalization of the classical Vehicle Routing Problem (VRP) where a particular structure as well as several operational aspects for the trucks composing the fleet are considered. This research has been motivated by the VeRoLog Solver Challenge 2014, organized together by VeRoLog and PTV group, aiming to motivate the study of real-world logistic problems. A truck can carry either only one swap body or, in addition, an extra trailer with an extra swap body. For the latter, special depots, called swap locations, can be used to drop and pickup the swap bodies. These operations may affect the feasibility and the cost of a route, and therefore the overall operational cost. In this paper, we propose a cluster-first route-second heuristic for the SB-VRP. Computational experiments are conducted over the benchmark instances proposed for the competition, simulating a practical environment by considering limited resources and execution time. The results obtained are of very good quality, where our approach ended as runner-up in the final set of instances and performs similarly to the other algorithms in the remaining cases, showing its potential to be applied in practice.

Keywords: Swap-Body VRP, Iterated Local Search, GRASP, Cluster-first route-second

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation: Miranda-Bront, J.J., Curcio, B., Méndez-Díaz, I., Montero, A., Pousa, F. and Zabala, P., A cluster-first route-second approach for the swap body vehicle routing problem, Annals of Operations Research, 1--22, 2016.


Entry Submitted: 03/19/2015
Entry Accepted: 03/19/2015
Entry Last Modified: 06/29/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society