Changelog

Copy Markdown View Source

0.8.0

Overtime is reworked. max_overtime — an allowance bolted onto shift_duration — is replaced by an explicit max_duration hard cap, and a new overtime_start adds clock-based overtime for drivers who are contracted until a time of day rather than for a number of hours.

Changed

  • Breaking: max_overtime is replaced by max_duration. The old field was an allowance added to shift_duration to derive the hard cap; max_duration now is the hard cap. To migrate, add the two numbers together:

    # before
Model.add_vehicle_type(model, shift_duration: 480, max_overtime: 60, unit_overtime_cost: 10)
# after
Model.add_vehicle_type(model, shift_duration: 480, max_duration: 540, unit_overtime_cost: 10)

    max_duration defaults to shift_duration, which matches the old max_overtime: 0 default: a route may not run past its nominal shift. Vehicle types that never set max_overtime need no change. Note that this default makes unit_overtime_cost inert on its own — duration-based overtime is only reachable once max_duration is raised above shift_duration. usage-rules.md has a section on the three fields and how they interact.

  • Multi-trip construction now respects max_duration rather than shift_duration. Both places that decide whether another trip fits — LocalSearch's trip-insertion heuristic and the initial solution builder — capped the route at shift_duration, so raising max_duration bought a single-trip route more room but never a multi-trip one. Behaviour is unchanged for vehicle types that leave max_duration at its default, since that default is shift_duration.

  • Breaking: ExVrp.Native.search_route_max_overtime_nif is removed. Use search_route_max_duration_nif/1 for the hard cap or the new search_route_overtime_start_nif/1 for the contracted end of shift. search_route_max_duration_nif/1 is unchanged in name but now reports the value the caller passed rather than shift_duration + max_overtime.

  • ExVrp.solve/2 and solve!/2 are specced as returning ExVrp.IteratedLocalSearch.Result, which is what they have always returned — the specs said ExVrp.Solution and were silenced with @dialyzer {:nowarn_function, ...}. The specs are now correct and the suppressions are gone; dialyzer passes without them.

Documented

  • shift_duration and max_duration both measure elapsed time, not time worked. Route duration runs from route start to route end with idle time included, so neither field expresses "no more than N hours worked per day": a day of two short shifts separated by a long gap breaches an elapsed cap the driver's actual hours would clear. Concretely, a route with 300 units of driving spread across a 900-unit day is infeasible under max_duration: 500. usage-rules.md and the ProblemData docs now say so, and point at Route.duration/1 - Route.wait_duration/1 for measuring worked time after the fact. No behaviour change — this was always true and undocumented.

Added

  • overtime_start on ExVrp.VehicleType — the contracted end of shift, on the same axis as :time_windows. When set, overtime becomes max(0, route_end - overtime_start): a driver contracted until 16:00 who runs 09:00–17:00 has worked an hour of overtime even though the route lasted only the nominal eight. Defaults to :infinity, in which case overtime stays max(0, duration - shift_duration) as before.

  • ExVrp.Native.search_route_overtime_start_nif/1, completing the search-route accessor set alongside search_route_shift_duration_nif/1 and search_route_max_duration_nif/1.

  • Doctests for ExVrp itself, so the moduledoc's end-to-end example is executed rather than asserted. The example's stated result was wrong ([[1, 2], [3]] at distance 8944 for an instance whose optimum is a single route at 68); it now shows real output, and notes that route entries are location indices.

Fixed

  • Local search was blind to overtime cost whenever the hard cap was unbounded. Route::hasDurationCost gates whether CostEvaluator::deltaCost prices the duration and time-warp terms of a move at all. It tested the old max_overtime != 0, whose natural translation (overtime_start being set) drops the duration-based case: with shift_duration: 480, max_duration: :infinity, unit_overtime_cost: 10 it returned false, so every move on that route was evaluated as if overtime were free. It now also accounts for a finite shift_duration.

  • Search-side overtime was wrong when forbidden windows were in play. The search route derived its end time as start + duration - time_warp, but under forbidden windows time_warp carries violation penalties that are not shifts along the timeline. A route with overtime_start: 250 and a forbidden window it had to idle through reported 0 overtime in the search where the final route reported 250. The search now uses the end time from the schedule walk it already performs, and the two agree.

0.7.1

Added

  • usage-rules.md, consumed by usage_rules, so agents working in a consuming project get ExVrp's semantics at request time instead of inferring them. It documents the traps that are invisible from the type specs: location indices being offset by the depot count, capacity dimensions having to match the first vehicle type, :time_windows being the only accepted way to give a vehicle its hours, required: false meaning nothing without a prize, and IteratedLocalSearch.Result.cost/1 being an objective rather than a distance.
  • CHANGELOG.md and usage-rules.md are now shipped in the package and rendered in the docs — the package included neither before.
  • usage-rules.md also covers the cost model (unit_distance_cost, unit_duration_cost, fixed_cost, and the fact that duration is free by default and dwarfs distance once service times are counted), warm-starting via :initial_routes, multi-trip via reload_depots, and :log_label.
  • Doctests. The project had none, so every iex> example in the moduledocs was unverified — which is how two fabricated result values survived in the docs. ExVrp.Client, ExVrp.ClientGroup, ExVrp.Depot, ExVrp.NeighbourhoodParams, ExVrp.PerturbationManager and ExVrp.VehicleType are now executed as doctests (13 in total). Examples that used elided ... output were reshaped into runnable form rather than deleted.

