Back to all cards Back to course

Route Optimization II: Search Space, Brute Force, and Practical Heuristics

Advanced Combinatorial Optimisation
Created by Pavel · 12.03.2026 at 07:54 UTC · 2 completed

For a multi-leg trip, each leg can offer several modalities. If each of L legs has k options, brute-force candidate count is approximately k^L.

Example:
- 3 legs, 2 options each -> 8 full-route combinations,
- 8 legs, 3 options each -> 6561 combinations.

Engineering trade-off:
- brute force gives guaranteed global best if fully enumerated,
- heuristic routing is faster but may miss optimum,
- constraints and tie-break policies should be explicit.

Practical strategies:
- prune impossible branches early,
- keep best-so-far bound,
- use domain constraints (max transfers, max price) to reduce candidates.

University approvals: 0
Tasks
Question 1

If each of 5 legs has 3 modality options, how many full-route combinations exist in exhaustive search?

Hint

Use k^L with k=3, L=5.

Question 2

Code task: implement route combination count.

def route_combo_count(num_legs, options_per_leg):
    # TODO

Submission format: submit a full function definition def route_combo_count(...): ....

Hint

Independent leg choices multiply.

Starter code is prefilled; replace TODO blocks with your solution.
2 test cases will be used for grading
Run checks runtime behavior only. Final correctness is evaluated when you submit.
Question 3

Which strategy most directly reduces brute-force route search without changing objective definition?

Hint

Use constraints to discard impossible candidates early.

Question 4

Code task: implement hard-budget filter.

def keep_affordable(routes, max_price):
    """Each route dict has key 'price_total'."""
    # TODO

Submission format: submit a full function definition def keep_affordable(...): ....

Hint

Use list comprehension.

Starter code is prefilled; replace TODO blocks with your solution.
2 test cases will be used for grading
Run checks runtime behavior only. Final correctness is evaluated when you submit.
Card Info
  • Topic: Combinatorial Optimisation
  • Difficulty: Advanced
  • Completed: 2 users
Creator
Pavel
Pavel