composing zero cost abstractions in route optimization

composing

zero cost

abstractions

in route optimization

Uğur Arıkan

RUST FORGE, 27-30 August 2025, Wellington

composing

zero cost

abstractions

in route optimization

composing

zero cost

abstractions

in route optimization

the domain

Traveling Salesperson Problem (TSP)

composing

zero cost

abstractions

in route optimization

the domain

Traveling Salesperson Problem (TSP)
- capacitated
- with time windows
- with precedence relations
- with pickup and delivery
- with grouped visits
- ...

composing

zero cost

performance

monomorphization

abstractions

in route optimization

the domain

speed as a requirement

N of tour requests within a few hours
each request to be handled within M seconds
each request requires communication among
- mobile devices
- databases
- street routing service
- etc.
1 second for the algorithm

composing

zero cost

performance

monomorphization

abstractions

in route optimization

the domain

speed as a requirement

N of tour requests within a few hours
each request to be handled within M seconds
each request requires communication among
- mobile devices
- databases
- street routing service
- etc.
1 second for the algorithm

speed as a quality feature

we often cannot prove global optimality

⇩

the more we search, the better the solution gets

⇩

the faster we search, the better the solution gets

composing

zero cost

performance

monomorphization

abstractions

problem variants

extensibility

in route optimization

the domain

problem variants

just minimize tour duration
go to delivery location only after pickup
visit location X before Y
cannot visit location X in the morning
visit locations X, Y and Z together
do not exceed vehicle capacity
might use a trailer to double capacity
open: new variants to come

composing

zero cost

performance

monomorphization

abstractions

problem variants

extensibility

in route optimization

the domain

problem variants

just minimize tour duration
go to delivery location only after pickup
visit location X before Y
cannot visit location X in the morning
visit locations X, Y and Z together
do not exceed vehicle capacity
might use a trailer to double capacity
open: new variants to come

variants as criteria

treat each consideration as a criterion

common: solution is a tour
different: objectives

C: set of all criteria

X ⊆ C: subset of criteria defining a specific problem variant

composing

maintainability

productivity

zero cost

performance

monomorphization

abstractions

problem variants

extensibility

in route optimization

the domain

composing criteria

provided that we can solve:

variant with criterion a ⊆ C, and
variant with criterion b ⊆ C

can we also solve

for criteria X = {a, b}?

variants as criteria

treat each consideration as a criterion

common: solution is a tour
different: objectives

C: set of all criteria

X ⊆ C: subset of criteria defining a specific problem variant

Local Search

Solution: a tour

⇨ 0-1-2-3-4-5

Local Search

Solution: a tour

⇨ 0-1-2-3-4-5

Local Search

Solution: a tour

⇨ 0-1-2-3-4-5

Neighbor: a similar tour

⇨ 0-5-2-3-4-1

Local Search

local optimum

Local Search


							fn best_neighbor(tour: &Tour, cost: u64) -> Option<(Tour, u64)> {         // INNER LOOP
								let (mut best, mut cost) = (None, cost);
								for neighbor in feasible_neighbors_of(tour) { // not red
									if tour_cost(&neighbor) < cost {
										best = Some(neighbor);
										cost = tour_cost(&neighbor);
									}
								}
								best.map(|best| (best, cost))
							}


							fn local_search(initial_tour: Tour) -> Tour {                              // OUTER LOOP
								let (mut best, mut best_cost) = (initial_tour, tour_cost(&initial_tour));
								while let Some((neighbor, cost)) = best_neighbor(&tour, cost) {
									tour = neighbor;
									best_cost = cost;
								}
								tour
							}

Neighborhoods ≡ Moves

Solution: a tour

⇨ 0-1-2-3-4-5

Neighbor: a similar tour

⇨ 0-5-2-3-4-1

Neighborhoods ≡ Moves

Solution: a tour

⇨ 0-1-2-3-4-5

Move: instructions to move to a neighbor

move city 5 to position 1

Neighborhoods ≡ Moves


						struct Tour { /**/ } // sequence of locations: 0-2-1-4-3

						struct Move { /**/ } // instructions to move to a particular neighbor

						impl Move {
							// takes the tour to the particular neighbor
							fn apply(&self, tour: &mut Tour) { /**/ }
						}

Solution: a tour

⇨ 0-1-2-3-4-5

Move: instructions to move to a neighbor

move city 5 to position 1

Explicit Implementation

Duration

minimize the total tour duration

keep duration within allowed limit

...

TimeWindows

