Tabu search¶

TabuSearch applies, at every iteration, the best admissible move of a candidate neighbourhood — 2-opt reversals and Or-opt relocations that join a node to one of its k nearest neighbours — even when that move worsens the tour, and forbids re-adding the edges the move removed for exactly tenure iterations (a tabu move is still allowed when it beats the best tour so far). With tenure="auto" the tenure is redrawn every iteration from [ceil(sqrt(n)), 2 ceil(sqrt(n))] (Taillard's robust tabu search); history_ records the best cost after every iteration and the best tour is kept in its own buffer (history_[-1] equals cost_ exactly).

Plain symmetric TSPs use the O(1) move deltas of the core; asymmetric matrices and the multi-trip objective use full evaluation of every candidate move, so the search sees the decoded trips and their fixed charges. Tabu attributes are edges — arcs on an asymmetric matrix, where a 2-opt reversal removes every arc of the reversed span — and live in an int32 (n, n) matrix, which bounds the practical size at about 5 000 nodes.

>>> from skroute import TabuSearch
>>> from skroute.datasets import load_tsp
>>> dj = load_tsp("dj38")
>>> ts = TabuSearch(random_state=0).fit(dj.distance_matrix(), labels=dj.labels)
>>> ts.cost_ / dj.optimal_tour_length < 1.08
True

TabuSearch ¶

TabuSearch(n_iter: int = 1000, tenure: int | str = 'auto', n_candidates: int | None = 10, patience: int | None = 200, init: Any = 'nearest_neighbour', time_limit: float | None = None, random_state: Any = None, verbose: int = 0)

Bases: BaseRouter

Tabu search over the giant tour: 2-opt and Or-opt candidate moves, edge tabus, aspiration.

Each iteration scans the candidate neighbourhood of the current tour, applies the best admissible move even when it worsens the tour, and forbids re-adding the edges that move removed for tenure iterations (a tabu move is still admissible when it beats the best tour so far). The best tour seen is kept in its own buffer and is what fit returns; history_ records its cost per iteration.

Parameters:

Name	Type	Description	Default
`n_iter`	`int >= 1`	Maximum number of iterations (`"max_iter"`).	`1000`
`tenure`	`int >= 1 or 'auto'`	Tabu tenure of a removed edge, in iterations: an edge removed at iteration `k` is tabu at exactly the iterations `k + 1 .. k + tenure`. `"auto"` draws one tenure per iteration uniformly from `[ceil(sqrt(n)), 2 * ceil(sqrt(n))]` (both ends inclusive, pre-drawn from `random_state`: the robust tabu search of Taillard); an int is a fixed tenure (a tenure of `n_iter` or more keeps every removed edge tabu until the end).	`"auto"`
`n_candidates`	`int >= 1 or None`	Size of the candidate lists (the `k` nearest nodes of every node by cost); `None` uses the full neighbourhood (`n - 1`).	`10`
`patience`	`int >= 1 or None`	Iterations without improvement of the best-so-far before stopping (`"patience"`); `None` disables the rule.	`200`
`init`	`('nearest_neighbour', 'random')`	Starting tour: the greedy nearest-neighbour construction, a random permutation, or the `tour_`/`route_` of another solver (labels; the depot may repeat).	`"nearest_neighbour"`
`time_limit`	`float > 0 or None`	Wall-clock budget in seconds, checked once per iteration (`"time_limit"`). Breaks bit-exact reproducibility across machines; `None` disables.	`None`
`random_state`	`(int, Generator or None)`	Seed of the tenure draws (and of `init="random"`). The same seed on the same machine gives bit-identical results; a passed `Generator` is advanced by the fit.	`None`
`verbose`	`int`	`0` is silent; `1` logs every `max(1, n_iter // 10)` iterations at INFO; `2` logs every iteration. Records go to the `skroute` logger at INFO; enable them with `logging.basicConfig(level=logging.INFO)` or `skroute.set_log_level("INFO")`.	`0`

Attributes:

Name	Type	Description
`history_`	`ndarray of shape (n_iter_,), float64`	Best-so-far cost after each iteration (monotone non-increasing); `history_[-1]` equals `cost_` exactly.
`n_iter_`	`int`	Iterations run.
`stop_reason_`	`{'max_iter', 'patience', 'time_limit', 'callback'}`	Why the search stopped (`"callback"`: the `callback` of `fit` returned `True`).
See `BaseRouter` for ``tour_``, ``route_``, ``trips_``, ``cost_`` and
`the other fitted attributes shared by every solver.`

Notes

Neighbourhood. For every node a and every candidate c of a (the k nearest nodes by cost): the 2-opt reversals that create the edge {a, c} (a before c in the tour, or after) and the no-reversal Or-opt relocations of the segments of length 1..3 starting or ending at a next to c (and vice versa) — the move family of the core's generic descent. On a symmetric plain TSP each move is priced with the O(1) deltas of the core (two_opt_delta, or_opt_delta); under a budget (multi-trip) or with an asymmetric matrix every move is applied on a scratch copy and priced with the full objective, so the search sees the decoded trips and their fixed charges, and directional costs on ATSP. The reversal of the whole tour (an orientation flip on a symmetric plain TSP) is not a move.

Tabu attributes. The edges a move removes (arcs when the matrix is asymmetric) are stored in an int32 (n, n) matrix tabu_until; a move is tabu when any edge it adds is still tabu, unless it improves on the best cost so far (aspiration). On an asymmetric matrix a 2-opt reversal removes every arc of the reversed span (the inner arcs change direction), so all of them are marked and a reversal is tabu when any arc it adds is tabu; on a symmetric matrix only the two boundary edges change. When every move is tabu the best move overall is applied, so the search never stalls. The practical ceiling of the matrix is about 5 000 nodes (100 MB).

Complexity. O(n * n_candidates) O(1) delta evaluations per iteration on the symmetric plain path (about 14 moves per candidate pair); O(n^2 * n_candidates) on the generic path (O(n) per move), which is meant for instances of a few hundred nodes.

Callback events (D30). "start" carries the init tour; every iteration emits one "iteration" whose tour is the walker (which may have moved uphill) and best_tour the best buffer, with extra["tenure"] the tenure applied in that iteration.

Supports: symmetric and asymmetric matrices, the multi-trip objective (both split rules); stochastic, iterative, budget-aware.

References

.. [1] F. Glover, "Tabu search — part I", ORSA Journal on Computing 1 (1989) 190-206. .. [2] E. Taillard, "Robust taboo search for the quadratic assignment problem", Parallel Computing 17 (1991) 443-455. .. [3] 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 import TabuSearch
>>> from skroute.datasets import load_tsp
>>> dj = load_tsp("dj38")
>>> ts = TabuSearch(random_state=0).fit(dj.distance_matrix(), labels=dj.labels)
>>> ts.cost_ / dj.optimal_tour_length < 1.08  # the fast-tier tolerance of SPEC §6
True
>>> int(ts.route_[0]) == int(ts.route_[-1]) == int(ts.depot_) == 1
True
>>> ts.n_iter_ == len(ts.history_) and ts.stop_reason_ in {"max_iter", "patience"}
True
>>> bool(np.all(np.diff(ts.history_) <= 0))  # best-so-far per iteration
True

A multi-trip instance: eight Spanish towns, a per-trip budget and a fixed charge per extra trip, two people. The search itself prices the decoded trips.

>>> from skroute.datasets import load_alicante_murcia
>>> d = load_alicante_murcia()
>>> budget = 1.5 * float((d.time[0] + d.time[:, 0]).max())
>>> ts = TabuSearch(random_state=0).fit(
...     d.cost,
...     time_matrix=d.time,
...     labels=d.labels,
...     depot=d.depot,
...     max_time_work=budget,
...     extra_cost=10.0,
...     people=2,
... )
>>> bool(np.all(ts.trip_times_ <= budget)) and ts.n_trips_ == len(ts.trips_)
True