Performance characterization of reinforcement learning-enabled evolutionary algorithms for integrated school bus routing and scheduling problem

Abstract

Bi-objective school bus scheduling optimization problem that is a subset of vehicle fleet scheduling problem is focused in this paper. In the literature, school bus routing and scheduling problem is proven to be an NP-Hard problem. The processed data supplied by our framework is utilized to search a near-optimum schedule with the aid of reinforcement learning by evolutionary algorithms. They are named as reinforcement learning-enabled genetic algorithm (RL-enabled GA), reinforcement learning-enabled particle swarm optimization algorithm (RL-enabled PSO), and reinforcement learning-enabled ant colony optimization algorithm (RL-enabled ACO). In this paper, the performance characterization of reinforcement learning-enabled evolutionary algorithms for integrated school bus routing and scheduling problem is investigated. The efficiency of the conventional algorithms is improved, and the near-optimal schedule is achieved significantly in a shorter duration with the active guidance of the reinforcement learning algorithm. We attempt to carry out extensive performance evaluation and conducted experiments on a geospatial dataset comprising road networks, trip trajectories of buses, and the address of students. The conventional and reinforcement learning integrated algorithms are improving the travel time of buses and the students. More than 50% saving by the conventional and the reinforcement learning-enabled ant colony optimization algorithm compared to the constructive heuristic algorithm is achieved from 92nd and 54th iterations, respectively. Similarly, the saving by the conventional and the reinforcement learning-enabled genetic algorithm is 41.34% at 500th iterations and more than 50% improvement from 281st iterations, respectively. Lastly, more than 10% saving by the conventional and the reinforcement learning-enabled particle swarm algorithm is achieved from 432nd and 28th iterations, respectively.

Keywords

• Reinforcement learning
• Ant colony optimization
• Genetic algorithm
• Particle swarm optimization
• School bus routing and scheduling
• Combinatorial optimization