Parametrisation to reduce solution space

[Hussein-Mahfouz]

The size of the solution space for a city-level bus network is computationally intractable for direct optimization using metaheuristics. Here is some example data:

• routes: 100 (This is close to the number of bus routes in Leeds)
• time of day intervals: 6 (this is specified by the user but 6 gives us [00:00-0400, 0400-08:00, 08:00-12:00 etc]
• discrete headway options: 5 [10min, 15min, 30min, 60min, 120min]

According to the Fundamental Counting Principle, the number of solutions is $5^{100*6}$ (which is $2.4 * 10^{419})$. this is a HUGE number which is impossible to solve exhaustively. Most of these solutions are infeasible (violate constraints), but the algorithm still struggles to search efficiently even after #9, and spends most of its time evaluating illogical schedules.

One solution to reduce solution space is parametrisation. The idea of parametrisation is to reduce the number of dimensions; instead of having the algorithm optimise 600 independant variables, we will have to optimise a small number of parameters that generate a full schedule. Here are 3 different ways to do this:

1) Route classification

This approach classifies routes into distinct groups and then assigns a pre-defined daily headway pattern to each group.

Workflow

1. Preprocessing: Run an initial MATSim simulation with a baseline schedule to gather demand data.
2. Clustering: Use a clustering algorithm (e.g., k-means) to group the 100 routes into a small number of clusters (e.g., 5) based on their 24-hour demand profiles. Example clusters could be:
   - High demand all day
   - Strong AM/PM peak
   - Strong PM peak only
   - Low demand all day
3. Define Headway Patterns: Create a list of plausible, pre-defined 24-hour headway patterns (e.g., 10 unique patterns). A pattern is a list of 6 headways, one for each time interval. For example, Pattern_A = [120, 15, 10, 15, 10, 60].
4. Optimisation: The genetic algorithm's task is to find the optimal assignment of one headway pattern to each route cluster.

Dimension reduction:

• Decisions: 5 (one for each route cluster)
• Choices: 10 (the unique headway patterns)
• Solution Space: $10^5$ = 100,000 solutions. (Down from $5^{600}$)

Pros & Cons:

• Pros: Massive reduction in search space. Ensures schedules are logical.
• Cons: Rigid. The pre-defined patterns might not be optimal. The quality of the solution depends heavily on the quality of the initial clustering and pattern design.

2) Time of day ratios

This approach has the optimizer set a single peak headway for each route, with other periods being calculated using fixed multipliers

Workflow:

1. Preprocessing: Define which time intervals are "peak", "off-peak", etc., and set fixed multipliers (e.g., off_peak_multiplier = 1.5, night_multiplier = 3.0).
2. Optimisation: The algorithm decides on one base headway (e.g., the peak headway) for each of the 100 routes.
3. Mapping: A script calculates the full 6-interval schedule for each route by applying the fixed multipliers to its assigned base headway. Let's say assigned peak headwy is 15min, the offpeak headway could be peak value * 1.5, the super off peak would be peak value * 2 etc. The objective function can then be calculated based on a full schedule

An optional addition to make it less rigid would be to define more than one set of multipliers

Dimensionality Reduction:

• Decisions: 100 (one per route)
• Choices: 5 (the headway options)
• Solution Space: $5^{100}$. Still very large, but a huge improvement over $5^{600}$

Pros & Cons:

• Pros: More flexible than Option 1, as each route gets a custom base headway.
• Cons: Assumes all routes have a similar daily demand shape (e.g., the peak is at the same time and the off-peak relationship is the same), which is a major simplification.

3) Hybrid approach

This approach combines the strengths of the first two. We classify routes, and then for each cluster, we design a schedule by combining a base pattern with a multiplier pattern. This allows for more flexibility than selecting a single pattern (Option 1) and applying one global multiplication rule (Option 2).

Workflow:

1. Preprocessing:
   • Classify routes (e.g., 5 clusters) as in Option 1.
   • Define a list of base Headway Patterns (e.g., Pattern A = [120, 15, 10, 15, 10, 60]).
   • Define a list of Multiplier Patterns (e.g., Multiplier X = [1, 1, 1, 1, 1, 1], Multiplier Y = [2, 1, 1.5, 1, 1.5, 2]).
2. Optimisation: The algorithm's decision for each route cluster is a pair of choices: one base headway pattern and one multiplier pattern
3. Mapping: A script generates the final schedule for a cluster by performing an element-wise multiplication of the chosen base pattern and multiplier pattern.

Dimensionality Reduction:

• Decisions: The number of decisions is equal to the number of route clusters (e.g., 5 clusters).
• Choices: For each cluster, the total number of unique schedules that can be generated is the number of base headway patterns multiplied by the number of multiplier patterns. If we assume 5 base headway patterns and 3 multiplier patterns, then total choices per cluster = 5 × 3 = 15.
• Solution Space = $(15)^5$ ≈760,000.

[Hussein-Mahfouz]

Option 2 may be best bet, as it reduces dimensionality but not by too much. Relevant paper: https://link.springer.com/article/10.1007/s10489-014-0613-2