Solving a Vehicle Routing Problem with Ant Colony Optimisation and Stochastic Ranking

摘要

In our contribution we are concerned with a real-world vehicle routing problem (VRP), showing characteristics of VRP with time windows, multiple depots and site dependencies. An analysis of transport request data reveals that the problem is over-constrained with respect to time constraints, i.e. maximum route durations and time windows for delivery at customer sites. Our results show that ant colony optimisation combined with stochastic ranking provides appropriate means to deal with the over-constrained problem. An essential point in our investigations was the development of problem-specific heuristics, guiding ants in the construction of solutions. Computational results show that the combination of a refined distance heuristic, taking into account the distances between customer sites when performing pickup operations at depots, and a look-ahead heuristic, estimating the violation of maximum route durations and delivery time windows when performing pickup operations, provides the best results for the VRP under consideration.