Title: A multiple ant colony system with random variable neighbourhood descent for the vehicle routing problem with time windows

Authors: Orivalde S. Silva Júnior; José E. Leal

Addresses: Fortification and Construction Engineering Section, Military Institute of Engineering, Praça General Tibúrcio, 80, Urca, Rio de Janeiro, RJ, Brazil ' Department of Industrial Engineering, Pontifical Catholic University of Rio de Janeiro, Rua Marquês de São Vicente, 225, Gávea, Rio de Janeiro, RJ, Brazil

Abstract: This paper proposes hybrid heuristics that use the multiple ant colony system (MACS) and random variable neighbourhood descent (RVND) algorithms to solve the vehicle routing problem with time windows (VRPTW). This problem involves determining the minimum-cost routes for a fleet of vehicles of the same capacity to visit a set of customers within a specified time interval, called a time window. The proposed heuristic, called MACS-RVND, uses two ant colonies to reduce the number of vehicles and the total distance travelled, and a RVND algorithm is used in the local search procedure. The algorithm was tested using standard benchmark problems in the literature and produced competitive results. The use of the RVND algorithm improved the MACS-VRPTW algorithm.

Keywords: VRPTW; vehicle routing problem with time windows; metaheuristics; ant colony optimisation; ACO; random variable neighbourhood descent; RVND; delivery service.

DOI: 10.1504/IJLSM.2021.117687

International Journal of Logistics Systems and Management, 2021 Vol.40 No.1, pp.52 - 69

Received: 05 Feb 2019
Accepted: 02 Jun 2019
Published online: 21 Sep 2021 *

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