A partial evaluation approach for the School Bus Routing Problem

Area of Science:

• Operations Research
• Computer Science
• Transportation Logistics

Background:

• Exact algorithms for complex optimization problems like the School Bus Routing Problem (SBRP) are often computationally expensive.
• Metaheuristics offer a practical alternative for generating high-quality solutions in a reasonable timeframe.
• Current metaheuristic approaches can be inefficient due to redundant re-evaluation of unchanged solution components.

Purpose of the Study:

• To introduce and apply the partial evaluation technique to the School Bus Routing Problem (SBRP).
• To reduce the computational cost and execution time of metaheuristic algorithms applied to SBRP.
• To investigate the novelty of applying partial evaluation to SBRP within existing literature.

Main Methods:

• Implemented a partial evaluation approach tailored for the SBRP.
• Modified solutions to store information about changes from their predecessors.
• Focused objective function evaluations on only the modified routes within each solution.

Main Results:

• Successfully reduced execution time for SBRP instances using the partial evaluation technique.
• Achieved a decrease in execution time for 80% of the tested instances.
• Demonstrated an average reduction in execution time of 73.6% across instances.

Conclusions:

• Partial evaluation is an effective technique for optimizing metaheuristic solutions for the School Bus Routing Problem.
• The application of partial evaluation significantly enhances the efficiency of solving SBRP instances.
• This research presents a novel contribution by applying partial evaluation to the SBRP domain.