A Split based Approach for the Vehicle Routing Problem with Route Balancing

Philippe Lacomme, Caroline Prodhon, Christian Prins, Xavier Gandibleux, Boris Beillevaire, Libo Ren

2014

Abstract

The vehicle routing problem with route balancing is a bi-objective routing problem, in which the total route length and the balance of routes (i.e. the difference between the maximal and minimal route length) have to be minimized. In this paper, we propose an approach based on two solution representations: a giant tour representing a sequence of customers (indirect representation) and a complete solution with a decomposition of the giant tour, combined with a split algorithm to alternate between them. This approach offers a mainly efficient way to explore the solution space. Our motivation is based on the possibility to generate efficiently several solutions a time using an indirect representation which has been already proved to be efficient in numerous routing problems resolution. The originality here is to tune the split algorithm considering two objectives. An evolutionary path relinking algorithm is embedded to improve the obtained solutions. The proposed approach is evaluated on classical vehicle routing problem instances and the results push us into accepting that the method is competitive with the best published mono-objective methods (on criteria one : the total route length). On a bi-objective point of view, our method is competitive with the lexicographic solutions reported in the literature in the sense that it provides similar or better results in comparable computational time.

Download


Paper Citation


in Harvard Style

Lacomme P., Prodhon C., Prins C., Gandibleux X., Beillevaire B. and Ren L. (2014). A Split based Approach for the Vehicle Routing Problem with Route Balancing . In Proceedings of the 3rd International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES, ISBN 978-989-758-017-8, pages 159-166. DOI: 10.5220/0004764801590166

in Bibtex Style

@conference{icores14,
author={Philippe Lacomme and Caroline Prodhon and Christian Prins and Xavier Gandibleux and Boris Beillevaire and Libo Ren},
title={A Split based Approach for the Vehicle Routing Problem with Route Balancing},
booktitle={Proceedings of the 3rd International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,},
year={2014},
pages={159-166},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004764801590166},
isbn={978-989-758-017-8},
}


in EndNote Style

TY - CONF
JO - Proceedings of the 3rd International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,
TI - A Split based Approach for the Vehicle Routing Problem with Route Balancing
SN - 978-989-758-017-8
AU - Lacomme P.
AU - Prodhon C.
AU - Prins C.
AU - Gandibleux X.
AU - Beillevaire B.
AU - Ren L.
PY - 2014
SP - 159
EP - 166
DO - 10.5220/0004764801590166