Route Optimization I: Domain Modeling, Constraints, and Local vs Global Decisions

Intermediate Combinatorial Optimisation

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

Case setup:
A route from Winterthur to Kreuzlingen is split into legs. Each leg has several modalities (for example train, taxi, bus), each with cost and duration.

Class model:
- Route(a, b) stores directed leg endpoints,
- Modality(route, name, price, duration) stores one travel option for one leg,
- Router(mods) searches feasible chains from start to finish.

Optimization modes:
- cheapest route (PRICE mode),
- fastest route (DURATION mode).

Why this is a case study:
- object model is simple but realistic,
- constraints are explicit,
- it demonstrates that local leg-optima do not guarantee global optimum.

Edge cases:
- destination unreachable,
- circular route definitions,
- missing modalities for one intermediate node,
- ties in price/duration requiring deterministic tie-break rules.

University approvals: 0

en.wikipedia.org/wiki/Shortest_path_problem

article

en.wikipedia.org

Tasks

Question 1

Why can a route assembled from cheapest option per leg still be suboptimal overall?

Hint

Think path dependency.

Because price is not additive across legs.

Because local decisions can restrict better downstream combinations.

Because routes cannot be represented as objects.

Because greedy methods always fail.

Question 2

Code task: implement modality scoring with weighted objective.

def score_modality(mod, w_price=1.0, w_time=1.0):
    """mod has attributes: price, duration"""
    # TODO

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

Hint

Return w_price * mod.price + w_time * mod.duration.

def score_modality(mod, w_price=1.0, w_time=1.0):
    # TODO: w_price * mod.price + w_time * mod.duration
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

2 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Question 3

What is the most robust behavior when no outgoing modality exists from the current node during search?

Hint

Fail explicitly, do not invent path data.

Pick a random previous modality.

Return a route-not-found result or raise a clear exception.

Assume zero-cost teleportation.

Drop the remaining constraints.

Question 4

Code task: implement one-leg best option selection.

def best_option(opts, mode):
    """mode is 'price' or 'duration'; opts is non-empty list of objects."""
    # TODO

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

Hint

Use min with key depending on mode.

def best_option(opts, mode):
    # TODO: mode is 'price' or 'duration'
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

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: Intermediate
Completed: 2 users

Creator

Pavel