Parallel Simulated Annealing metaheuristic for the Heterogenous On-Demand Bus Routing Problem

Résumé fourni par la source

This study introduces a parallel metaheuristic designed for addressing an on-demand transportation problem, namely the Heterogeneous On-Demand Bus Routing Problem (H-ODBRP). In this problem, passengers issue transportation requests and are designated to bus stations near their origin and destination locations. The fleet is heterogeneous, comprising vehicles with various capacities and stationed at depots across different locations. The primary objective is to minimize user ride times while respecting a set of constraints, including time windows and vehicle capacities. The literature to date lacks comprehensive coverage of large-scale scenarios for on-demand transportation problems, suggesting the investigation of larger instances as a direction for future research. A parallel approach is an effective method to handle the increasing size and complexity of these problems. Therefore, aiming for a balance between computational time and solution quality, we propose a parallel metaheuristic that decomposes the search space by assigning a subset of vehicles to each processor. This paper conducts a comparative analysis of the sequential and parallel algorithms in terms of computational time and objective function value. The parallel algorithm not only demonstrated better efficiency by solving the large-scale problem instances faster but also consistently outperforms the sequential approach in achieving better solution values, sometimes by as much as 30%. The experiments also tested different numbers of processing units, with the employment of 8 clusters consistently providing the better results in comparison to all other configurations for the large-scale scenarios examined in this study.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.