minimize lateness of visits

minimize waiting time due to arriving early

...

Input

Duration


								struct DurationMatrix {
									// data required to evaluate a tour
									// wrt Duration criterion
									// 
									// might be point-to-point duration computed
									// via street routing

									
									/*fields*/
								}


								// eg: a 4✕4 matrix
								[
									[0, 3, 2, 1],
									[7, 0, 1, 5],
									[2, 4, 0, 3],
									[5, 1, 8, 0],
								]

TimeWindows


								struct AvailableTimeSlots {
									// data required to evaluate a tour
									// wrt TimeWindows criterion
									// 
									// might be a map of location to
									// time slots that we can visit
									// the corresponding location
									
									/*fields*/
								}


								// eg: map of locations to available time slots
								{
									0 🡒 [{from: 10:00, to: 12:00}],
									2 🡒 [
										{from: 9:00, to: 10:00},
										{from: 15:00, to: 17:00}
									],
								}

Tour Cost Evaluation


						(input, tour) -> cost

Duration


								fn tour_cost_duration(
									input: &DurationMatrix,
									tour: &Tour,
								) -> u64 {
									// sum all driving duration between all
									// locations in the tour sequence

									todo!()
								}

TimeWindows


								fn tour_cost_tw(
									input: &AvailableTimeSlots,
									tour: &Tour,
								) -> u64 {
									// compute lateness & earliness of each
									// location, compute sum of penalties

									todo!()
								}

Feasible Moves


						(input, tour) -> moves & neighbor costs

Duration


								fn moves_duration(
									input: &DurationMatrix,
									tour: &Tour,
								) -> impl Iterator<Item = (Move, u64)> {
									// create an iterator that yields
									// all moves that takes the `tour`
									// to all of its neighbors which
									// are feasible wrt Duration criterion

									// the second item of the pair is the
									// tour cost of the neighbor wrt
									// Duration criterion

									todo!()
								}

TimeWindows


								fn moves_tw(
									input: &AvailableTimeSlots,
									tour: &Tour,
								) -> impl Iterator<Item = (Move, u64)> {
									// create an iterator that yields
									// all moves that takes the `tour`
									// to all of its neighbors which
									// are feasible wrt TimeWindows criterion

									// the second item of the pair is the
									// tour cost of the neighbor wrt
									// TimeWindows criterion

									todo!()
								}

Best Move


						(input, tour, tour_cost) -> move to best neighbor with lower cost than tour

Duration


								fn best_move_duration(
									input: &DurationMatrix,
									tour: &Tour,
									cost: u64,
								) -> Option<(Move, u64)> {
									let mut best_cost = cost;
									let mut best_move = None;

									let moves = moves_duration(input, tour);

									for (mv, cost) in moves {
										if cost < best_cost {
											best_move = Some(mv);
											best_cost = cost;
										}
									}

									best_move.map(|mv| (mv, best_cost))
								}

TimeWindows


								fn best_move_tw(
									input: &AvailableTimeSlots,
									tour: &Tour,
									cost: u64,
								) -> Option<(Move, u64)> {
									let mut best_cost = cost;
									let mut best_move = None;

									let moves = moves_tw(input, tour);

									for (mv, cost) in moves {
										if cost < best_cost {
											best_move = Some(mv);
											best_cost = cost;
										}
									}

									best_move.map(|mv| (mv, best_cost))
								}

Local Search


						(input, tour) -> local optimal tour

Duration


								fn local_search_duration(
									input: &DurationMatrix,
									mut tour: Tour,
								) -> Tour {
									let mut cost =
										tour_cost_duration(input, &tour);

									while let Some((mv, neighbor_cost)) =
										best_move_duration(input, &tour, cost)
									{
										mv.apply(&mut tour);
										cost = neighbor_cost;
									}

									tour
								}

TimeWindows


								fn local_search_tw(
									input: &AvailableTimeSlots,
									mut tour: Tour,
								) -> Tour {
									let mut cost =
										tour_cost_tw(input, &tour);

									while let Some((mv, neighbor_cost)) =
										best_move_tw(input, &tour, cost)
									{
										mv.apply(&mut tour);
										cost = neighbor_cost;
									}

									tour
								}

composing criteria

provided that we can solve:

variant with criterion Duration ⊆ C, and
variant with criterion TimeWindows ⊆ C

can we also solve

for criteria {Duration, TimeWindows} ⊆ C?

yes, but ...

