●  How to use · Routing & Logistics

Pickup & delivery (PDPTW)

Each request is a pickup and a drop-off served by the same vehicle, pickup first, without ever exceeding capacity in between.

What it decides

For every request, the solver picks one vehicle and the positions of its pickup and its dropoff on that route, or leaves the whole request unrouted.

Minimal example

from optimaru.pickup_delivery.models import (
    DeliveryModel, PdpInput, PdpRequest, StopModel, VehicleModel, solve_request,
)

request = PdpRequest(
    timelimit=2,
    random_seed=42,
    model_input=PdpInput(
        vehicles=[
            VehicleModel(id="V1", capacity=10, home=(37.5665, 126.9780), departure_time=8 * 3600),
        ],
        deliveries=[
            DeliveryModel(
                id="R1", demand=6,
                pickup=StopModel(id="R1-P", location=(37.5700, 126.9820), service_duration=300),
                dropoff=StopModel(id="R1-D", location=(37.5512, 126.9882), service_duration=300),
            ),
            DeliveryModel(
                id="R2", demand=6,
                pickup=StopModel(id="R2-P", location=(37.5133, 127.1001), service_duration=300),
                dropoff=StopModel(id="R2-D", location=(37.5219, 127.0411), service_duration=300),
            ),
        ],
    ),
)

solution = solve_request(request)
print(solution.feasible, solution.score)
for vehicle_id, stops in solution.routes.items():
    print(vehicle_id, [(stop.stop_id, stop.pickup, stop.arrival_time) for stop in stops])
print(solution.unassigned, solution.vehicle_metrics["V1"].peak_load)

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

Input parameters

VehicleModel

Field Meaning
id required Vehicle id. capacity required Most load on board at any moment. home 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 home. Off by default. max_stops Most pickup and dropoff stops; a request counts as two. 20 by default, 0 lifts the cap. 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. 0 means no limit. max_route_radius_meters Farthest a stop may be from home, in straight-line meters. 0 means no limit. min_load_ratio Target delivered demand on a used vehicle, as a share of capacity. fixed_cost Cost of using this vehicle at all. initial_route Stop ids the route starts from. Both stops of a request must be there or both absent. pinned_stops How many leading stops of initial_route cannot change.

StopModel

Field Meaning
id required Stop id. location required Where the stop is, as (latitude, longitude). min_start_time Time window opens, in seconds from day start. max_end_time Time window closes, in seconds from day start. service_duration Seconds spent at the stop.

DeliveryModel

Field Meaning
id required Request id. demand required Load carried from pickup to dropoff. pickup required The pickup StopModel. dropoff required The dropoff StopModel. required_vehicle Vehicle the request must ride on. Its place on the route stays free. order_time When the request was placed. Negative if it has already been waiting. Only squared_order_age_cost reads it.

PdpInput

Field Meaning
vehicles required The fleet. deliveries required The transport requests. driving_seconds Optional driving-time matrix.

PdpRequest

Field Meaning
model_input required The PdpInput.

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 (53)

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.0 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 0.8 Probability of using that bias.
driving_time_nearby_size 20 Neighbours kept per stop.
first_fit_decreasing True Place the tightest windows and largest demands first. False keeps input order.
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.
late_acceptance_size 0 Late-acceptance history length. 0 picks it from the instance size.
list_swap_move_weight 0.1 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.3 Relative share of Or-opt moves, which relocate a short segment. 0 disables them.
pair_assignment_probability 0.1 Share of pair moves that drop a request or pull one back.
pair_construction_heuristic True Build the start one complete request at a time.
pair_exchange_min_nodes 300 Smallest instance, in stops, that uses them. 0 forces them at every size.
pair_exchange_moves True Enable moves that exchange whole requests.
pair_moves True Enable moves that treat a pickup and its dropoff as one.
pair_repair_probability 0.7 Share of pair moves spent repairing a broken request.
pair_ruin True Ruin whole requests, not single stops.
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.15 Relative share of relocate moves. 0 disables them.
route_elimination_max_size 12 Largest route that move empties.
route_elimination_weight 0.0 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 True 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.0 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.4 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 [3.0, 2.0, 1.0, 0.5] 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.35 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 PdpSolution. The decisions are in routes and unassigned.

