Title: Ant colony optimisation for a 2-stage capacitated vehicle routing problem with probabilistic demand increases

Authors: Nihat Engin Toklu; Vassilis Papapanagiotou; Matthias Klumpp; Luca Maria Gambardella; Roberto Montemanni

Addresses: Dalle Molle Institute for Artificial Intelligence, IDSIA – USI/SUPSI, Galleria 2, 6928 Manno, Switzerland ' Dalle Molle Institute for Artificial Intelligence, IDSIA – USI/SUPSI, Galleria 2, 6928 Manno, Switzerland ' ild, Institute for Logistics and Service Management, FOM University of Applied Sciences, Leimkugelstraße 6, D-45141 Essen, Germany ' Dalle Molle Institute for Artificial Intelligence, IDSIA – USI/SUPSI, Galleria 2, 6928 Manno, Switzerland ' Dalle Molle Institute for Artificial Intelligence, IDSIA – USI/SUPSI, Galleria 2, 6928 Manno, Switzerland

Abstract: In this paper we address a 2-stage capacitated vehicle routing problem (CVRP) in which the demands are probabilistic and can only increase. In this CVRP variant the routes used by the fleet to satisfy the customers must be minimised. The customers' demands may increase with a probability after the beginning of the tours like the unexpected events that happen in a realistic environment. The existence of these events make sometimes the fleet fail to satisfy all the customers at their first try (1st stage). In this case, additional vehicles will be used to cover the rest of the demand (2nd stage). In this paper, an ant colony system is used to generate solutions and the effect of different objective functions used is shown. Conclusions are drawn on which evaluation method leads to near optimum routes and which to near optimum number of vehicles.

Keywords: ant colony optimisation; ACO; capacitated VRP; vehicle routing problem; CVRP; green bullwhip effect; probabilistic demand.

DOI: 10.1504/IJBIR.2016.077607

International Journal of Business Innovation and Research, 2016 Vol.11 No.1, pp.5 - 17

Received: 08 May 2021
Accepted: 12 May 2021

Published online: 07 Jul 2016 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article