Fixed

  • Solver.solve/2's :max_runtime was documented as seconds. It has always been milliseconds — resolve_max_runtime_ms/1 passes the value straight through — so the docstring's max_runtime: 60.0 example asked for a 60 millisecond solve. ExVrp.solve/2 already documented it correctly; the two now agree, and both point at StoppingCriteria.max_runtime/1 being the one that takes seconds.

  • README quick start printed results the code does not produce. It claimed routes #=> [[1, 2], [3]] and distance #=> 8944; the actual output is [[2, 1, 3]] and 68. The install snippet still pinned ~> 0.4.0, and the prerequisites said Elixir 1.15+ against elixir: "~> 1.18" in mix.exs. The development section now also documents EX_VRP_FORCE_BUILD=1, without which c_src/ edits are silently ignored in favour of a precompiled artifact.

  • Flaky timing tests made load-independent. ExVrp.TimeoutTest, ExVrp.SolveTest, ExVrp.OscillationPreventionTest and ExVrp.PrizeCollectingEdgeCasesTest all asserted on elapsed time, so mix check failed intermittently: running ex_unit alongside dialyzer, credo and reach starves the schedulers, and a 250ms budget reported 892ms while a 1.5s oscillation guard took 3734ms. TimeoutTest had also assumed result.runtime was not a wall-clock measurement; it is, just taken inside the ILS loop.

    The oscillation tests were measuring the wrong thing entirely. Those searches complete their full iteration budget in 10-29ms; oscillation manifests as a search stalling inside an iteration and being cut off by max_runtime after a handful, not as a slow wall clock. They now assert that the iteration budget was completed, which is immune to machine load. The timeout tests assert that the stopping criterion fired — the run ended well short of the default 10_000 iterations — and keep only a loose runtime ceiling to catch a criterion that is ignored outright. All timing-sensitive solves also pin num_starts: 1 so one chain's budget is what is being measured.

    SolveTest additionally passed max_runtime: 0.001, a float left over from the seconds assumption, where solve_opts declares pos_integer().

Changed

  • The ExVrp.ABBenchmark.* modules live under dev/ and are not shipped in the package, but were still published to HexDocs. They are now filtered out, which also clears the mix docs warnings about their hidden types.

Known issues

  • ExVrp.Route's trips field is declared on the struct and in its typespec, but ExVrp.Solution.routes/1 never populates it — it is always [], even on a route that made three trips. Use ExVrp.Route.num_trips/1. Documented in usage-rules.md; populating the field is a behavioural change left for a later release.

0.7.0

Fixed

  • solve/2 with num_starts > 1 picked the winning start on the wrong metric. IteratedLocalSearch.Result.cost/1 returned best.distance, while every ILS chain minimises unit_distance_cost × distance + unit_duration_cost × duration + fixed_cost × vehicles + uncollected prizes. Solver.finalize_best/3 ranks starts with that function, so the cross-start winner was chosen on one term of an objective no start had optimised. It now returns the full objective (stats.final_cost), still :infinity when infeasible.

    This is a behavioural change for callers reading Result.cost/1 as a distance — it now equals distance only when unit_duration_cost is 0, no vehicle type sets a fixed_cost, and every client is visited. Measured on a 153-order instance with a fixed vehicle cost: the old rule returned a 7-vehicle plan, the new rule a 6-vehicle plan that was also shorter in duration.

Changed

  • IteratedLocalSearch.Params default max_no_improvement lowered from 50_000 to 800. Upstream PyVRP's 150_000 assumes runs of millions of iterations; a two-minute solve of ~150 locations runs about 10_000, so any threshold in that range left maybe_restart/1 unreachable and a stalled chain simply burned its remaining budget. On the same instance 800 fires 3-6 restarts per start and raises total iterations ~29%. Pass ils_params to override.

  • Per-iteration and per-start setup logging dropped from :info to :debug (ILS iteration, LocalSearch created, Initial solution generated, Total setup time before ILS, Total solve time). An 8-start two-minute solve emitted over a thousand :info lines, burying everything else in the host's log.

Added

  • Parallel solves log one [exvrp start N] candidate: line per finished start (cost, distance, duration, routes, clients, iterations), and Parallel solve complete names the winning start. ILS completed is prefixed with [exvrp start N] so interleaved chains can be told apart. Indices are the original spawn indices and stay stable when a start fails.

  • New :log_label option on solve/2. Start indices only tell chains apart within one solve, so a host running several solves concurrently would see the same [exvrp start 0..3] labels from all of them. log_label: "relaxed_15" namespaces every line of that solve:

    [exvrp relaxed_15 start 2] ILS completed in 4210ms (3180 iterations)
