Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem

Area of Science:

• Operations Research
• Combinatorial Optimization
• Transportation Science

Background:

• The school bus routing problem is a complex combinatorial optimization challenge.
• Efficient scheduling is crucial for multi-school systems to meet time window constraints.

Purpose of the Study:

• To develop and evaluate methods for the bi-objective school bus scheduling problem.
• To minimize the number of buses and total travel distance.

Main Methods:

• Developed exact methods using mixed integer programming (MIP) for homogenous and heterogeneous fleets.
• Implemented a two-stage metaheuristic combining simulated annealing and local search.
• Utilized CPLEX solver for MIP models.

Main Results:

• MIP formulations were developed and solved.
• The metaheuristic method demonstrated superior performance compared to state-of-the-art methods.
• The bus type-based MIP formulation reduced model complexity for heterogeneous fleets.

Conclusions:

• The proposed metaheuristic method is highly effective for school bus scheduling.
• This research offers efficient solutions for optimizing school transportation logistics.