Construction heuristics¶
skroute.construction builds a tour from scratch, deterministically, in O(n²) to O(n² log n):
no random_state, no iterations (hence no history_, n_iter_ or stop_reason_); with a callback they still report one iteration event per construction step carrying the partial structure in extra["edges"]. These solvers are the natural warm starts of the
local searches and metaheuristics (init=est.tour_, or simply init="nearest_neighbour") and
honest baselines when a tolerance has to be judged.
| Solver | Rule | Asymmetric matrices | Sees the multi-trip budget | Typical gap (wi29 / dj38) |
|---|---|---|---|---|
NearestNeighbour |
greedy walk from the depot | yes | no (warns; result still split) | 31.8 % / 46.4 % |
Insertion |
farthest / cheapest / nearest insertion at the cheapest position | yes (direction-aware) | no (warns; result still split) | 1.9 % / 0.0 % (farthest) |
ClarkeWright |
parallel savings, merges refused when the merged trip would not fit | no (ValueError) |
yes | 4.9 % / 0.1 % |
NRBS |
the 2020 Node Ranking Based on Stats heuristic | yes | no (warns; result still split) | 18.3 % / 7.8 % |
All four accept every input kind of the base class (ndarray, DataFrame, dict-of-dicts, or a ready
RoutingProblem) and return the fitted attributes of BaseRouter:
tour_, route_, trips_, cost_, ... The cost is always recomputed from the tour by the base
class.
>>> from skroute import ClarkeWright, Insertion, NearestNeighbour
>>> from skroute.datasets import load_tsp
>>> dj = load_tsp("dj38")
>>> C = dj.distance_matrix()
>>> gaps = {type(est).__name__: est.fit(C, labels=dj.labels).cost_ / dj.optimal_tour_length - 1
... for est in (NearestNeighbour(), Insertion(), ClarkeWright())}
>>> gaps["Insertion"] <= gaps["ClarkeWright"] <= gaps["NearestNeighbour"]
True
Under a budget, ClarkeWright is the one construction heuristic whose search sees
max_time_work: the others build a plain tour, warn once, and hand it to the decoder, which
still splits it into feasible trips and prices it under the multi-trip objective. Every savings
trip fits the budget as it is driven (checked with the decoder's own arithmetic, in the
orientation that is emitted — with an asymmetric time matrix the direction that fits is kept),
so on a time matrix that satisfies the triangle inequality the decoder can only merge savings
trips further; on one that violates it, the decoder may also split a trip, and n_trips_ can
then exceed the number of savings trips.
Migrating NRBS from 1.0: the five exponents must now be >= 0 (1.0.0a2 validated only the type,
so a negative exponent was accepted there and raises ValueError here); ints are accepted, the
defaults are 1.0 and distance_weigth is spelt distance_weight.
NearestNeighbour ¶
Bases: BaseRouter
Nearest-neighbour construction: from the depot, always move to the closest unvisited node.
The simplest tour builder and the default warm start (init="nearest_neighbour") of every
iterative solver. Deterministic: ties are broken by the lowest node index.
Attributes:
| Name | Type | Description |
|---|---|---|
tour_ |
ndarray of shape (n,)
|
The open giant tour in label space, depot first. |
route_ |
ndarray of shape (n + n_trips,)
|
The route as driven: depot, trip 1, depot, trip 2, ..., depot. |
cost_ |
float
|
Objective of |
n_trips_, trips_, trip_costs_, trip_times_, fit_time_, problem_, labels_, depot_, n_nodes_ |
The other fitted attributes of |
Notes
Algorithm: start at the depot; while unvisited nodes remain, append the unvisited node j
with the smallest C[current, j] (lowest index on ties); the tour closes back to the depot.
The whole walk runs in the compiled core (nearest_neighbour_tour),
O(n²) time and O(n) extra memory. The result is typically 25 % (rounded Euclidean instances)
to 45 % above the optimum: use it as a baseline or a warm start, not as an answer.
Supports: symmetric and asymmetric matrices (every step reads C[current, j] directionally);
multi-trip objective only through the decoder — the search itself ignores max_time_work and
a UserWarning says so (the returned trips still fit the budget). Deterministic.
Callback events (D30, D31): "start" has no tour; then one "iteration" per node the walk
appends — n - 1 events indexed 1 .. n - 1 — each with tour=None, cost=nan,
best_cost=nan and extra["edges"], the growing path from the depot as a list of
(label, label) pairs (k pairs at event k); "end" carries the finished tour. The
walk itself runs in the kernel, so the trace is replayed afterwards from the returned tour and
costs O(n²) Python work only when a callback is set; a callback returning True silences the
remaining trace events — every step when it answers at "start" (the result is the same with
or without a callback).
References
.. [1] D. S. Johnson and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization", in Local Search in Combinatorial Optimization, Wiley, 1997.
Examples:
>>> import numpy as np
>>> from skroute.construction import NearestNeighbour
>>> C = np.array([[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]], dtype=float)
>>> nn = NearestNeighbour().fit(C)
>>> nn.tour_.tolist(), nn.route_.tolist(), nn.cost_
([0, 1, 2, 3], [0, 1, 2, 3, 0], 22.0)
On a national instance the gap to the published optimum is a stable fact (31.8 % on wi29):
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")
>>> nn = NearestNeighbour().fit(wi.distance_matrix(), labels=wi.labels)
>>> int(nn.route_[0]) == int(nn.route_[-1]) == 1 and nn.cost_ / wi.optimal_tour_length < 1.5
True
Insertion ¶
Bases: BaseRouter
Insertion construction: grow the tour one node at a time, each at its cheapest position.
Start with the depot and one seed node, then repeatedly pick an unrouted node by the
strategy and insert it between the two consecutive tour nodes a -> b that minimise
C[a, j] + C[j, b] - C[a, b]. There are no FarthestInsertion/CheapestInsertion
classes: the strategy is a parameter.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
strategy
|
('farthest', 'cheapest', 'nearest')
|
Which unrouted node is inserted next.
The distance from the partial tour to a node |
"farthest"
|
Attributes:
| Name | Type | Description |
|---|---|---|
tour_ |
ndarray of shape (n,)
|
The open giant tour in label space, depot first. |
route_ |
ndarray of shape (n + n_trips,)
|
The route as driven: depot, trip 1, depot, trip 2, ..., depot. |
cost_ |
float
|
Objective of |
n_trips_, trips_, trip_costs_, trip_times_, fit_time_, problem_, labels_, depot_, n_nodes_ |
The other fitted attributes of |
Notes
Algorithm (compiled kernel, typed memoryviews, no Python in the loop): the partial tour is a
linked list closed on the depot; min_dist[j] (distance from the tour to every unrouted
node) is updated incrementally after each insertion; the cheapest strategy additionally caches
each unrouted node's best edge and rescans only the nodes whose cached edge was split.
Complexity O(n²) for farthest and nearest; O(n²) in practice for cheapest (O(n³) in the
adversarial worst case, when every unrouted node keeps preferring the edge that was just
split). Deterministic: selection ties go to the lowest node index, position ties to the first
edge met walking the tour from the depot.
Every insertion cost is evaluated with the arcs in driving direction, so the heuristic is
exact on asymmetric matrices (ATSP): nothing is reversed, nothing assumes C == C.T.
Supports: symmetric and asymmetric matrices; multi-trip objective only through the decoder —
the search itself ignores max_time_work and a UserWarning says so (the returned trips
still fit the budget). Deterministic.
Callback events (D30, D31): "start" has no tour; then one "iteration" per node placed
— n - 1 events indexed 1 .. n - 1, the seed being the first — each with tour=None,
cost=nan, best_cost=nan and extra["edges"], the closed partial cycle after that
placement as (label, label) pairs in driving direction (m pairs for m routed nodes;
at the seed the two pairs depot -> seed -> depot cover the same segment); "end" carries
the finished tour. The kernel records the insertion order (the node placed and the node it was
placed after, two stores per step) only when a callback is set, and the estimator then replays
it on a Python list in O(n²); without a callback nothing is recorded or replayed and the tour is
bit-identical. A callback returning True silences the remaining trace events (every step when
it answers at "start").
References
.. [1] D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis, "An analysis of several heuristics for the traveling salesman problem", SIAM Journal on Computing 6(3), 1977, 563-581. .. [2] D. S. Johnson and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization", in Local Search in Combinatorial Optimization, Wiley, 1997.
Examples:
>>> import numpy as np
>>> from skroute.construction import Insertion
>>> C = np.array([[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]], dtype=float)
>>> far = Insertion().fit(C) # strategy="farthest"
>>> far.tour_.tolist(), far.cost_
([0, 1, 2, 3], 22.0)
>>> cheap = Insertion(strategy="cheapest").fit(C)
>>> cheap.tour_.tolist(), cheap.cost_ # the same cycle, driven the other way round
([0, 3, 2, 1], 22.0)
Farthest insertion stays within the 25 % tolerance of the test-suite on the national instances:
>>> from skroute.datasets import load_tsp
>>> dj = load_tsp("dj38")
>>> est = Insertion().fit(dj.distance_matrix(), labels=dj.labels)
>>> est.cost_ / dj.optimal_tour_length < 1.25
True
ClarkeWright ¶
Bases: BaseRouter
Clarke-Wright parallel savings: merge the pairs of trips that save the most, budget included.
Every customer starts as its own out-and-back trip; the saving of serving i and j
consecutively is s_ij = C[d, i] + C[j, d] - shape * C[i, j]. Savings are visited in
descending order and two trips are merged at their endpoints whenever the merged trip is still
feasible. Without a budget everything merges into one tour (the greedy-edge heuristic); with
max_time_work the merge is refused when the merged closed trip would not fit, so the
search itself sees the multi-trip objective (budget_aware=True).
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
shape
|
float
|
Savings weight |
1.0
|
Attributes:
| Name | Type | Description |
|---|---|---|
tour_ |
ndarray of shape (n,)
|
The open giant tour in label space, depot first: the savings trips concatenated by increasing creation index, each oriented with its endpoint nearer to the depot first (unless only the other direction fits the budget, which needs an asymmetric time matrix). |
route_ |
ndarray of shape (n + n_trips,)
|
The route as driven: depot, trip 1, depot, trip 2, ..., depot. |
cost_ |
float
|
Objective of |
n_trips_, trips_, trip_costs_, trip_times_, fit_time_, problem_, labels_, depot_, n_nodes_ |
The other fitted attributes of |
Notes
Algorithm: n-1 singleton trips with creation index = node index; the (n-1)(n-2)/2
savings sorted descending (stable, then by (i, j)); for each pair, merge when neither node
is interior to its trip, the trips differ and — under a budget — the merged closed trip's
duration is <= max_time_work; the merged trip keeps the smaller creation index. The giant
tour is the concatenation of the trips by increasing creation index, each oriented so that
its first node is the endpoint with the smaller C[d, .] (ties: the smaller node index).
Complexity O(n² log n) time (the sort) and O(n²) memory (the savings, as numpy arrays; the
Python-level state is O(n)).
The feasibility of a merge is decided on the trip as it will be driven: the merged path is oriented first and its duration is accumulated leg by leg from the depot, with the arithmetic of the greedy decoder, so a merge accepted here is never undone by rounding. When the time matrix is asymmetric (the cost matrix must be symmetric) the two directions of a trip last differently; if only the reverse of the preferred orientation fits, the trip is kept reversed rather than refused. Every savings trip therefore fits the budget in driving direction.
The base class then re-decodes the giant tour with the problem's split rule. When the time
matrix satisfies the triangle inequality, the greedy decoder can only merge consecutive
savings trips further, so n_trips_ <= the number of savings trips; when it violates it
(road matrices occasionally do) the decoder may also split a trip whose prefix cannot return
to the depot in time, so n_trips_ may exceed the number of savings trips. In both cases
the reported trips_ can differ from the savings trips and every trip fits the budget.
Supports: symmetric matrices only (an asymmetric X raises ValueError); multi-trip
objective inside the search. Deterministic.
Callback events (D30, D31): "start" has no tour; then one "iteration" before the first
merge — every customer its own out-and-back trip — and one per accepted merge (merges + 1
events indexed from 1), each with tour=None, cost=nan, best_cost=nan,
extra["edges"] — the depot -> trip -> depot legs of every current trip as
(label, label) pairs in driving direction, trips by increasing creation index — and
extra["n_trips"], the number of savings trips at that moment; "end" carries the giant
tour. Refused merges emit nothing. The trace is built inline in the savings loop and costs O(n)
per event only when a callback is set; a callback returning True silences the remaining
trace events — every step when it answers at "start" (the merges themselves go on: the
result never depends on the callback).
References
.. [1] G. Clarke and J. W. Wright, "Scheduling of vehicles from a central depot to a number of delivery points", Operations Research 12(4), 1964, 568-581. .. [2] T. J. Gaskell, "Bases for vehicle fleet scheduling", Operational Research Quarterly 18(3), 1967, 281-295.
Examples:
>>> import numpy as np
>>> from skroute.construction import ClarkeWright
>>> C = np.array([[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]], dtype=float)
>>> cw = ClarkeWright().fit(C)
>>> cw.tour_.tolist(), cw.cost_, cw.n_trips_
([0, 1, 2, 3], 22.0, 1)
Under a budget the merges that would not fit are refused (the example of the base class: 4-hour trips, 3 EUR per extra trip):
>>> cost = {
... 1: {1: 0, 2: 5, 3: 9, 4: 10},
... 2: {1: 5, 2: 0, 3: 4, 4: 8},
... 3: {1: 9, 2: 4, 3: 0, 4: 3},
... 4: {1: 10, 2: 8, 3: 3, 4: 0},
... }
>>> hours = {
... 1: {1: 0, 2: 1, 3: 2, 4: 2},
... 2: {1: 1, 2: 0, 3: 1, 4: 2},
... 3: {1: 2, 2: 1, 3: 0, 4: 1},
... 4: {1: 2, 2: 2, 3: 1, 4: 0},
... }
>>> cw = ClarkeWright().fit(cost, time_matrix=hours, max_time_work=4.0, extra_cost=3.0)
>>> cw.route_.tolist(), cw.cost_, cw.n_trips_
([1, 2, 3, 1, 4, 1], 41.0, 2)
>>> bool(np.all(cw.trip_times_ <= 4.0))
True
NRBS ¶
NRBS(mean_priority: float = 1.0, std_priority: float = 1.0, mean_connection: float = 1.0, std_connection: float = 1.0, distance_weight: float = 1.0)
Bases: BaseRouter
Node Ranking Based on Stats: rank nodes by the statistics of their cost row, then link them.
The construction heuristic of scikit-route 1.0 (2020), ported faithfully. Every node gets a
priority from the mean and standard deviation of its row of C and a ranked list of
connection candidates; two passes over the priority order give each node two neighbours
without closing a premature cycle, and the resulting Hamiltonian cycle is the tour.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
mean_priority
|
float
|
Exponent |
1.0
|
std_priority
|
float
|
Exponent |
1.0
|
mean_connection
|
float
|
Exponent |
1.0
|
std_connection
|
float
|
Exponent |
1.0
|
distance_weight
|
float
|
Exponent All five exponents must be |
1.0
|
Attributes:
| Name | Type | Description |
|---|---|---|
tour_ |
ndarray of shape (n,)
|
The open giant tour in label space, depot first. |
route_ |
ndarray of shape (n + n_trips,)
|
The route as driven: depot, trip 1, depot, trip 2, ..., depot. |
cost_ |
float
|
Objective of |
n_trips_, trips_, trip_costs_, trip_times_, fit_time_, problem_, labels_, depot_, n_nodes_ |
The other fitted attributes of |
Notes
Algorithm (the 2020 heuristic, with its arithmetic): mu_i and sigma_i are the mean and
the population standard deviation of the full row C[i, :], zero diagonal included. The
priority mu_i^a * sigma_i^b is sorted descending (ties by node index). The connection
score of candidate j for node i is mu_j^c * sigma_j^e / max(C[i, j], 1e-12)^f,
sorted descending per node (ties by priority order); the depot participates like any node and
coincident points (C[i, j] == 0) get the maximum score and are linked first. Two passes over
the priority order: for each node with fewer than two neighbours, link it to its highest-scoring
candidate that has fewer than two neighbours, is not already its neighbour and does not close a
cycle before all nodes are covered — cycle detection by union-find plus degree counters (the
2020 code deep-copied the graph per candidate; the selection order is unchanged). The cycle is
read from the depot towards the neighbour attached to it first.
Two passes always close the cycle. Before the last edge the graph is a forest of paths, so a
node with fewer than two neighbours is an endpoint (or isolated): if another path exists, any
of its endpoints is an eligible candidate (different component, not a neighbour); if the graph
is already one Hamiltonian path, its other endpoint is eligible because the cycle ban is lifted
at n - 1 edges. Every visit of a node with degree below two therefore adds an edge, and
after the second pass every degree is two — one cycle through every node, whatever the ties.
The scores must be well defined: negative costs with a fractional exponent (mu^a of a
negative mean) or costs so large that the powers overflow to inf / inf give NaN scores and
raise ValueError; infinite scores (coincident points with a large distance_weight) are
fine and sort first. Complexity O(n² log n) time; the candidate ranking is computed one node at
a time, so the memory beyond the cost matrix is O(n).
On Barcelona with all five exponents = 0.5 the tour and its cost reproduce the 1.0 result
pinned in tests/data/nrbs_barcelona_1_0.json.
Supports: symmetric and asymmetric matrices (the score reads C[i, j] directionally; the
linked cycle is undirected, so ATSP results are heuristic); multi-trip objective only through
the decoder — the search itself ignores max_time_work and a UserWarning says so (the
returned trips still fit the budget). Deterministic.
Callback events (D30, D31): "start" has no tour; then one "iteration" per connection
the two passes add — n events indexed 1 .. n for n >= 3 (the cycle has n edges;
none below three nodes) — each with tour=None, cost=nan, best_cost=nan,
extra["edges"], the edge set built so far as (label, label) pairs (the node served by
the pass first, its chosen candidate second: the graph is undirected), and extra["n_edges"];
"end" carries the tour read from the closed cycle. The trace is built inline and costs O(n)
per event only when a callback is set; a callback returning True silences the remaining
trace events — every step when it answers at "start" (the passes go on: the result never
depends on the callback).
References
.. [1] A. Rubiales, scikit-route 1.0.0a2, skroute.heuristics.NRBS (2020).
Examples:
>>> import numpy as np
>>> from skroute.construction import NRBS
>>> C = np.array([[0, 5, 9, 10], [5, 0, 4, 8], [9, 4, 0, 3], [10, 8, 3, 0]], dtype=float)
>>> est = NRBS().fit(C)
>>> sorted(est.tour_.tolist()) == [0, 1, 2, 3] and int(est.route_[0]) == int(est.route_[-1]) == 0
True
>>> est.cost_
22.0
The 1.0 regression: Barcelona with every exponent at 0.5 (depot= is a label):
>>> from skroute.datasets import load_barcelona
>>> bcn = load_barcelona()
>>> est = NRBS(0.5, 0.5, 0.5, 0.5, 0.5).fit(bcn.cost, labels=bcn.labels, depot=bcn.depot)
>>> int(est.route_[0]) == int(est.route_[-1]) == 10000007 and est.n_nodes_ == 19
True