[exvrp relaxed_15 start 2] candidate: cost 977440, distance 252435, ...
[exvrp relaxed_15] Parallel solve complete: 4 starts, ... best from start 2: ...

    Defaults to nil, which keeps the unlabelled format.

0.6.0

Added

  • Exhaustive-on-best polishing in Iterated Local Search (PyVRP #988). When a candidate becomes a new global best, it is now polished with a non-perturbing (exhaustive) local-search pass before being recorded as the best. Controlled by the new exhaustive_on_best field on IteratedLocalSearch.Params (default true). The polished result replaces the candidate only when it is feasible; an infeasible polish falls back to the original candidate.

  • New exhaustive argument on Native.local_search_run/5 (default false), backing the polishing pass. Passing true skips perturbation and runs a pure intensification search, matching PyVRP's exhaustive flag.

Changed

  • IteratedLocalSearch.Params default max_no_improvement restored from an accidental 5_000 to 50_000 (upstream PyVRP uses 150_000).

  • NIF local_search_run_nif arity changed from 4 to 5. This bumps the minor version because the precompiled artifact is version-pinned: consumers must pull the v0.6.0 release binary (or force a local build with EX_VRP_FORCE_BUILD=1) — the v0.5.x artifact exposes the old arity-4 NIF and will fail to load against this release.

0.5.3

Added

  • Warm-start solver via :initial_routes option on ExVrp.solve/2. The outer list position maps to the vehicle type index; each inner list is the sequence of client IDs visited by that vehicle type. Empty inner lists are skipped. Example:

    ExVrp.solve(model, initial_routes: [[1, 2, 3], [], [4, 5]])
# vehicle type 0 → clients 1, 2, 3; vehicle type 2 → clients 4, 5

    Use this when you already have a known-good (or even partially-known) assignment to seed the solver — e.g. inserting new orders into existing routes — instead of cold-starting from an empty solution.

  • New Native.create_solution_from_routes_with_types/2 NIF backing the warm-start path. Takes [{vehicle_type, [client_id, ...]}, ...], unlike the existing create_solution_from_routes/2 which hardcodes vehicle type 0 and is only suitable for homogeneous fleets.

Robustness

  • Warm-start inputs are bounds-checked in the NIF before constructing the C++ Solution: vehicle type indices outside [0, numVehicleTypes()) and client IDs outside [numDepots, numLocations) now raise ArgumentError with a descriptive message instead of segfaulting.
  • ExVrp.solve/2 rescues any ArgumentError/RuntimeError from the warm-start NIF and falls back to an empty-solution start with a warning log. Structurally invalid :initial_routes (duplicate clients, malformed tuples, too many routes for num_available) no longer crash the solve.
  • Capacity-overloaded or time-window-violating warm-starts are passed through to the solver unchanged — these are valid infeasible starting points that the solver can repair via penalties.

0.5.2

Internal

  • Static analysis baseline: zero findings across credo, sobelow, ex_dna, and reach (arch/dead-code/smells/candidates). Wired into mix check and the pre-commit hook; PRs also run mix reach.check --changed.
  • Performance: hot validators in Model and Read switched from Enum.at-in-loop and length checks to Stream.with_index, Enum.sum_by, List.to_tuple + elem/2, and Enum.zip_with.
  • Architecture: ExVrp.Native is now a true PDG leaf (type-erased Model.t() in the @spec) with explicit reach forbidden rules.
  • Safety: replaced String.to_atom/1 in TSPLIB parsing with String.to_existing_atom/1 + rescue.

0.5.1

Added

  • Forbidden time windows in route planning: support for multiple disjunctive feasibility windows on vehicle time, used by the local search to evaluate insertions against reload-time constraints (see test/forbidden_window_test.exs).

Fixed

  • AddressSanitizer / Valgrind setup stabilised across the C++ search code (LocalSearch, Route, Solution, CostEvaluator).

Internal

  • Removed the in-tree credo/append_in_loop.ex custom check (and its test); superseded by upstream tooling.

0.5.0

Breaking Changes

  • VehicleType: replaced tw_early/tw_late/forbidden_windows with time_windows

    The VehicleType API now uses a single :time_windows option (list of {start, end} tuples) instead of separate :tw_early, :tw_late, and :forbidden_windows options.

    # Before
Model.add_vehicle_type(model,
  num_available: 1,
  capacity: [100],
  tw_early: 0,
  tw_late: 28_800
)

# After
Model.add_vehicle_type(model,
  num_available: 1,
  capacity: [100],
  time_windows: [{0, 28_800}]
)

    Multiple disjunctive time windows are now first-class:

    Model.add_vehicle_type(model,
  num_available: 1,
  capacity: [100],
  time_windows: [{0, 500}, {600, 1000}]
)

    When :time_windows is omitted, it defaults to [{0, :infinity}] (no time constraint).

    Passing :tw_early, :tw_late, or :forbidden_windows directly now raises an ArgumentError with a migration hint.

  • Invalid time windows are silently filtered instead of raising. Windows where start >= end are dropped. If all windows are invalid, the vehicle gets tw_early: 0, tw_late: 0 (effectively unusable).