Local Search - Duration & Time Windows


						fn tour_cost_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour
						) -> u64 {
							let cost_duration = tour_cost_duration(input_duration, tour);
							let cost_tw = tour_cost_tw(input_tw, tour);
							todo!()
						}

						fn moves_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
						) -> impl Iterator<Item = (Move, u64)> {
							let moves_duration = moves_duration(input_duration, tour);
							let moves_tw = moves_tw(input_tw, tour);
							todo!()
						}

						fn best_move_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
							cost: u64,
						) -> Option<(Move, u64)> {
							let mut best_cost = cost;
							let mut best_move = None;

							for (mv, cost) in moves_duration_tw(input_duration, input_tw, tour) {
								if cost < best_cost {
									(best_cost, best_move) = (cost, Some(mv));
								}
							}

							best_move
						}

						fn local_search_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							mut tour: Tour
						) -> Tour {
							let mut cost = tour_cost_duration_tw(input_duration, input_tw, &tour);

							while let Some((mv, neighbor_cost)) =
								best_move_duration_tw(input_duration, input_tw, &tour, cost)
							{
								mv.apply(&mut tour);
								cost = neighbor_cost;
							}
							
							tour
						}

yes, but not nice

what if we have other use cases for

{Duration, Capacity}
{Capacity, TimeWindows}
{Duration, Capacity, TimeWindows}
...

Local Search - Duration & Time Windows


						fn tour_cost_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour
						) -> u64 {
							let cost_duration = tour_cost_duration(input_duration, tour);
							let cost_tw = tour_cost_tw(input_tw, tour);
							todo!()
						}

						fn moves_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
						) -> impl Iterator<Item = (Move, u64)> {
							let moves_duration = moves_duration(input_duration, tour);
							let moves_tw = moves_tw(input_tw, tour);
							todo!()
						}

						fn best_move_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
							cost: u64,
						) -> Option<(Move, u64)> {
							let mut best_cost = cost;
							let mut best_move = None;

							for (mv, cost) in moves_duration_tw(input_duration, input_tw, tour) {
								if cost < best_cost {
									(best_cost, best_move) = (cost, Some(mv));
								}
							}

							best_move
						}

						fn local_search_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							mut tour: Tour
						) -> Tour {
							let mut cost = tour_cost_duration_tw(input_duration, input_tw, &tour);

							while let Some((mv, neighbor_cost)) =
								best_move_duration_tw(input_duration, input_tw, &tour, cost)
							{
								mv.apply(&mut tour);
								cost = neighbor_cost;
							}
							
							tour
						}

C1. compose inputs

Local Search - Duration & Time Windows


						fn tour_cost_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour
						) -> u64 {
							let cost_duration = tour_cost_duration(input_duration, tour);
							let cost_tw = tour_cost_tw(input_tw, tour);
							todo!()
						}

						fn moves_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
						) -> impl Iterator<Item = (Move, u64)> {
							let moves_duration = moves_duration(input_duration, tour);
							let moves_tw = moves_tw(input_tw, tour);
							todo!()
						}

						fn best_move_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
							cost: u64,
						) -> Option<(Move, u64)> {
							let mut best_cost = cost;
							let mut best_move = None;

							for (mv, cost) in moves_duration_tw(input_duration, input_tw, tour) {
								if cost < best_cost {
									(best_cost, best_move) = (cost, Some(mv));
								}
							}

							best_move
						}

						fn local_search_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							mut tour: Tour
						) -> Tour {
							let mut cost = tour_cost_duration_tw(input_duration, input_tw, &tour);

							while let Some((mv, neighbor_cost)) =
								best_move_duration_tw(input_duration, input_tw, &tour, cost)
							{
								mv.apply(&mut tour);
								cost = neighbor_cost;
							}
							
							tour
						}

C2. compose costs

Local Search - Duration & Time Windows


						fn tour_cost_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour
						) -> u64 {
							let cost_duration = tour_cost_duration(input_duration, tour);
							let cost_tw = tour_cost_tw(input_tw, tour);
							todo!()
						}

						fn moves_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
						) -> impl Iterator<Item = (Move, u64)> {
							let moves_duration = moves_duration(input_duration, tour);
							let moves_tw = moves_tw(input_tw, tour);
							todo!()
						}

						fn best_move_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
							cost: u64,
						) -> Option<(Move, u64)> {
							let mut best_cost = cost;
							let mut best_move = None;

							for (mv, cost) in moves_duration_tw(input_duration, input_tw, tour) {
								if cost < best_cost {
									(best_cost, best_move) = (cost, Some(mv));
								}
							}

							best_move
						}

						fn local_search_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							mut tour: Tour
						) -> Tour {
							let mut cost = tour_cost_duration_tw(input_duration, input_tw, &tour);

							while let Some((mv, neighbor_cost)) =
								best_move_duration_tw(input_duration, input_tw, &tour, cost)
							{
								mv.apply(&mut tour);
								cost = neighbor_cost;
							}
							
							tour
						}

