Base and problem¶

Every solver in scikit-route is an estimator: __init__ stores the hyper-parameters (the "knobs"), fit(X, ...) receives the data and returns self, and the results live in trailing-underscore attributes (tour_, route_, trips_, cost_, ...). The contract has three parts:

RoutingProblem — one immutable instance in index space: the coerced cost matrix, the optional time matrix and budget, the depot and the labels. fit builds it for you, or you build it once and pass it to several solvers (Other().fit(est.problem_)).
BaseRouter — the template method: it validates the inputs and the hyper-parameters, honours the solver's RouterTags, calls the solver's _solve(problem, rng), validates the returned tour and recomputes cost_ from it, so a route that does not match its cost is impossible by construction.
RouteEvent — the progress report a solver hands to the callback of fit, so you can watch (or stop) a search while it runs.
the helpers clone, is_router, all_solvers and set_log_level, the exceptions and the public helpers of skroute.metrics: route_cost and split_trips recompute a label-space route, timetable turns a solution into arrival and departure times (one list of Stops per day) and timetable_summary totals every day.

Plain TSP is est.fit(C); the multi-trip objective is est.fit(C, time_matrix=T, max_time_work=8, extra_cost=12.83, people=2) — time_matrix is keyword-only, so the two square matrices can never be swapped by accident.

Service times¶

