Title: Ant colony optimisation for solving real-world pickup and delivery problems with hard time windows
Authors: Anna Syberfeldt; Henrik Smedberg
Addresses: University of Skövde, P.O. 408, SE-54148 Skövde, Sweden ' University of Skövde, P.O. 408, SE-54148 Skövde, Sweden
Abstract: This paper compares the performance of the classic genetic algorithm with the more recently proposed ant colony optimisation for solving real-world pickup and delivery problems with hard time windows. A real-world problem that is present worldwide - waste collection - is used to evaluate the algorithms. As in most real-world waste collection problems, many of the waste bins have time windows. The time windows stem from such things as safety regulations and customer agreements, and must be strictly adhered to. The optimisation showed that the genetic algorithm is better than the ant colony optimisation when utilising standard implementations of both algorithms. However, when the algorithms are enhanced with a local search procedure, the ant colony optimisation immediately becomes superior and achieves improved results. Local search seems to be a drawback for the genetic algorithm when hard time windows are involved. Various implementations of the local search procedure are evaluated in this paper using five different test sets. Recommendations for future implementations are given as well as additional enhancements which could improve the performance of the ant colony optimisation.
Keywords: ant colony optimisation; pickup and delivery problem; hard time windows.
World Review of Intermodal Transportation Research, 2020 Vol.9 No.1, pp.76 - 96
Accepted: 03 Jul 2019
Published online: 30 Mar 2020 *