●  How to use · Routing & Logistics

Vehicle routing (VRP)

Assign visits to vehicles and order them into routes, respecting capacities and time windows while minimizing travel.

What it decides

For every visit, the solver picks a vehicle and a position on that vehicle's route. A visit no route can take stays unassigned and costs a medium penalty.

Minimal example

from optimaru.vehicle_routing.models import (
    RoutePlanRequest, RoutingInput, VehicleModel, VisitModel, solve_request,
)

request = RoutePlanRequest(
    timelimit=2,
    random_seed=42,
    model_input=RoutingInput(
        vehicles=[
            VehicleModel(id="V1", capacity=6, depot=(37.5665, 126.9780), departure_time=8 * 3600),
            VehicleModel(id="V2", capacity=6, depot=(37.5665, 126.9780), departure_time=8 * 3600),
        ],
        visits=[
            VisitModel(id="A", location=(37.5700, 126.9820), demand=3, service_duration=600,
                       min_start_time=9 * 3600, max_end_time=12 * 3600),
            VisitModel(id="B", location=(37.5512, 126.9882), demand=3, service_duration=600,
                       min_start_time=9 * 3600, max_end_time=17 * 3600),
            VisitModel(id="C", location=(37.5133, 127.1001), demand=4, service_duration=600),
        ],
    ),
)

solution = solve_request(request)
print(solution.feasible, solution.score, solution.total_driving_seconds)
for vehicle_id, stops in solution.routes.items():
    print(vehicle_id, [(stop.visit_id, stop.arrival_time) for stop in stops])
print(solution.unassigned)

The same use case as a Jupyter notebook, with charts and saved outputs: examples/vehicle-routing.ipynb ↗

Input parameters

VehicleModel

Field Meaning
id required Vehicle id. capacity required Most demand the vehicle can carry. depot required Start point, as (latitude, longitude). departure_time When the vehicle leaves, in seconds from day start. return_to_depot Charge and time the leg back to depot. Off by default, so a route ends at its last stop. max_travel_time Driving-time limit in seconds. 0 means no limit. max_route_duration Route-duration limit in seconds, waits and service included. 0 means no limit. max_end_time Latest time the route may end, in seconds from day start. 0 means no limit. max_stops Most visits on this vehicle. 0 means no limit. max_route_radius_meters Farthest a visit may be from depot, in straight-line meters. 0 means no limit. min_load_ratio Target load ratio for a used vehicle, from 0 to 1. fixed_cost Cost of using this vehicle at all. initial_route Visit ids the route starts from. See the section on existing solutions.

VisitModel

Field Meaning
id required Visit id. location required Where the visit is, as (latitude, longitude). demand Load the visit takes up. min_start_time Time window opens, in seconds from day start. A vehicle arriving early waits. max_end_time Time window closes, in seconds from day start. service_duration Seconds spent at the visit. unassigned_penalty_minutes Penalty if the visit is left unrouted. -1, the default, uses its service minutes.

RoutingInput

Field Meaning
vehicles required The fleet. visits required The visits to serve. driving_seconds Optional driving-time matrix over vehicles, then visits. Without it, times come from straight-line distance.

RoutePlanRequest

Field Meaning
model_input required The RoutingInput.

Solve parameters

What you pass to the solve call. Time limit, seed and parallel count are here.

Parameter Default Meaning
name None Optional label for the request.
timelimit 30.0 Search budget in seconds, from 0 to 1e9.
random_seed 0 Seed for the search.
num_workers 1 Independent parallel starts. The best result wins.
stop_at_first_feasible False Stop as soon as hard 0 is reached.
solver_parameters {} SolverConfig fields by name, as a dict. It cannot set the time limit, seed, worker count or on_new_best.
constraints None Which constraints to score, and how. Left unset, the defaults apply.
All search options (58)

Pass these by name in solver_parameters.

