Optimisation of Bus Timetables using Adaptive Large Neighborhood Search (ALNS)

This presentation introduces a novel matheuristic approach combining Adaptive Large Neighborhood Search (ALNS) with mixed-integer programming to solve large-scale bus schedule optimization problems.

Authors: Mr. Robin Gaborit (Technical University of Denmark) and Dr. Yu Jiang (Lancaster University)

Problem Statement

The Bus Timetabling Problem: Transfer waiting times significantly impact passenger experience. The challenge is to set departure/arrival times for buses to minimize weighted passenger travel times while satisfying operational constraints.

Model Components

• Decision Variables: Departure times from each stop for each bus
• Constraints:
  • Minimum and maximum headways between consecutive buses
  • Minimum and maximum dwell times at stops
  • Travel time consistency across the network
• Objective: Minimize weighted passenger travel times

Methodology: ALNS + MILP

Large Neighborhood Search Principles

• Metaheuristic with iterative improvements
• Destroy then Repair: Partial solution destruction followed by reconstruction

Key Innovation: MILP Repair Operator

• Uses Mixed-Integer Linear Programming solver for repair
• Guarantees feasible solutions (unlike heuristic repairs)
• Acts as solving a restricted optimization problem

The Inverse-Square Rule

Problem with Standard ALNS: When operators have vastly different computation times, standard probability weighting (proportional to score) wastes time on slow operators.

Solution: Weight operators by $p_i = \frac{s_i / t_i^2}{\sum_k s_k / t_k^2}$ where:

• $s_i$ = quality score
• $t_i$ = computation time

This ensures time allocation is proportional to efficiency ($s/t$), not just quality.

Results

Inverse-Square Rule Performance

• Small instances: 0.3% - 0.6% improvement vs standard ALNS
• Medium instances: 0.6% - 0.8% improvement
• Large instances: 0.7% - 1.8% improvement

Synergy: MILP + Heuristic Operators

Combining both operator types significantly outperforms using either alone:

• Small: 4.5% - 6.6% better than heuristic-only
• Medium: 7.0% - 8.1% better than heuristic-only
• Large: 2.9% - 4.1% better than heuristic-only

Conclusions

1. Identified Issue: Standard ALNS struggles with mixed operator speeds
2. Inverse-Square Rule: Correctly allocates computational time
3. Synergy: MILP and heuristic operators are highly complementary