C3. compose moves

Local Search - Duration & Time Windows


						fn tour_cost_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour
						) -> u64 {
							let cost_duration = tour_cost_duration(input_duration, tour);
							let cost_tw = tour_cost_tw(input_tw, tour);
							todo!()
						}

						fn moves_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
						) -> impl Iterator<Item = (Move, u64)> {
							let moves_duration = moves_duration(input_duration, tour);
							let moves_tw = moves_tw(input_tw, tour);
							todo!()
						}

						fn best_move_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
							cost: u64,
						) -> Option<(Move, u64)> {
							let mut best_cost = cost;
							let mut best_move = None;

							for (mv, cost) in moves_duration_tw(input_duration, input_tw, tour) {
								if cost < best_cost {
									(best_cost, best_move) = (cost, Some(mv));
								}
							}

							best_move
						}

						fn local_search_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							mut tour: Tour
						) -> Tour {
							let mut cost = tour_cost_duration_tw(input_duration, input_tw, &tour);

							while let Some((mv, neighbor_cost)) =
								best_move_duration_tw(input_duration, input_tw, &tour, cost)
							{
								mv.apply(&mut tour);
								cost = neighbor_cost;
							}
							
							tour
						}

already generic 🗸

composing criteria

define the Criterion abstraction
define composed criteria
- C1. compose inputs
- C2. compose costs
- C3. compose moves

Abstraction


						trait Criterion {
						}


						struct Duration;
						impl Criterion for Duration { }

						struct TimeWindows;
						impl Criterion for TimeWindows { }

Composition


					struct ComposedCriteria<X1, X2>(X1, X2)
					where
						X1: Criterion,
						X2: Criterion;

					impl<X1, X2> Criterion for ComposedCriteria<X1, X2>
					where
						X1: Criterion,
						X2: Criterion;
					{
					}

C1. compose inputs


							fn tour_cost_duration_tw(
								input_duration: &DurationMatrix,
								input_tw: &AvailableTimeSlots,
								tour: &Tour
							) -> u64 {
								/**/
							}

							fn moves_duration_tw(
								input_duration: &DurationMatrix,
								input_tw: &AvailableTimeSlots,
								tour: &Tour,
							) -> impl Iterator<Item = (Move, u64)> {
								/**/
							}

C1. compose inputs


							fn tour_cost_duration_tw(
								input_duration: &DurationMatrix,
								input_tw: &AvailableTimeSlots,
								tour: &Tour
							) -> u64 {
								/**/
							}

							fn moves_duration_tw(
								input_duration: &DurationMatrix,
								input_tw: &AvailableTimeSlots,
								tour: &Tour,
							) -> impl Iterator<Item = (Move, u64)> {
								/**/
							}


							fn tour_cost<X: Criterion>(
								input: &X::Input,
								tour: &Tour
							) -> u64 {
								/**/
							}


							fn moves<X: Criterion>(
								input: &X::Input,
								tour: &Tour,
							) -> impl Iterator<Item = (Move, u64)> {
								/**/
							}

C1. compose inputs


						trait Criterion {
							type Input;
						}

C1. compose inputs


						trait Criterion {
							type Input;
						}


							impl Criterion for Duration {
								type Input = DurationMatrix;
							}

							impl Criterion for TimeWindows {
								type Input = AvailableTimeSlots;
							}

C1. compose inputs


						trait Criterion {
							type Input;
						}


							impl Criterion for Duration {
								type Input = DurationMatrix;
							}

							impl Criterion for TimeWindows {
								type Input = AvailableTimeSlots;
							}


							impl<X1, X2> Criterion for ComposedCriteria<X1, X2>
							where
								X1: Criterion,
								X2: Criterion;
							{
								type Input = ??;
							}

C1. compose inputs


							trait Criterion {
								type Input;
							}


							impl Criterion for Duration {
								type Input = DurationMatrix;
							}

							impl Criterion for TimeWindows {
								type Input = AvailableTimeSlots;
							}


							impl<X1, X2> Criterion for ComposedCriteria<X1, X2>
							where
								X1: Criterion,
								X2: Criterion;
							{
								type Input = (X1::Input, X2::Input);
							}