Parameter Default Meaning
acceptor_type LATE_ACCEPTANCE Which rule accepts or rejects a move.
best_score_limit — Stop early once the best score reaches this value. By default it never fires.
blink_rate 0.01 Probability of skipping a candidate placement in repair, so repeated kicks differ. 0 disables it.
descent_max_sweeps 4 Improving passes before giving up on a neighbourhood.
descent_weight 0.03 Share of best-improvement descent. 0 turns it off.
driving_time_nearby True Bias move partners and repair positions toward stops close in driving time.
driving_time_nearby_probability 1.0 Probability of using that bias.
driving_time_nearby_size 25 Neighbours kept per stop.
ejection_chain_candidate_lists 4 Candidate routes per chain step.
ejection_chain_max_evaluations 50000 Score evaluations one chain may spend.
ejection_chain_max_steps 24 Longest ejection chain.
ejection_chain_weight 0.05 Share of ejection-chain moves. 0 turns them off.
first_fit_decreasing True Place the tightest windows and largest demands first. False keeps input order.
granular_descent True Search nearby route pairs with best-improvement moves.
granular_descent_candidate_routes 4 Candidate routes per pass.
granular_descent_max_segment 2 Longest segment moved.
inter_exchange_max_segment 3 Longest segment a CROSS exchange swaps.
inter_exchange_move_weight 0.0 Share of CROSS-exchange moves, which swap a run of stops between two routes. Off by default.
iterated_local_search_max_evaluations 5000000 Evaluation budget of the descent.
iterated_local_search_max_ruin 8 Most visits ruined per move.
iterated_local_search_max_segment 1 Longest segment its descent moves.
iterated_local_search_min_ruin 2 Fewest visits ruined per move.
iterated_local_search_weight 0.05 Share of iterated local search moves. 0 disables them.
late_acceptance_size 0 Late-acceptance history length. 0 picks it from the instance size.
list_swap_move_weight 0.2 Relative share of list swap moves. 0 disables them.
on_new_best None Callback run on each new best solution. If it raises, the solve stops and raises the same exception.
or_opt_move_weight 0.15 Relative share of Or-opt moves, which relocate a short segment. 0 disables them.
parallel_solver_count 1 Independent parallel starts, each with its own seed and the full budget. The best one wins.
random_seed 0 Seed for the search.
record_to_record_end_gap 0.0 The same gap at the end of the search.
record_to_record_start_gap 0.02 With record-to-record acceptance, the gap allowed below the best score at the start, as a fraction of the initial objective.
regret_k 3 Regret-k repair for values of 2 or more. 0 or 1 means plain greedy repair.
relocate_move_weight 0.4 Relative share of relocate moves. 0 disables them.
route_elimination_max_size 12 Largest route that move empties.
route_elimination_weight 0.1 Share of moves that empty the smallest route into the others. 0 turns them off.
route_ruin True Add a ruin operator that empties whole routes.
ruin_recreate False Run adaptive ruin-and-recreate kicks when the search stagnates.
ruin_recreate_as_move_max_ruin 12 Most entities that small ruin removes.
ruin_recreate_as_move_weight 0.05 Probability that a step is a small ruin and repair, judged like any other move. Negative picks it automatically where the use case supports that; 0 turns it off.
ruin_recreate_max_ruin_count 60 Absolute cap on entities removed per kick.
ruin_recreate_max_ruin_fraction 0.3 Largest share of the solution one kick removes.
ruin_recreate_min_ruin_fraction 0.1 Smallest share of the solution one kick removes.
ruin_recreate_operator_decay 0.8 How fast operator weights adapt.
ruin_recreate_polish_steps 5000 Hill-climbing moves that polish each kick. Not counted against step_count_limit.
ruin_recreate_rewards [33.0, 9.0, 3.0, 0.0] Operator rewards for a new best, a better, an accepted and a rejected result.
ruin_recreate_selection_alpha 0.05 Exploration weight for the ALPHA_UCB selection.
ruin_recreate_selection_segment_length 100 Iterations per weight update for the segmented roulette wheel.
ruin_recreate_selection_type ROULETTE_WHEEL How ruin operators are picked.
ruin_recreate_unimproved_step_trigger 5000 Steps without a new best before a kick.
sisr_max_string_removals 3 Most strings one substring removal takes.
sisr_max_string_size 12 Longest string it takes.
sisr_ruin True Add substring removal to the ruin operators.
spent_limit_seconds 30.0 Time budget in seconds, from 0 to 1e9.
step_count_limit 0 Stop after this many steps. 0 means no limit.
tail_swap_move_weight 0.1 Relative share of tail swaps (2-opt*) between two lists. 0 disables them.
two_opt_move_weight 0.15 Relative share of 2-opt moves. 0 disables them.
unimproved_spent_limit_seconds 0.0 Stop after this many seconds without a new best. 0 means no limit.
unimproved_step_count_limit 0 Stop after this many steps without a new best. 0 means no limit.

What comes back

solve_request returns a RouteSolution. The decisions are in routes and unassigned.

RouteSolution

Field Meaning
routes required Vehicle id to its ordered stops. Each stop has visit_id, arrival_time and demand. unassigned Ids of visits on no route. score required Score as text, such as 0hard/0medium/-1078soft. feasible required True when no hard constraint is broken. total_driving_seconds required Driving time across all routes. vehicle_metrics Per-vehicle stops, load, driving, waiting and service times and route end. Reported only, never scored.

Constraints

Pick them by calling their classes from optimaru.vehicle_routing.constraints, such as VehicleCapacityCost(). Only what you pass is scored; pass nothing to keep the defaults. A list may name a constraint more than once, and each pick is scored on its own. Each one takes these parameters:

