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

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.