A visit takes time: fit(..., service_time=0.5) (a scalar for every non-depot node) or service_time=array (one value per node, in matrix row order, the depot's paid once per day at departure) adds it to the budget, in the units of time_matrix (D32). The kernels search on the effective matrix T_eff[i, j] = T[i, j] + service[j] for j != depot, T_eff[i, depot] = T[i, depot] and T_eff[depot, j] += service[depot]; problem_.time stays the raw driving time, problem_.service_time is the (n,) array (zeros when not given), problem_.time_or_cost is T_eff, and trip_times_ includes the visits. A fit with service_time equals, by definition, a fit on T_eff without it; route_cost(..., service_time=) re-prices a route the same way.

>>> import numpy as np
>>> from skroute import BruteForce
>>> from skroute.metrics import timetable
>>> C = np.array([[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]], dtype=float)
>>> hours = np.array([[0, 1, 2, 2], [1, 0, 1, 2], [2, 1, 0, 1], [2, 2, 1, 0]], dtype=float)
>>> bf = BruteForce().fit(C, time_matrix=hours, max_time_work=5.0, extra_cost=3.0, service_time=0.5)
>>> bf.route_.tolist(), bf.trip_times_.tolist(), bf.cost_
([0, 1, 2, 0, 3, 0], [5.0, 4.5], 41.0)
>>> [(s.label, s.arrival_time, s.departure_time) for s in timetable(bf, units="h")[0]]
[(0, '08:00', '08:00'), (1, '09:00', '09:30'), (2, '10:30', '11:00'), (0, '13:00', '13:00')]

Watching a solver work¶

Every fit accepts callback=: any callable taking one RouteEvent. The solver calls it once at "start", once after every outer iteration — exactly where history_ grows, with the tour it is working on, the best tour so far and their costs — and once at "end" with the fitted tour. Return True to stop the search after the current outer iteration (stop_reason_ == "callback"). The tours arrive in label space, depot first, and event.route/event.trips decode the best one with the problem's own split rule, so a multi-trip instance can be drawn trip by trip. Every solver documents the keys of event.extra it fills (the temperature of an annealing level, the kick of an iterated local search, the LP support of a MILP cut round...). Inside a MultiStart the inner solvers report under their own name with extra["restart"], and only when the restarts run sequentially (n_jobs=None or 1 — then in the calling thread, whatever an enclosing joblib.parallel_config says, so the callback never runs in a worker). The callback runs inside the timed search (fit_time_ includes it), and an exception it raises propagates out of fit and leaves the estimator unfitted, at the "end" event as at any other. The skroute.viz package builds live plots and animations on top of this protocol.

>>> import numpy as np
>>> from skroute import SimulatedAnnealing
>>> C = np.array([[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]], dtype=float)
>>> seen = []
>>> sa = SimulatedAnnealing(random_state=0).fit(C, callback=seen.append)
>>> seen[0].stage, seen[0].iteration, seen[-1].stage, seen[-1].iteration == sa.n_iter_
('start', 0, 'end', True)
>>> len(seen) == sa.n_iter_ + 2 and seen[-1].best_cost == sa.cost_
True
>>> sorted(seen[1].extra)
['accepted', 'n_moves', 'temperature']
>>> short = SimulatedAnnealing(random_state=0).fit(C, callback=lambda e: e.iteration >= 5)
>>> short.n_iter_, short.stop_reason_
(5, 'callback')

Partial structures: `edges`, `edge_weights`, `ring`¶

A solver that has no tour yet still has something to show — and three optional extra keys carry it, in a shape every viewer understands (D31); keys a viewer does not know are ignored.

extra["edges"] — a list of (label, label) tuples: the partial structure the solver holds when tour is None or incomplete. The construction heuristics emit one "iteration" event per construction step, with tour=None, cost=nan and best_cost=nan (nan means unknown, not a value): the growing path of NearestNeighbour (n - 1 events), the closed partial cycle of Insertion after each placement (n - 1, the seed included), the current depot -> trip -> depot legs of ClarkeWright before the first merge and after each accepted one (merges + 1, plus extra["n_trips"]), the edge set of NRBS after each connection (n, plus extra["n_edges"]); MILP reports the support of each cut round; AntColony its strongest min(3n, n(n-1)/2) pheromone trails (min(3n, n(n-1)) arcs on an asymmetric matrix, where every arc competes).
extra["edge_weights"] — floats in [0, 1] parallel to extra["edges"]: AntColony's trail strength over the current tau_max, MILP's variable values of the support.
extra["ring"] — an (m, 2) float array: SOM's neuron positions after each epoch, in the units of problem.coords, so the ring can be drawn over the cities.

The traces cost nothing without a callback: the kernels record nothing and the Python side replays nothing. Every event owns its list or array — a recorder that keeps the events keeps the history. A construction solver has no search to stop: a callback returning True only silences its remaining step events (all of them when it answers at "start"), and the result never depends on the callback.

>>> import math
>>> from skroute import NearestNeighbour
>>> trace = []
>>> nn = NearestNeighbour().fit(C, labels=["d", "a", "b", "c"], callback=trace.append)
>>> [e.stage for e in trace]
['start', 'iteration', 'iteration', 'iteration', 'end']
>>> [e.extra["edges"] for e in trace if e.stage == "iteration"]
[[('d', 'a')], [('d', 'a'), ('a', 'b')], [('d', 'a'), ('a', 'b'), ('b', 'c')]]
>>> trace[1].tour is None and math.isnan(trace[1].cost), trace[-1].best_tour.tolist()
(True, ['d', 'a', 'b', 'c'])

RoutingProblem ¶

RoutingProblem(X: Any, *, time_matrix: Any = None, depot: Any = None, coords: Any = None, labels: Any = None, max_time_work: float | None = None, extra_cost: float = 0.0, people: int = 1, service_time: Any = None, split: str = 'greedy')

One instance in index space. Immutable after construction; shareable across solvers and threads.

Parameters:

Name	Type	Description	Default
`X`	`(n, n) array-like, DataFrame or dict-of-dicts`	Cost matrix. Rows are origins, columns destinations. Must be square, n >= 3, all finite.	required
`time_matrix`	`same kinds as X, optional, keyword-only (D7)`	Durations, same shape and labels as X, all finite and >= 0. Required iff max_time_work is given.	`None`
`depot`	`label`	Label of the depot (a position for plain arrays without labels=). Default: first node.	`None`
`coords`	`(n, 2) array-like`	Coordinates in row order of X. Needed by SOM; carried, never validated beyond shape.	`None`
`labels`	`sequence of n hashables`	Labels for a plain ndarray X. Must equal the labels X already carries, if any.	`None`
`max_time_work`	`float > 0`	Per-trip budget in the units of time_matrix. None = plain TSP.	`None`
`extra_cost`	`float >= 0`	Fixed charge per trip beyond the first.	`0.0`
`people`	`int >= 1`	Multiplies extra_cost only.	`1`
`service_time`	`float or (n,) array-like`	Time spent at each node, in the units of `time_matrix` (finite, >= 0). A scalar applies to every non-depot node; an array gives one value per node in matrix row order (the depot's entry is paid once per trip, at departure). A pandas Series is read in row order too, but its index must be the labels of `X`. Requires `max_time_work` (D32). Default: no service time.	`None`
`split`	`('greedy', 'optimal')`	Decoder of the giant tour into trips (see D1).	`"greedy"`

Attributes:

Name	Type	Description
`cost`	`ndarray of shape (n, n), float64, C-contiguous`	The coerced cost matrix.
`time`	`ndarray of shape (n, n) or None`	The coerced raw travel-time matrix; `None` for plain TSP. The kernels read `time_or_cost` instead, which adds the service times.
`service_time`	`ndarray of shape (n,), float64`	Service time of every node in matrix row order; all zeros when not given.
`n`	`int`	Number of nodes.
`labels`	`ndarray of shape (n,), dtype int64 or object`	Label of every node, in matrix row order.
`depot`	`int`	Index of the depot.
`max_time_work`	`float`	The per-trip budget; `inf` for plain TSP.
`extra_cost`	`float`
`people`	`int`
`split`	`{'greedy', 'optimal'}`
`coords`	`ndarray of shape (n, 2) or None`
`symmetric`	`bool`	Whether `cost` equals its transpose.

Notes

The objective (D1) is the travel cost of the decoded trips plus people * extra_cost * (n_trips - 1). Under the greedy decoder a leg a -> b joins the open trip iff the trip can still return to the depot within max_time_work; the optimal decoder (Prins, 2004) is the minimum-cost partition of the giant tour into consecutive feasible trips. Both are O(n) and O(n L) respectively, with L the longest feasible open path.

A service time is folded into the matrix the decoders read (D32): with s the (n,) service array and d the depot, the effective time matrix is T_eff[i, j] = T[i, j] + s[j] for j != d (the service is paid on arrival), T_eff[i, d] = T[i, d] (nothing is paid on returning) and T_eff[d, j] += s[d] for j != d (a service at the depot is paid once per trip, at departure); the diagonal, which no kernel reads, stays raw. time_or_cost returns T_eff, so evaluate, trip_starts and trip_times all account for the services, and fitting with service_time equals fitting on T_eff without it. time keeps the raw travel times for reporting (skroute.metrics.timetable).

The problem never writes to its arrays, but it does not copy a float64, C-contiguous X or time_matrix either — cost and time are then views of the caller's arrays (no second n x n matrix at n = 10 639) — so an array must not be modified after it has been passed. service_time is always copied, and with a non-zero service T_eff is a private matrix: a later write to the caller's time_matrix would move timetable (which reads time) but not trip_times_ (which reads T_eff).

References

.. [1] C. Prins, "A simple and effective evolutionary algorithm for the vehicle routing problem", Computers & Operations Research 31 (2004) 1985-2002.

Examples:

>>> import numpy as np
>>> from skroute import RoutingProblem
>>> C = np.array([[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]], dtype=float)
>>> p = RoutingProblem(C, labels=["d", "a", "b", "c"], depot="d")
>>> p
RoutingProblem(n=4, TSP, symmetric, depot='d')
>>> p.to_index_tour(["d", "a", "b", "c", "d"]).tolist()
[0, 1, 2, 3]
>>> p.evaluate([0, 1, 2, 3])
22.0
>>> hours = np.array([[0, 1, 2, 2], [1, 0, 1, 2], [2, 1, 0, 1], [2, 2, 1, 0]], dtype=float)
>>> q = RoutingProblem(C, time_matrix=hours, max_time_work=4.0, extra_cost=3.0)
>>> q.evaluate([0, 1, 2, 3]), q.trip_starts([0, 1, 2, 3]).tolist()
(41.0, [1, 3, 4])

Half an hour at every customer under a five-hour day: the services are paid on arrival (row 0 of the effective matrix), never on the way back (column 0), and trip_times includes them.

>>> r = RoutingProblem(C, time_matrix=hours, max_time_work=5.0, extra_cost=3.0, service_time=0.5)
>>> r.service_time.tolist()
[0.0, 0.5, 0.5, 0.5]
>>> r.time_or_cost[0].tolist(), r.time_or_cost[:, 0].tolist()
([0.0, 1.5, 2.5, 2.5], [0.0, 1.0, 2.0, 2.0])
>>> starts = r.trip_starts([0, 1, 2, 3])
>>> starts.tolist(), r.trip_times([0, 1, 2, 3], starts).tolist(), r.evaluate([0, 1, 2, 3])
([1, 3, 4], [5.0, 4.5], 41.0)

multi_trip `property` ¶

multi_trip: bool

Whether a time matrix and a budget were given.

fixed_cost `property` ¶

fixed_cost: float

extra_cost * people: the charge per trip beyond the first.

time_or_cost `property` ¶

time_or_cost: ndarray

The matrix kernels receive as T: the effective time matrix, or the cost matrix if no budget.

The effective matrix is time plus the service times (D32, see the class notes): it is time when no service was given. Without a budget (max_time_work == inf) the kernels never read T; passing the cost matrix keeps every call signature uniform.

split_code `property` ¶

split_code: int

Integer code of the split rule, as the core's SplitRule enum.

depot_label `property` ¶

depot_label: Any

The depot's label.

index_of ¶

index_of(label: Any) -> int

Index of label in matrix row order; ValueError if it is not a label of X.

to_index_tour ¶

to_index_tour(seq: Any) -> ndarray

Labels -> int64 tour with the depot at position 0.

Accepts an open tour (n labels), a closed route (depot repeated at the end) or a multi-trip route (depot repeated between trips): every occurrence of the depot is removed, then the depot is prepended. Raises ValueError unless the remaining labels are exactly the non-depot labels, each once.

to_label_tour ¶

to_label_tour(tour: Any) -> ndarray

Index tour -> label array (same length, label dtype).

evaluate ¶

evaluate(tour: Any) -> float

Objective of an index tour (D1). O(n) greedy / plain, O(n*L) optimal.

trip_starts ¶

trip_starts(tour: Any) -> ndarray

Trip start positions of an index tour.

Returns an int64 array of shape (n_trips + 1,) with starts[0] == 1 and starts[-1] == n; trip k is tour[starts[k]:starts[k + 1]]. Plain TSP gives [1, n].

trip_costs ¶

trip_costs(tour: Any, starts: Any) -> ndarray

Travel cost of each closed trip (fixed charge excluded), float64 (n_trips,).

trip_times ¶

trip_times(tour: Any, starts: Any) -> ndarray

Duration of each closed trip, float64 (n_trips,), services included. Requires a time matrix.

neighbours ¶

neighbours(k: int = 10) -> ndarray

k nearest neighbours of every node by C[i, :], as int64 (n, k), sorted ascending; cached.

The diagonal is excluded regardless of its value (only finiteness is required of it) and ties are broken by node index (stable sort). Six bundled instances have coincident points (lu980: 346 duplicate rows, ho14473: 7 370), so zero off-diagonal distances are normal input.

BaseRouter ¶

Base class of every solver.

Subclasses: store every __init__ argument verbatim as an attribute of the same name and nothing else; declare _parameter_constraints; override _get_tags(); implement _solve(problem, rng) -> int64 array (a permutation of range(n) with problem.depot first). Iterative solvers set self.history_, self.n_iter_, self.stop_reason_ inside _solve; exact solvers set self.is_optimal_. Everything else is set here.

Attributes:

Name	Type	Description
`problem_`	`RoutingProblem`	The coerced instance (reusable: `Other().fit(est.problem_)`).
`n_nodes_`	`int`	Number of nodes.
`labels_`	`ndarray of shape (n,), label dtype`	Labels in matrix row order.
`depot_`	`scalar, label dtype`	The depot's label.
`tour_`	`ndarray of shape (n,), label dtype`	Open giant tour, depot first — the warm-start format (`init=`).
`route_`	`ndarray of shape (n + n_trips,), label dtype`	As driven: depot, trip 1, depot, trip 2, ..., depot.
`trips_`	`list of ndarray`	One closed `[depot, ..., depot]` array per trip; `len == 1` for plain TSP.
`n_trips_`	`int`	`len(trips_)`.
`trip_costs_`	`ndarray of shape (n_trips,), float64`	Travel cost of each closed trip (fixed charge excluded).
`trip_times_`	`ndarray of shape (n_trips,), float64`	Only when a time matrix was given; each `<= max_time_work + 1e-9`, service times included.
`cost_`	`float`	`trip_costs_.sum() + fixed_cost * (n_trips_ - 1)`, recomputed from the tour (D2).
`fit_time_`	`float`	Seconds spent in `_solve` — including the time taken by the `callback` of `fit`, which runs inside it (a live plot redrawn at every iteration inflates it; time a solver without a callback).
`history_`	`ndarray of shape (n_iter_,), float64`	Iterative solvers only: best-so-far cost after each outer iteration.
`n_iter_`	`int`	Iterative solvers only: outer iterations actually run.
`stop_reason_`	`str`	Iterative solvers only: `"converged" \| "max_iter" \| "patience" \| "time_limit" \| "callback"` — the last one when the `callback` of `fit` returned `True` (D30).
`is_optimal_`	`bool`	Exact solvers only.

Notes

fit never trusts a cost reported by the solver: the returned index tour is validated (a permutation with the depot first, else RuntimeError) and cost_ is recomputed with the problem's own decoder, so a route that does not match its cost is impossible by construction.

Examples:

>>> import numpy as np
>>> from skroute.base import BaseRouter, RouterTags
>>> class Identity(BaseRouter):
...     '''Returns the nodes in matrix order.'''
...
...     def __init__(self, verbose=0):
...         self.verbose = verbose
...
...     def _get_tags(self):
...         return RouterTags(kind="construction")
...
...     def _solve(self, problem, rng):
...         return np.arange(problem.n)
>>> C = np.array([[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]], dtype=float)
>>> est = Identity().fit(C)
>>> est.tour_.tolist(), est.route_.tolist(), est.cost_, est.n_trips_
([0, 1, 2, 3], [0, 1, 2, 3, 0], 22.0, 1)
>>> est
Identity()
>>> Identity(verbose=1)
Identity(verbose=1)

get_params ¶

get_params(deep: bool = True) -> dict[str, Any]

Parameters of this estimator.

Parameters:

Name	Type	Description	Default
`deep`	`bool`	If True, also return the parameters of nested estimators as `<name>__<param>`.	`True`

Returns:

Name	Type	Description
`params`	`dict`	Parameter names mapped to their values.

set_params ¶

set_params(**params: Any) -> BaseRouter

Set the parameters of this estimator (<name>__<param> reaches nested estimators).

Returns:

Type	Description
`self`

fit ¶

fit(X: Any, *, time_matrix: Any = None, depot: Any = None, coords: Any = None, labels: Any = None, max_time_work: float | None = None, extra_cost: float = 0.0, people: int = 1, service_time: Any = None, split: str = 'greedy', callback: Callable[[RouteEvent], Any] | None = None) -> BaseRouter

Solve the instance and store the result in trailing-underscore attributes.

Parameters:

Name	Type	Description	Default
`X`	`(n, n) array-like, DataFrame, dict-of-dicts or RoutingProblem`	Cost matrix (rows are origins). A ready `RoutingProblem` must be passed alone (`callback` is not a problem argument and may accompany it).	required
`time_matrix`	`same kinds as X, optional, keyword-only`	Durations; required iff `max_time_work` is given.	`None`
`depot`	`label`	Label of the depot. Default: the first node.	`None`
`coords`	`(n, 2) array-like`	Node coordinates in row order (needed by `SOM`).	`None`
`labels`	`sequence of n hashables`	Labels for a plain ndarray `X`.	`None`
`max_time_work`	`float > 0`	Per-trip budget in the units of `time_matrix`; `None` = plain TSP.	`None`
`extra_cost`	`float >= 0`	Fixed charge per trip beyond the first.	`0.0`
`people`	`int >= 1`	Multiplies `extra_cost` only.	`1`
`service_time`	`float or (n,) array-like`	Time spent at each stop, in the units of `time_matrix` (D32): a scalar for every non-depot node, or one value per node in matrix row order (a pandas Series must carry the labels of `X`). Requires `max_time_work`; the trips then fit the budget with the services included (`trip_times_` counts them).	`None`
`split`	`('greedy', 'optimal')`	Decoder of the giant tour into trips.	`"greedy"`
`callback`	`callable`	Called with one `RouteEvent` at `"start"`, after every outer iteration and at `"end"` (D30). Return `True` to stop an iterative solver after the current outer iteration (`stop_reason_ = "callback"`); any other return value continues. The callback runs inside the timed search, so its cost counts in `fit_time_`; an exception it raises propagates out of `fit` and leaves the estimator unfitted whatever the stage, the `"end"` event included. `skroute.viz` offers ready-made callbacks that draw the search live.	`None`

Returns:

Type	Description
`self`

Raises:

Type	Description
`TypeError`	If `callback` is neither callable nor `None`.

RouterTags `dataclass` ¶

RouterTags(kind: str = 'metaheuristic', exact: bool = False, stochastic: bool = False, iterative: bool = False, budget_aware: bool = False, requires_symmetric: bool = False, requires_coords: bool = False, max_nodes: int | None = None)

Capabilities of a solver, returned by BaseRouter._get_tags().

Parameters:

Name	Type	Description	Default
`kind`	`('exact', 'construction', 'local_search', 'metaheuristic', 'ensemble')`	Family of the solver (D28); used by the capability table and the tolerance tests.	`"exact"`
`exact`	`bool`	Provably optimal for the objective it accepts; such solvers set `is_optimal_`.	`False`
`stochastic`	`bool`	Consumes `random_state`; can be wrapped by `MultiStart`.	`False`
`iterative`	`bool`	Sets `history_`, `n_iter_` and `stop_reason_`.	`False`
`budget_aware`	`bool`	The search itself sees the multi-trip objective. Solvers opt IN (D28): a solver that does not declare it warns under a budget and its result is still decoded and priced under the multi-trip objective (D6).	`False`
`requires_symmetric`	`bool`	Raises on an asymmetric cost matrix (`ClarkeWright`).	`False`
`requires_coords`	`bool`	Raises without `coords=` (`SOM`).	`False`
`max_nodes`	`int or None`	Hard cap on the number of nodes (`BruteForce`, `HeldKarp`, `MILP`).	`None`

Notes

budget_aware=True is declared explicitly by: BruteForce, ClarkeWright, TwoOpt, OrOpt, LocalSearch, IteratedLocalSearch, SimulatedAnnealing, TabuSearch, Genetic, AntColony, EnsembleGenetic, EnsembleSimulatedAnnealing; MultiStart delegates to its estimator. Everything else warns under a budget.

Examples:

>>> from skroute import RouterTags
>>> RouterTags(kind="exact", exact=True, budget_aware=True, max_nodes=11).budget_aware
True
>>> RouterTags().budget_aware
False

RouteEvent `dataclass` ¶

RouteEvent(solver: str, stage: str, iteration: int, cost: float, best_cost: float, tour: ndarray | None, best_tour: ndarray | None, problem: RoutingProblem, extra: dict[str, Any] = dict())

One progress report of a running solver, handed to the callback of fit (D30).

Parameters:

Name	Type	Description	Default
`solver`	`str`	Class name of the solver that emitted the event (`"SimulatedAnnealing"`). Inside a `MultiStart` the inner solvers report under their own name, with `extra["restart"]`.	required
`stage`	`('start', 'iteration', 'end')`	`"start"` once before the first outer iteration, `"iteration"` once per outer iteration (where `history_` grows), `"end"` once with the final result.	`"start"`
`iteration`	`int`	Outer iteration index: 0 at `"start"`, `1, 2, ...` for the iterations, and the last iteration index at `"end"` — `n_iter_` for every iterative solver, the wrappers included (`MultiStart` and the Ensembles emit no iterations of their own and report the winning restart's `n_iter_`); for a construction solver, the number of step events it emitted (D31).	required
`cost`	`float`	Objective of `tour` as the solver knows it; `nan` when there is no tour yet.	required
`best_cost`	`float`	Objective of `best_tour`; `nan` when there is none yet. Non-increasing over the finite values of one fit (`nan` means unknown, not a value — D31); at `"end"` it equals the recomputed `cost_`.	required
`tour`	`ndarray of shape (n,) or None`	The solver's CURRENT solution as a label-space open giant tour, depot first — the tour it is working on (the annealing walker, the candidate of an iterated local search, the best individual of a generation...); `None` when the solver has no tour yet (`MILP` before its first integral solution, a construction heuristic at every event before `"end"` — D31).	required
`best_tour`	`ndarray of shape (n,) or None`	The best-so-far tour in the same format; at `"end"` exactly `tour_`.	required
`problem`	`RoutingProblem`	The instance being solved (`est.problem_` after the fit): labels, coordinates, budget.	required
`extra`	`dict`	Solver-specific facts: `temperature` (SimulatedAnnealing), `tenure` (TabuSearch), `generation`/`n_evaluations` (Genetic), `kick` (IteratedLocalSearch), `moves_applied` (the descents), `radius`/`learning_rate`/`ring` (SOM), `n_ants` (AntColony), `n_components`/`lower_bound` (MILP), `n_trips` (ClarkeWright), `n_edges` (NRBS), `restart` (added by `MultiStart` to every forwarded event). Three keys are standardised by D31 so that viewers can draw the structure a solver is building: `edges` — a list of `(label, label)` tuples (the growing path or partial cycle of a construction heuristic, MILP's current LP support, the strongest pheromone trails of AntColony); `edge_weights` — floats in `[0, 1]` parallel to `edges` (pheromone strength, LP values); `ring` — an `(m, 2)` float array with the SOM neurons in the units of `problem.coords`. Construction solvers emit one `"iteration"` event per step with `tour=None`, `cost=nan` and `edges`. Each solver's docstring lists its keys.	`dict()`

Notes

Events are frozen and compare by identity. The arrays are copies: a solver's buffers keep changing after the callback returns, the event does not. route and trips decode best_tour with the problem's own split rule (the one fit uses for route_ and trips_), so a multi-trip instance is drawn trip by trip.

Examples:

A deterministic descent on four nodes: one event per stage, and the "end" event carries the fitted tour.

>>> import numpy as np
>>> from skroute import TwoOpt
>>> C = np.array([[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]], dtype=float)
>>> events = []
>>> est = TwoOpt().fit(C, callback=events.append)
>>> [e.stage for e in events]
['start', 'iteration', 'end']
>>> events[-1]
RouteEvent(solver='TwoOpt', stage='end', iteration=1, best_cost=22)
>>> events[-1].best_tour.tolist() == est.tour_.tolist(), events[-1].route.tolist()
(True, [0, 1, 2, 3, 0])

Returning True stops an iterative solver after the current outer iteration:

>>> from skroute import SimulatedAnnealing
>>> sa = SimulatedAnnealing(random_state=0).fit(C, callback=lambda e: e.stage == "iteration")
>>> sa.n_iter_, sa.stop_reason_
(1, 'callback')

trips `property` ¶

trips: list[ndarray]

best_tour decoded into closed label trips [depot, ..., depot]; [] without a tour.

route `property` ¶

route: ndarray | None

best_tour as driven — depot, trip 1, depot, ..., depot — or None without a tour.

clone ¶

clone(estimator: BaseRouter) -> BaseRouter

New unfitted estimator with the same parameters (deep copies nothing; parameters are values).

Parameters:

Name	Type	Description	Default
`estimator`	`BaseRouter`	The estimator to copy. Nested estimators (parameters with `get_params`) are cloned recursively.	required

Returns:

Name	Type	Description
`estimator`	`BaseRouter`	A fresh instance of the same class, `== estimator` but never fitted.

Examples:

>>> from skroute import clone
>>> from skroute.base import BaseRouter
>>> class Identity(BaseRouter):
...     def __init__(self, verbose=0):
...         self.verbose = verbose
...
...     def _solve(self, problem, rng):
...         return problem.to_index_tour(problem.labels)
>>> est = Identity(verbose=2).fit([[0, 1, 2], [1, 0, 1], [2, 1, 0]])
>>> copy = clone(est)
>>> copy == est, copy is est, hasattr(copy, "cost_")
(True, False, False)

is_router ¶

is_router(obj: Any) -> bool

Whether obj is a scikit-route estimator (an instance of BaseRouter).

Examples:

>>> from skroute import is_router
>>> from skroute.base import BaseRouter
>>> is_router(BaseRouter()), is_router(BaseRouter), is_router(None)
(True, False, False)

all_solvers ¶

all_solvers() -> list[type[BaseRouter]]

Every solver class that can be instantiated with no arguments, sorted by name (D27).

The roster is derived from the registry at the top of skroute/__init__.py: every registered name defined in one of the five solver subpackages (exact, construction, local_search, metaheuristics, ensemble) except MultiStart, which needs an estimator. Imports are eager: a registered module that is missing or does not define its name raises ImportError — the roster is the parametrisation of the whole test battery and must never shrink silently.

Returns:

Name	Type	Description
`solvers`	`list of type`	Subclasses of `BaseRouter`, sorted by `__name__`.

Raises:

Type	Description
`ImportError`	When a registered solver module cannot be imported or lacks the registered name.

Examples:

>>> from skroute import all_solvers
>>> solvers = all_solvers()
>>> [s.__name__ for s in solvers][:3]
['AntColony', 'BruteForce', 'ClarkeWright']

set_log_level ¶

set_log_level(level: int | str) -> None

Set the level of the skroute logger and make its records visible.

Sets logging.getLogger("skroute").setLevel(level); if the logger's only handler is the NullHandler attached at import, adds a StreamHandler to stderr with the format "%(name)s %(levelname)s %(message)s". Equivalent to logging.basicConfig(level=logging.INFO) for users who do not configure logging.

Parameters:

Name	Type	Description	Default
`level`	`int or str`	A logging level (`logging.INFO`, `"INFO"`, `"DEBUG"`...).	required

Examples:

>>> import logging, skroute
>>> log = logging.getLogger("skroute")
>>> saved = (log.level, list(log.handlers))  # the example restores the logger it changes
>>> skroute.set_log_level("INFO")
>>> log.level == logging.INFO and any(isinstance(h, logging.StreamHandler) for h in log.handlers)
True
>>> log.setLevel(saved[0])  # undo, so the example leaves the logger as it found it
>>> log.handlers[:] = saved[1]

exceptions ¶

Exceptions raised by scikit-route.

NotFittedError ¶

Bases: ValueError, AttributeError

Raised by check_is_fitted when a fitted attribute is accessed before fit was called.

InfeasibleProblemError ¶

Bases: ValueError

Raised when a node cannot be served in a single trip within max_time_work.

metrics ¶

Public recomputation helpers: route_cost, split_trips and the per-day timetable (SPEC §3.5, D32).

Everything here works in label space, on the route_/tour_ arrays a fitted solver exposes, so a user (or a test) can price any route under the objective — or turn it into arrival and departure times — without touching index space.

Stop `dataclass` ¶

Stop(day: int, order: int, label: Any, arrival: float, departure: float, travel: float, service: float, wait: float = 0.0, start: float = 8 * 60.0)

One line of a timetable: a visit, or the depot at either end of a day.

Times are minutes since the start of the day (floats, so the arithmetic is exact and the caller decides the rounding); the *_time properties render them as HH:MM clock strings from the day's start.

Parameters:

Name	Type	Description	Default
`day`	`int`	Day (trip) number, 1-based.	required
`order`	`int`	Position in the day: `0` is the departure from the depot, the last order the return.	required
`label`	`hashable`	Label of the node (the depot's label at both ends).	required
`arrival`	`float`	Minutes after `start` at which the vehicle arrives (`0.0` at the departure stop).	required
`departure`	`float`	`arrival + service + wait`; at the final depot stop it equals `arrival`.	required
`travel`	`float`	Driving minutes from the previous stop (`0.0` at the departure stop).	required
`service`	`float`	Minutes spent at the stop (`problem.service_time` of the node; `0.0` on returning).	required
`wait`	`float`	Idle minutes before the service starts. Always `0.0` today — reserved for time windows.	`0.0`
`start`	`float`	Minutes after midnight at which the day starts (`08:00`); used by the clock strings only, and left out of the repr and of equality: two stops with the same minutes are equal (and hash alike) whatever clock they are rendered on.	`480.0`

Examples:

>>> from skroute.metrics import Stop
>>> stop = Stop(day=1, order=2, label="b", arrival=95.0, departure=125.0, travel=20.0, service=30.0)
>>> stop.arrival_time, stop.departure_time
('09:35', '10:05')
>>> Stop(1, 0, "d", 0.0, 0.0, 0.0, 0.0, start=9 * 60 + 30).departure_time
'09:30'
>>> Stop(1, 0, "d", 0.0, 0.0, 0.0, 0.0, start=9 * 60 + 30) == Stop(1, 0, "d", 0.0, 0.0, 0.0, 0.0)
True

arrival_time `property` ¶

arrival_time: str

HH:MM of arrival (rounded to the minute; wraps past midnight).

departure_time `property` ¶

departure_time: str

HH:MM of departure (rounded to the minute; wraps past midnight).

route_cost ¶

route_cost(X: Any, route: Any, *, depot: Any = None, labels: Any = None, time_matrix: Any = None, max_time_work: float | None = None, extra_cost: float = 0.0, people: int = 1, service_time: Any = None, split: str = 'greedy') -> float

Objective of a label-space route (D1), recomputed from scratch.

Parameters:

Name	Type	Description	Default
`X`	`(n, n) array-like, DataFrame or dict-of-dicts`	Cost matrix (rows are origins).	required
`route`	`sequence of labels`	Open tour, closed route or multi-trip route (the depot may repeat). Its first label is the depot. Every depot occurrence is removed and the giant tour is re-decoded with `split`, exactly as `fit` did — so a hand-made plan is priced as the decoder would cut it, not as driven; `timetable` keeps the days as driven instead. The two agree on every route produced by `fit`.	required
`depot`	`label`	Must equal `route[0]` when given; `None` means `route[0]` — so a `route_`/`tour_` produced with any `depot=` re-evaluates without repeating it.	`None`
`labels`	`sequence of n hashables`	Labels of a plain ndarray `X`.	`None`
`time_matrix`	`same kinds as X`	Durations; required iff `max_time_work` is given.	`None`
`max_time_work`	`float > 0`	Per-trip budget. `None` = plain TSP.	`None`
`extra_cost`	`float >= 0`	Fixed charge per trip beyond the first.	`0.0`
`people`	`int >= 1`	Multiplies `extra_cost` only.	`1`
`service_time`	`float or (n,) array-like`	Time spent at each stop, in the units of `time_matrix` (D32); requires `max_time_work`. The route is re-decoded with the services included, exactly as `fit` did.	`None`
`split`	`('greedy', 'optimal')`	Decoder of the giant tour into trips.	`"greedy"`

Returns:

Name	Type	Description
`cost`	`float`

Raises:

Type	Description
`ValueError`	`"depot must be the first label of route"` when `depot` disagrees with `route[0]`; the `RoutingProblem` errors for invalid inputs.

Examples:

>>> from skroute.metrics import route_cost
>>> C = [[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]]
>>> route_cost(C, [0, 1, 2, 3, 0])
22.0
>>> route_cost(C, [2, 3, 0, 1], labels=[0, 1, 2, 3])
22.0
>>> hours = [[0, 1, 2, 2], [1, 0, 1, 2], [2, 1, 0, 1], [2, 2, 1, 0]]
>>> route_cost(C, [0, 1, 2, 0, 3, 0], time_matrix=hours, max_time_work=4.0, extra_cost=3.0)
41.0

Half an hour at every stop makes the same tour need two trips under a five-hour day:

>>> route_cost(C, [0, 1, 2, 3], time_matrix=hours, max_time_work=5.0, extra_cost=3.0)
22.0
>>> route_cost(C, [0, 1, 2, 3], time_matrix=hours, max_time_work=5.0, extra_cost=3.0, service_time=0.5)
41.0

split_trips ¶

split_trips(route: Any, depot: Any = None) -> list[ndarray]

Split a label route at depot occurrences into closed trips [depot, ..., depot].

Parameters:

Name	Type	Description	Default
`route`	`sequence of labels`	As driven: depot first, possibly repeated between trips and at the end. An open tour (depot only at the front) is returned as one closed trip.	required
`depot`	`label`	`None` means `route[0]`.	`None`

Returns:

Name	Type	Description
`trips`	`list of ndarray`	One closed trip per segment, in route order; empty segments (two consecutive depots) are dropped.

Examples:

>>> from skroute.metrics import split_trips
>>> [t.tolist() for t in split_trips([0, 1, 2, 0, 3, 0])]
[[0, 1, 2, 0], [0, 3, 0]]
>>> [t.tolist() for t in split_trips(["d", "a", "b"])]
[['d', 'a', 'b', 'd']]

timetable ¶

timetable(obj: Any, route: Any = ..., *, start: Any = ..., units: str = ..., as_frame: Literal[False] = ...) -> list[list[Stop]]

timetable(obj: Any, route: Any = ..., *, start: Any = ..., units: str = ..., as_frame: Literal[True]) -> DataFrame

timetable(obj: Any, route: Any = ..., *, start: Any = ..., units: str = ..., as_frame: bool) -> list[list[Stop]] | DataFrame

timetable(obj: Any, route: Any = None, *, start: Any = '08:00', units: str = 'min', as_frame: bool = False) -> list[list[Stop]] | DataFrame

Arrival and departure times of every stop, day by day (D32).

Parameters:

Name	Type	Description	Default
`obj`	`fitted estimator or RoutingProblem`	A fitted solver (its `problem_` and `route_` are used) or a `RoutingProblem` with a time matrix and a budget.	required
`route`	`sequence of labels`	Required with a `RoutingProblem`; overrides `route_` with an estimator. A multi-trip route (the depot repeated between trips, as `route_`) is read as driven, one day per segment, whatever `max_time_work` says — a day that runs over the budget is reported (with a warning), never re-cut; an open tour or a closed route is a giant tour and is cut into days with the problem's split rule (`problem.split`). Note the difference with `route_cost`, which always removes the depot occurrences and re-decodes the giant tour: the two agree on every route produced by `fit`.	`None`
`start`	`str or time`	Start of the day at the depot, every day, as `"HH:MM"` or a `datetime.time`; the vehicle leaves at `start` plus the depot's service time, if any.	`"08:00"`
`units`	`('min', 'h', 's')`	Units of `problem.time` and `problem.service_time`; the timetable is always in minutes.	`"min"`
`as_frame`	`bool`	Return one flat `pandas.DataFrame` instead (pandas required: `pip install "scikit-route[pandas]"`), with the columns `day`, `order`, `label`, `arrival_time`, `departure_time`, `travel`, `service`, `wait`, `arrival`, `departure`.	`False`

Returns:

Name	Type	Description
`days`	`list of list of Stop, or DataFrame`	One inner list per day (trip), each opening with the departure from the depot (`order 0`, `departure == service at the depot`, `0.0` without one) and closing with the return (`arrival` = minutes after `start` at which the day ends). Times are computed from `problem.time` (driving) and `problem.service_time` (stops), so the return of every day lands within `max_time_work` for a route produced by `fit`.

Raises:

Type	Description
`ValueError`	`"timetable needs time_matrix and max_time_work"` for a plain TSP; a route that is not a valid tour; a `start` that is not a clock time.
`TypeError`	When `obj` is neither an estimator nor a problem.
`NotFittedError`	For an unfitted estimator.

Warns:

Type	Description
`UserWarning`	When a day of a route read as driven ends after `max_time_work`.

timetable_summary ¶

timetable_summary(days: list[list[Stop]]) -> list[dict[str, Any]]

Totals of every day of a timetable.

Parameters:

Name	Type	Description	Default
`days`	`list of list of Stop`	As returned by `timetable(...)` (not the DataFrame form: group that one by `day`).	required

Returns:

Name	Type	Description
`summary`	`list of dict`	One dict per day with `day` (1-based), `n_stops` (customers visited, the depot excluded), `driving` (minutes on the road), `service` (minutes at the stops, the depot's included), `total` (minutes from the start to the return) and `back_at` (the return as `HH:MM`).

Raises:

Type	Description
`TypeError`	When `days` is not a list of days of `Stop`s — the DataFrame of `as_frame=True` included.

Examples:

>>> import numpy as np
>>> from skroute import BruteForce
>>> from skroute.metrics import timetable, timetable_summary
>>> minutes = np.array([[0, 30, 60, 60], [30, 0, 30, 60], [60, 30, 0, 30], [60, 60, 30, 0]], dtype=float)
>>> est = BruteForce().fit(minutes, time_matrix=minutes, max_time_work=200.0, service_time=30.0)
>>> for day in timetable_summary(timetable(est)):
...     print(day)
{'day': 1, 'n_stops': 2, 'driving': 120.0, 'service': 60.0, 'total': 180.0, 'back_at': '11:00'}
{'day': 2, 'n_stops': 1, 'driving': 120.0, 'service': 30.0, 'total': 150.0, 'back_at': '10:30'}

Base and problem¶

Service times¶

Watching a solver work¶

Partial structures: edges, edge_weights, ring¶

RoutingProblem ¶

multi_trip property ¶

fixed_cost property ¶

time_or_cost property ¶

split_code property ¶

depot_label property ¶

index_of ¶

to_index_tour ¶

to_label_tour ¶

evaluate ¶

trip_starts ¶

trip_costs ¶

trip_times ¶

neighbours ¶

BaseRouter ¶

get_params ¶

set_params ¶

fit ¶

RouterTags dataclass ¶

RouteEvent dataclass ¶

trips property ¶

route property ¶

clone ¶

is_router ¶

all_solvers ¶

set_log_level ¶

exceptions ¶

NotFittedError ¶

InfeasibleProblemError ¶

metrics ¶

Stop dataclass ¶

arrival_time property ¶

departure_time property ¶

route_cost ¶

split_trips ¶

timetable ¶

timetable_summary ¶

Partial structures: `edges`, `edge_weights`, `ring`¶

multi_trip `property` ¶

fixed_cost `property` ¶

time_or_cost `property` ¶

split_code `property` ¶

depot_label `property` ¶

RouterTags `dataclass` ¶

RouteEvent `dataclass` ¶

trips `property` ¶

route `property` ¶

Stop `dataclass` ¶

arrival_time `property` ¶

departure_time `property` ¶