Parameter Default Meaning
weight None Multiplier on the constraint's cost, in units of the level in effect. Left unset, the default weight below applies. A constraint whose default weight is 0 is off until you give it a weight.
level None "hard", "medium" or "soft" moves the constraint onto that level, as do Level.HARD, Level.MEDIUM and Level.SOFT. Left unset, it keeps the level below. This use case has a medium level, and any constraint may move onto it.
exponent 1.0 Sign-preserving power on the cost, above 0, taken after offset. 2.0 squares it, so concentrated violations cost much more. It applies per unit, such as a vehicle or a day, or to the total of a constraint scored as one sum.
offset 0.0 Subtracted from the cost x before the exponent, per unit or total like the exponent. It is in the cost's own measure: seconds, minutes, a count and so on. Any finite number of either sign, keyword only. clip decides what happens below it.
clip True True makes offset a threshold: only the part beyond it counts, max(0, x - offset) ** exponent, so a cost at or below it adds nothing. False takes the literal (x - offset) ** exponent, sign kept: a unit below the offset counts negative, as a reward, even one whose cost is 0. On a level that counts toward hard, clip=False with a non-zero offset raises ValueError, since hard 0 must mean no violation. Keyword only.

A medium constraint weighs 1 in medium units by default. The search compares solutions on medium * 1e9 + soft, so medium outranks soft while the soft total stays below 1e9. With level, any constraint moves onto any of the three levels: level="medium" puts it on medium, and "hard" or "soft" takes a medium one off it. A weight counts in units of the level in effect.

This continues the minimal example above.

from optimaru.vehicle_routing.constraints import (
    MaxEndTimeCost, TravelTimeCost, UnassignedVisitsCost, VehicleCapacityCost, get_constraints,
)

picked = get_constraints([
    VehicleCapacityCost(),                        # on, as it is
    UnassignedVisitsCost(),                       # on, as it is
    TravelTimeCost(weight=10),                    # reweighted
    MaxEndTimeCost(level="soft"),                 # hard turned into soft
    TravelTimeCost(level="medium", offset=7200),  # picked again: driving beyond 2 h per vehicle, on medium
])
print(solve_request(request, constraints=picked).score)
Name Level Default weight What it does
vehicle_capacity_cost Hard 1 Load above the vehicle's capacity.
max_end_time_cost Hard 1 Minutes, rounded up, by which arrival plus service passes max_end_time.
travel_time_cost Soft 1 Total driving time. The leg back counts only with return_to_depot.
max_travel_time_cost Hard 1 Driving seconds above max_travel_time.
max_route_duration_cost Hard 1 Route seconds above max_route_duration, waits and service included.
vehicle_max_end_time_cost Hard 1 Seconds by which the route ends after max_end_time.
max_stops_cost Hard 1 Visits above max_stops.
max_route_radius_cost Hard 1 Meters by which the farthest visit is beyond max_route_radius_meters from the depot.
enclosing_circle_radius_cost Soft 0 Radius of the smallest circle around a route's visits, depot excluded. Weight 0 by default, so give it a weight to use it.
min_capacity_utilization_cost Soft 1 Shortfall of a used vehicle below min_load_ratio.
route_duration_cost Soft 0 Total route time, waits and service included. Weight 0 by default, so give it a weight to use it.
latency_cost Soft 0 Sum of the times taken to reach each visit. Weight 0 by default, so give it a weight to use it.
vehicle_fixed_cost Soft 1 fixed_cost of every vehicle used at least once.
unassigned_visits_cost Medium 1 Each unrouted visit's unassigned_penalty_minutes.

How constraints work →

Starting from an existing solution

This needs the latest release: pip install -U optimaru.

with_initial_solution(request, solution) returns a new request whose vehicles carry initial_route, a list of visit ids. The request you pass in is not changed.

This continues the minimal example above.

from optimaru.vehicle_routing.models import with_initial_solution

seeded = with_initial_solution(request, solution)  # or solution.model_dump(mode="json")
better = solve_request(seeded)
print(better.score, better.unassigned)
  • A complete solution skips construction: the search starts exactly from it. A partial one keeps what it gives, and only the visits it leaves out are constructed.
  • Visits in unassigned get another try.
  • With timelimit=0 the solve stops at once, so a complete solution comes back as it went in. Use the time limit for this: step_count_limit = 0 means no limit.
  • An unknown id or a visit routed twice raises ValueError.

Exceptions and limits

  • Times are integer seconds from a common day start.
  • Routes are open by default: without return_to_depot, the leg back is neither driven nor timed.
  • Lateness is measured from arrival plus service, so time spent waiting for a window to open does not count.
  • Setting any of max_travel_time, max_route_duration, max_end_time, max_stops, min_load_ratio, fixed_cost or max_route_radius_meters runs the solve with constraint plugins, where num_workers has no effect.