The transit route network design problem (TRNDP) has long attracted research attention, with many metaheuristic approaches proposed for its solution. So far, and despite the promising performance of Variable Neighbourhood Search (VNS) variants for vehicle routing problems, the performance of the algorithm on the TRNDP remains unexplored. In this context, this study develops a VNS-based algorithm for the problem at hand. The performance of the algorithm is tested using benchmark networks used in bus transit network design and compared with some of the most recent and efficient methods from the literature. Results show that the algorithm yields superior results over existing implementations in short computational times.
The Urban Transit Routing Problem (UTRP) is a challenging discrete problem that revolves around designing efficient routes for public transport systems. It falls under the category of NP-hard problems, characterized by its complexity and numerous constraints. Evaluating potential route sets for feasibility is a demanding and time-consuming task, often resulting in the rejection of many solutions. Given its difficulty, metaheuristic methods, such as swarm intelligence algorithms, are considered highly suitable for addressing the UTRP. However, the effectiveness of these methods depends heavily on appropriately adapting them to discrete problems, as well as employing suitable initialization procedures and solution-evaluation methods. In this study, a new variant of the particle swarm optimization algorithm is proposed as an efficient solution approach for the UTRP. We present an improved initialization function and improved modification operators, along with a post-optimization routine to further improve solutions. The algorithm’s performance is then compared to the state of the art using Mandl’s widely recognized benchmark, a standard for evaluating UTRP solutions. By comparing the generated solutions to published results from 10 studies on Mandl’s benchmark network, we demonstrate that the developed algorithm outperforms existing techniques, providing superior outcomes.
This paper deals with the school timetabling problem. The problem was formulated as encountered in a typical Greek high school. A local version of the particle swarm optimization algorithm was developed and applied to the problem at hand. Results on well-established benchmark instances showed that the proposed algorithm achieved the proven optima provided from an integer programming method presented in earlier research. In almost all cases, the current algorithm beat the integer programming method, either concerning the lower bound yielded or the execution time needed.