An Iterated Local Search for the Split Delivery Vehicle Routing Problem

DOI

10.2991/cisia-15.2015.12How to use a DOI?

Keywords

SDVRP; Local Search; perturbation;Multi-restart

Abstract

A multi-restart iterated local search (MRSILS) algorithm is introduced for the Split Delivery Vehicle Routing Problem (SDVRP). The initial solution is generated by the GENIUS and applied the local search procedure by removing one node from its current route and inserting it into the best locations, with the possibility of splitting its demand. A node inserting algorithm is proposed for SDVRP, trying to find a better solution by an insertion with the consideration of splitting the demand. The perturbation is applied while certain predefined continuous no improvement local search steps are occurred. In order to extend the search space and keeping the quality of the restart solution, a method is designed for the perturbation that the perturbed solution is chosen from an elite solution set, while the best solution is preferred. The object of this work is to minimize the total travel distance. Experimental results on a benchmark set show that the MRSILS is competitive with a state of the art algorithm.

Copyright

© 2015, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Z.Z Wen
AU  - X.Y Dong
AU  - S. Han
PY  - 2015/06
DA  - 2015/06
TI  - An Iterated Local Search for the Split Delivery Vehicle Routing Problem
BT  - Proceedings of the International Conference on Computer Information Systems and Industrial Applications
PB  - Atlantis Press
SP  - 43
EP  - 46
SN  - 2352-538X
UR  - https://doi.org/10.2991/cisia-15.2015.12
DO  - 10.2991/cisia-15.2015.12
ID  - Wen2015/06
ER  -