Vehicle routing for public transport with adapted simulated annealing

Abstract

This paper presents an Adapted Simulated Annealing (ASA) algorithm to solve an instance of the vehicle routing problem (VRP): the intercity public transport problem (IPTP). This combinatorial optimization problem was effectively solved by means of a robust method. Its performance was achieved thanks to the incorporation of an auxiliary memory and a novel choice of the neighbours. The model is based on initial random solutions capable of generating appropriate bus routes and frequencies in a large solution space. We have established a search strategy that provides excellent responses at the process level. The intercity line linking Bahía Blanca and Punta Alta was chosen with the intention of evaluating ASA performance. The real traffic-behavior has been represented by means of the simulation software called SUMO. The computational results clearly indicate that the proposed approach constitutes an improvement in the ability to search for high quality solutions that facilitates the convergence.