The Inverse-Square Rule: Smarter Algorithms, Better Buses

In the world of public transport, "better buses" usually means one thing: an experience that respects the passenger's time. But creating a schedule that minimizes waiting, transfers, and travel time across a massive city network is a computational nightmare.

To solve this, a recent study, "Adaptive large neighbourhood search (ALNS) based matheuristic to an acyclic bus timetabling problem," introduces a breakthrough concept: The Inverse-Square Rule. This simple yet powerful mathematical tweak transforms how algorithms think, leading to significantly smarter scheduling decisions.

Smarter Algorithms: The "Brain" of the Operation

The core problem in optimizing timetables is balancing speed and precision.

1. Fast Heuristics: Quick fixes that shift times slightly. Good for speed, bad for deep optimization.
2. Exact Solvers (MILP): The "heavy lifters" that find the math-perfect solution but take forever to run.

A truly smart algorithm (a "matheuristic") needs to know when to use which tool. If it overuses the heavy lifter, it freezes. If it ignores it, the schedule stays mediocre.

The Inverse-Square Rule: The Decision Maker

This is where the Inverse-Square Rule acts as the algorithm's conscience.

Instead of choosing tools based solely on past success, the rule weighs the decision by the inverse-square of the computation time.

The Mathematical Foundation

We calculate the selection probability $P_i$ for each operator $i$ as:

$$p_i = \frac{s_i / t_i^2}{\sum_k s_k / t_k^2}$$

Where:

• $s_i$ is the quality score (past performance).
• $t_i$ is the average computation time.

The Logic: It imposes a "tax" on slow methods. A computationally expensive MILP operator is only chosen if its potential payoff is exponentially higher. This makes the algorithm "frugal" with its time, investing in deep optimization only when it really counts.

Better Buses: The Real-World Impact

To validate this approach, the team tested it on realistic scenarios from the Copenhagen bus network. The instances ranged from small (2 hours) to massive (8 hours), with the largest involving millions of variables and constraints—a scale where traditional exact solvers often struggle.

Size	Time Period	Passenger Groups	No. of Runs	Variables	Constraints
Small	8:00 – 10:00	51–60	96	~100,000	~90,000
Medium	8:00 – 12:00	102–120	192	~500,000	~600,000
Large	8:00 – 16:00	204–240	384	~3,000,000	~5,000,000

Results: Outperforming the Industry Standard

The performance gap becomes undeniable when looking at the results (Table 2). The team compared their ALNS algorithm against Gurobi, a state-of-the-art commercial optimization solver.

Instance	S1	S2	S3	M1	M2	M3	L1	L2	L3
ALNS Cost	2,218	1,900	2,431	4,577	3,891	4,939	9,850	8,461	10,802
Improvement	-43%	-45%	-43%	-41%	-44%	-41%	-37%	-38%	-36%
Exact Solver	0.6% gap	0.6% gap	0.7% gap	0.7% gap	Failed	Failed	Failed	Failed	Failed

Finding the "Sweet Spot": Why Square?

You might ask: Why the "inverse-square" rule? Why not just inverse, or inverse-cube?

The researchers performed a sensitivity analysis (Table 5) to test different powers for the penalty function. The results show that the Inverse-Square (power of 2) strikes the perfect balance. It outperforms both "lenient" penalties (like linear weighting) and "harsh" penalties (like cubic weighting).

Formula	Small	Medium	Large	Verdict
No Time Weight	-0.4%	-0.6%	-2.1%	Wastes time on heavy operators.
Inverse Linear (1/t)	-0.2%	-0.4%	-1.7%	Not strict enough.
Inverse Cubic (1/t³)	-5.0%	-5.8%	-2.6%	Too strict; limits power.
Inverse-Square (1/t²)	Baseline	Baseline	Baseline	Optimal Balance

Conclusion

This research highlights a crucial lesson for optimization: it's not just about having powerful tools (like MILP solvers), but knowing when to use them. The inverse-square rule provides a robust mathematical foundation for making that decision, leading to better public transport schedules and happier passengers.