PdpSolution

Field Meaning
routes required Vehicle id to its ordered stops. Each stop has stop_id, delivery_id, pickup and arrival_time. unassigned Requests left unrouted. score required Score as text, with hard, medium and soft levels. feasible required True when no hard constraint is broken. total_driving_seconds required Driving time across all routes. vehicle_metrics Per-vehicle stops, requests, peak_load, delivered demand, times and route end. Reported only, never scored.

Constraints

Pick them by calling their classes from optimaru.pickup_delivery.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.pickup_delivery.constraints import (
    PairedRequestCost, PickupBeforeDropoffCost, SameVehicleCost, TravelTimeCost,
    UnassignedRequestsCost, VehicleCapacityCost, get_constraints,
)

picked = get_constraints([
    PairedRequestCost(), SameVehicleCost(), PickupBeforeDropoffCost(), UnassignedRequestsCost(),
    VehicleCapacityCost(), TravelTimeCost(weight=10),
])
print(solve_request(request, constraints=picked).score)
Name Level Default weight What it does
vehicle_capacity_cost Hard 1 Running load above capacity. Load rises at a pickup and falls at its dropoff, so what must fit is the peak, not the route total.
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 Stops above max_stops; a request counts as two.
max_route_radius_cost Hard 1 Meters by which the farthest stop is beyond max_route_radius_meters from home.
enclosing_circle_radius_cost Soft 0 Radius of the smallest circle around a route's stops, home excluded. Weight 0 by default, so give it a weight to use it.
min_capacity_utilization_cost Soft 1 Shortfall of a used vehicle's delivered demand below the min_load_ratio target.
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 stop. Weight 0 by default, so give it a weight to use it.
squared_order_age_cost Soft 0 Squared seconds from each request's order_time to the end of its dropoff. 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.
pinned_stops_cost Hard 1e12 A route must start with its vehicle's pinned stops, in order. Each misplaced stop counts once.
required_vehicle_cost Hard 1000 A request off its required_vehicle: once when unassigned, twice on another vehicle, so a request with no place on its vehicle waits.
paired_request_cost Hard 1000 A request with only one of its pickup and dropoff routed.
same_vehicle_cost Hard 1000 A request whose pickup and dropoff ride on different vehicles.
pickup_before_dropoff_cost Hard 1000 A request whose dropoff comes before its pickup on the route.
unassigned_requests_cost Medium 1 Service minutes of requests with neither stop routed.

How constraints work →

Starting from an existing solution

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

with_initial_solution(request, solution) turns a solution into the initial_route of each vehicle, replacing the ones the request had.

This continues the minimal example above.

from optimaru.pickup_delivery.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 requests it leaves out are constructed.
  • Requests 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.
  • A vehicle's pinned_stops stay as the request has them: its route in the solution must start with them, or ValueError is raised.
  • An unknown id, a stop routed twice, or a request whose pickup and dropoff are apart also raises ValueError, so a hard-infeasible result with a broken pair cannot be used as a start.

Exceptions and limits

  • max_stops is 20 on VehicleModel unless you change it. Pass 0 to lift the cap.
  • Routes are open by default: without return_to_depot, the leg back home is neither driven nor timed.
  • Goods already on board have no pickup left. Give them a pickup at the vehicle's position with no service time, and pin it with pinned_stops.
  • Pinning a pickup keeps its request on the vehicle. Stops after the pinned ones can be reordered, moved to another vehicle or have stops inserted between.
  • required_vehicle keeps a request on a vehicle without fixing its place, for work that is promised but can still be reordered.
  • 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.