tuple

C1. compose inputs

since ComposedCriteria: Criterion

it can recursively compose with itself as many times as we require

C1. compose inputs

Duration
=> DurationMatrix

C1. compose inputs

Duration
=> DurationMatrix

ComposedCriteria<Duration, TimeWindows>
=> (DurationMatrix, AvailableTimeSlots)

C1. compose inputs

Duration
=> DurationMatrix

ComposedCriteria<Duration, TimeWindows>
=> (DurationMatrix, AvailableTimeSlots)

ComposedCriteria<ComposedCriteria<Duration, TimeWindows>, Capacity>
=> ((DurationMatrix, AvailableTimeSlots), CapacityDeltas)

C1. compose inputs

Duration
=> DurationMatrix

ComposedCriteria<Duration, TimeWindows>
=> (DurationMatrix, AvailableTimeSlots)

ComposedCriteria<ComposedCriteria<Duration, TimeWindows>, Capacity>
=> ((DurationMatrix, AvailableTimeSlots), CapacityDeltas)

ComposedCriteria<ComposedCriteria<ComposedCriteria<X1, X2>, X3>, X4>
=> (((X1::Input, X2::Input), X3::Input), X4::Input)

C2. compose costs


						fn tour_cost_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour
						) -> u64 {
							let cost_duration = tour_cost_duration(input_duration, tour);
							let cost_tw = tour_cost_tw(input_tw, tour);
							
							??
						}

C2. compose costs


						fn tour_cost_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour
						) -> u64 {
							let cost_duration = tour_cost_duration(input_duration, tour);
							let cost_tw = tour_cost_tw(input_tw, tour);
							
							cost_duration + cost_tw
						}

addition

C2. compose costs


						fn tour_cost_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour
						) -> u64 {
							let cost_duration = tour_cost_duration(input_duration, tour);
							let cost_tw = tour_cost_tw(input_tw, tour);
							
							cost_duration + cost_tw
						}

addition

actually not that obvious, see multi-objective optimization

but we stick to additive costs here

C2. compose costs


						trait Criterion {
							type Input;

							fn tour_cost(input: &Self::Input, tour: &Tour) -> u64;
						}

C2. compose costs


						trait Criterion {
							type Input;

							fn tour_cost(input: &Self::Input, tour: &Tour) -> u64;
						}


						impl Criterion for Duration {
							type Input = DurationMatrix;

							fn tour_cost(input: &Self::Input, tour: &Tour) -> u64 {
								tour_cost_duration(input, tour)
							}
						}

						impl Criterion for TimeWindows {
							type Input = AvailableTimeSlots;

							fn tour_cost(input: &Self::Input, tour: &Tour) -> u64 {
								tour_cost_tw(input, tour)
							}
						}

C2. compose costs


						trait Criterion {
							type Input;

							fn tour_cost(input: &Self::Input, tour: &Tour) -> u64;
						}


						impl<X1, X2> Criterion for ComposedCriteria<X1, X2>
						where
							X1: Criterion,
							X2: Criterion;
						{
							type Input = (X1::Input, X2::Input);

							fn tour_cost((input1, input2): &Self::Input, tour: &Tour) -> u64 {
								X1::tour_cost(input1, tour) + X2::tour_cost(input2, tour)
							}
						}

C3. compose moves


						fn moves_duration_tw(
							input_duration: &DurationMatrix,
							input_tw: &AvailableTimeSlots,
							tour: &Tour,
						) -> impl Iterator<Item = (Move, u64)> {
							let duration_moves = duration_moves(input_duration, tour);
							let tw_moves = tw_moves(input_tw, tour);

							// ??
						}

C3. compose moves

tour has a fixed neighborhood that can be represented as a set of moves

some of these moves are feasible wrt Duration

and some are feasible wrt TimeWindows

C3. compose moves

tour has a fixed neighborhood that can be represented as a set of moves

some of these moves are feasible wrt Duration

and some are feasible wrt TimeWindows

intersection

⇩

composition is the intersection of the subsets

C3. compose moves

tour has a fixed neighborhood that can be represented as a set of moves

some of these moves are feasible wrt Duration

and some are feasible wrt TimeWindows

intersection

⇩

composition is the intersection of the subsets

challenge: intersect two iterators in linear time

trick: traverse neighbors in a standard order