Repository: PyVRP/PyVRP
Pull request #251 (2023-06-21 19:20:43)

Remove circle sector
This PR removes the CircleSector stuff in favour of something a little simpler. It's a bit of an experiment, so I'm not sure if this will ever leave the draft phase.

- [x] Relates somewhat to #122 with the overlap tolerance parameter.
- [x] Adds and passes relevant tests. (some, not a lot)
- [x] Has well-formatted code and documentation.
- [x] Profiled.

### Benchmark

On VRPTW, avg. over ten seeds with 1h runtime:

| category     | Main| This PR / tol `0.05` | This PR / tol `0.1` |
|-----|-------|---------------|----------------|
| C1  | 413653.2 | 413715.9 | **413624.8** |
| C2  | 161914.0 | 161911.7 | **161904.6** |
| R1  | 473236.7 | **472958.3** | 473476.1 |
| R2  | 277276.7 | **277151.2** | 277180.0 |
| RC1 | **442251.7** | 442278.5 | 442496.8 |
| RC2 | 232344.3 | **232172.1** | 232267.2 |

This PR with tol `0.1` (dda1c3754553ad6d08c2f541f2734d217f9d7034; job ID 3191043; 10x seeds/1h):
```
 Avg. objective: 333491.7 (min: 333335, max: 333615)
Avg. iterations: 46777.7 (min: 37213, max: 54719)
```

This PR with tol `0.05` (9a367b12c83863c24a0e623aafe1b2bb8ec3290d; job ID 3197392; 10x seeds/1h):
```
 Avg. objective: 333364.7 (min: 333266, max: 333541)
Avg. iterations: 65629.2 (min: 54852, max: 73735)
```

Current main (44814444bdc641a6bd2b97db4f776de9ef94b934; job ID 3194371; 10x seeds/1h):
```
 Avg. objective: 333446.2 (min: 333378, max: 333578)
Avg. iterations: 53109.8 (min: 42391, max: 60488)
```

<details>

Current main:
```
                mean       min       max
      inst                              
obj   C1    413653.2  413399.5  413894.1
      C2    161914.0  161875.7  161940.3
      R1    473236.7  472823.4  473928.7
      R2    277276.7  277137.7  277423.1
      RC1   442251.7  441941.2  442696.9
      RC2   232344.3  232142.0  232515.8
iters C1     86897.7   67948.0   96072.3
      C2     89695.5   70547.7  104632.9
      R1     32816.6   24127.4   39345.9
      R2     31566.0   25629.5   37211.7
      RC1    41553.3   33352.8   49832.1
      RC2    36129.7   30638.5   40896.0
```

Tol 5%:
```
                mean       min       max
      inst                              
obj   C1    413715.9  413506.7  413963.9
      C2    161911.7  161881.9  161940.2
      R1    472958.3  472276.9  473682.5
      R2    277151.2  276883.0  277421.0
      RC1   442278.5  441943.8  442802.4
      RC2   232172.1  232039.6  232297.8
iters C1     68754.8   58413.7   75266.2
      C2    125908.9  104863.5  137205.7
      R1     37943.0   29827.4   46800.1
      R2     55186.0   44400.6   62332.7
      RC1    43416.2   37265.2   48655.1
      RC2    62565.9   52367.9   73215.2
```

Tol 10%:
```
                mean       min       max
      inst                              
obj   C1    413624.8  413419.1  413787.6
      C2    161904.6  161876.3  161952.9
      R1    473476.1  472934.1  474472.5
      R2    277180.0  276856.6  277492.0
      RC1   442496.8  442036.7  442847.5
      RC2   232267.2  232094.3  232446.5
iters C1     49744.7   38400.1   58399.0
      C2     82816.3   65034.2  101933.3
      R1     27435.0   21179.1   33515.0
      R2     40568.2   33302.2   45933.8
      RC1    32510.7   25672.3   40133.3
      RC2    47591.7   35629.1   56144.2
```

</details>

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/PyVRP/PyVRP/pull/251?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PyVRP) Report
Patch coverage: **`100.00`**% and project coverage change: **`-0.07`** :warning:
> Comparison is base [(`ba5ea6e`)](https://app.codecov.io/gh/PyVRP/PyVRP/commit/ba5ea6e7d98b770a2991626340ca65d123bb29c4?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PyVRP) 94.22% compared to head [(`4989b06`)](https://app.codecov.io/gh/PyVRP/PyVRP/pull/251?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PyVRP) 94.15%.

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##             main     #251      +/-   ##
==========================================
- Coverage   94.22%   94.15%   -0.07%     
==========================================
  Files          63       62       -1     
  Lines        2388     2363      -25     
  Branches      196      193       -3     
==========================================
- Hits         2250     2225      -25     
  Misses         51       51              
  Partials       87       87              
```


| [Impacted Files](https://app.codecov.io/gh/PyVRP/PyVRP/pull/251?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PyVRP) | Coverage Δ | |
|---|---|---|
| [pyvrp/cpp/search/Route.h](https://app.codecov.io/gh/PyVRP/PyVRP/pull/251?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PyVRP#diff-cHl2cnAvY3BwL3NlYXJjaC9Sb3V0ZS5o) | `83.33% <ø> (ø)` | |
| [pyvrp/cpp/search/LocalSearch.cpp](https://app.codecov.io/gh/PyVRP/PyVRP/pull/251?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PyVRP#diff-cHl2cnAvY3BwL3NlYXJjaC9Mb2NhbFNlYXJjaC5jcHA=) | `91.58% <100.00%> (ø)` | |
| [pyvrp/cpp/search/Route.cpp](https://app.codecov.io/gh/PyVRP/PyVRP/pull/251?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PyVRP#diff-cHl2cnAvY3BwL3NlYXJjaC9Sb3V0ZS5jcHA=) | `91.04% <100.00%> (-0.74%)` | :arrow_down: |


</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/PyVRP/PyVRP/pull/251?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PyVRP).   
:loudspeaker: Do you have feedback about the report comment? [Let us know in this issue](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PyVRP).

N-Wouda: Profiling this doesn't look too bad. `std::atan` isn't fast, but it doesn't take more than 0.5% of the time, so I don't think it's worth swapping that out for something faster right now.

SWAP* is much more concerning. Something to look into in the future.

N-Wouda: Took a little calibrating, but an `overlap_tolerance` of 5% seems to do the trick.

N-Wouda: @leonlan @wouterkool could either/both of you have a look? This PR does the overlap thing for routes in a simpler way than what we currently have with the `CircleSector`, and that seems to be OK in terms of performance (benchmarks in first comment above).

leonlan: It's been a while since I touched the CircleSector code, but IIRC, the circle sectors are "pie-slices" that cover the entire route right? And the current PR proposes to simplify this by only looking at the route centroids? Are there any cases where this may go wrong really badly?
N-Wouda: >We do need to introduce a single parameter (overlap tolerance) required to make it work. I think this new method is less robust, but I prefer the simpler implementation.

(we already have this parameter currently as well, it's not new)

I can see us remove this particular thing pretty quickly anyway, particularly if we do anything about #126. It's more of a temporary solution that at least removes some stuff that's pretty complicated and apparently not really needed.

N-Wouda: > It's been a while since I touched the CircleSector code, but IIRC, the circle sectors are "pie slices" that cover the entire route right? And the current PR proposes to simplify this by only looking at the route centroids? Are there any cases where this may go wrong really badly?

It could result in very few routes overlapping, which might be bad. But I can't think of a nontrivial example where that'd happen, and in any case, we also still have search and the granular neighbourhood that covers some of that. In other cases, ~1/10th of the circle (+5% or -5% overlap) is enough for the centroids to be "close enough". I think that works particularly well on the random instances (R1/R2) where previously the sectors would overlap almost all the time, but the centroids could be pretty far apart.

leonlan: > (we already have this parameter currently as well, it's not new)

That's true, but it was unused. I don't know when we added this parameter, but HGS-CVRP did not have this parameter.

> I can see us remove this particular thing pretty quickly anyway, particularly if we do anything about https://github.com/PyVRP/PyVRP/issues/126. It's more of a temporary solution that at least removes some stuff that's pretty complicated and apparently not really needed.

If we follow up with #126 then I think we should definitely do this. (#126 is very low priority though because I don't have any "route neighbors" ideas right now.)
N-Wouda: >I don't know when we added this parameter, but HGS-CVRP did not have this parameter.

From what I can gather it's a leftover from the [EURO/NeurIPS baseline](https://github.com/ortec/euro-neurips-vrp-2022-quickstart/blob/77a1a24e6b30baf3aab8931c020302c3975ca77e/baselines/hgs_vrptw/Params.h#L111). We removed it in our implementation because in the end we didn't do this intensification regularly, and then reintroduced it during our performance panic in February :-).


Patch:
diff --git a/pyvrp/cpp/crossover/selective_route_exchange.cpp b/pyvrp/cpp/crossover/selective_route_exchange.cpp
index e3d68e2..b67e445 100644
--- a/pyvrp/cpp/crossover/selective_route_exchange.cpp
+++ b/pyvrp/cpp/crossover/selective_route_exchange.cpp
@@ -14,14 +14,9 @@ namespace
 // Angle of the given route w.r.t. the centroid of all client locations.
 double routeAngle(pyvrp::ProblemData const &data, Route const &route)
 {
-    // This computes a pseudo-angle that sorts roughly equivalently to the atan2
-    // angle, but is much faster to compute. See the following post for details:
-    // https://stackoverflow.com/a/16561333/4316405.
     auto const [dataX, dataY] = data.centroid();
     auto const [routeX, routeY] = route.centroid();
-    auto const dx = routeX - dataX;
-    auto const dy = routeY - dataY;
-    return std::copysign(1. - dx / (std::fabs(dx) + std::fabs(dy)), dy);
+    return std::atan2(routeY - dataY, routeX - dataX);
 }
 
 Routes sortByAscAngle(pyvrp::ProblemData const &data, Routes routes)
diff --git a/pyvrp/cpp/search/CircleSector.h b/pyvrp/cpp/search/CircleSector.h
deleted file mode 100644
index 88e9fd6..0000000
--- a/pyvrp/cpp/search/CircleSector.h
+++ /dev/null
@@ -1,85 +0,0 @@
-#ifndef PYVRP_CIRCLESECTOR_H
-#define PYVRP_CIRCLESECTOR_H
-
-namespace pyvrp::search
-{
-// Data structure to represent circle sectors
-// Angles are measured in [0,65535] instead of [0,359], in such a way that
-// modulo operations are much faster (since 2^16 = 65536) Credit to Fabian
-// Giesen at "https://web.archive.org/web/20200912191950" and
-// "https://fgiesen.wordpress.com/2015/09/24/intervals-in-modular-arithmetic/"
-// for useful implementation tips regarding interval overlaps in modular
-// arithmetics
-struct CircleSector
-{
-    int start;  // The angle where the circle sector starts
-    int end;    // The angle where the circle sector ends
-
-    // Calculate the positive modulo 65536 of i
-    // Example: positive_mod(-6) returns 65530
-    // Example: positive_mod(10) returns 10
-    // Example: positive_mod(65538) returns 2
-    static int positive_mod(int i)
-    {
-        // Using the formula positive_mod(i,x) = (i % x + x) % x
-        // Remark that "i % 65536" should be automatically compiled in an
-        // optimized form as "i & 0xffff" for faster calculations
-        return (i % 65536 + 65536) % 65536;
-    }
-
-    static int positive_mod(CircleSector const &sector)
-    {
-        return positive_mod(sector.end - sector.start);
-    }
-
-    // Initialize a circle sector from a single point
-    // The function extend(int point) can be used to create a circle sector that
-    // is not only one point
-    void initialize(int point)
-    {
-        start = point;
-        end = point;
-    }
-
-    // Tests if a point is enclosed in the circle sector
-    [[nodiscard]] bool isEnclosed(int point) const
-    {
-        return positive_mod(point - start) <= positive_mod(end - start);
-    }
-
-    // Tests overlap of two circle sectors with tolerance
-    // Note, this effectively is sector1.isEnclosed(sector2.start) ||
-    // sector2.isEnclosed(sector1.start), while also taking into account
-    // tolerance
-    static bool overlap(const CircleSector &sector1,
-                        const CircleSector &sector2,
-                        const int tolerance)
-    {
-        // the RHS is the size of the sector, by adding the tolerance outside
-        // the positive_mod, we avoid overflow beyond a full circle
-        return ((positive_mod(sector2.start - sector1.start)
-                 <= positive_mod(sector1) + tolerance)
-                || (positive_mod(sector1.start - sector2.start)
-                    <= positive_mod(sector2) + tolerance));
-    }
-
-    // Extends the circle sector to include an additional point
-    // Done in a "greedy" way, such that the resulting circle sector is the
-    // smallest
-    void extend(int point)
-    {
-        // Check if the point is in the circle sector
-        if (!isEnclosed(point))
-        {
-            // If the point is outside the circle sector, extend the circle
-            // sector in a greedy way
-            if (positive_mod(point - end) <= positive_mod(start - point))
-                end = point;
-            else
-                start = point;
-        }
-    }
-};
-}  // namespace pyvrp::search
-
-#endif  // PYVRP_CIRCLESECTOR_H
diff --git a/pyvrp/cpp/search/LocalSearch.cpp b/pyvrp/cpp/search/LocalSearch.cpp
index 1200308..4e9c69d 100644
--- a/pyvrp/cpp/search/LocalSearch.cpp
+++ b/pyvrp/cpp/search/LocalSearch.cpp
@@ -96,15 +96,16 @@ Solution LocalSearch::search(Solution &solution,
 
 Solution LocalSearch::intensify(Solution &solution,
                                 CostEvaluator const &costEvaluator,
-                                int overlapToleranceDegrees)
+                                double overlapTolerance)
 {
+    if (overlapTolerance < 0 || overlapTolerance > 1)
+        throw std::runtime_error("overlapTolerance must be in [0, 1].");
+
     if (routeOps.empty())
         return solution;
 
     loadSolution(solution);
 
-    auto const overlapTolerance = overlapToleranceDegrees * 65536;
-
     std::vector<int> lastTestedRoutes(data.numVehicles(), -1);
     lastModified = std::vector<int>(data.numVehicles(), 0);
 
diff --git a/pyvrp/cpp/search/LocalSearch.h b/pyvrp/cpp/search/LocalSearch.h
index fd29d3f..ca1261c 100644
--- a/pyvrp/cpp/search/LocalSearch.h
+++ b/pyvrp/cpp/search/LocalSearch.h
@@ -101,7 +101,7 @@ public:
      */
     Solution intensify(Solution &solution,
                        CostEvaluator const &costEvaluator,
-                       int overlapToleranceDegrees = 0);
+                       double overlapTolerance = 0.05);
 
     /**
      * Shuffles the order in which the node and route pairs are evaluated, and
diff --git a/pyvrp/cpp/search/Route.cpp b/pyvrp/cpp/search/Route.cpp
index b606ae2..2f0b07c 100644
--- a/pyvrp/cpp/search/Route.cpp
+++ b/pyvrp/cpp/search/Route.cpp
@@ -71,52 +71,23 @@ Route::Route(ProblemData const &data, size_t const idx, size_t const vehType)
     endDepot.route = this;
 }
 
-void Route::setupSector()
-{
-    if (empty())
-        return;
-
-    auto const &depotData = data.client(startDepot.client);
-    auto const &clientData = data.client(n(&startDepot)->client);
-
-    auto const diffX = static_cast<double>(clientData.x - depotData.x);
-    auto const diffY = static_cast<double>(clientData.y - depotData.y);
-    auto const angle = CircleSector::positive_mod(
-        static_cast<int>(32768. * std::atan2(diffY, diffX) / std::numbers::pi));
-
-    sector.initialize(angle);
-
-    for (auto *node : *this)
-    {
-        auto const &clientData = data.client(node->client);
-
-        auto const diffX = static_cast<double>(clientData.x - depotData.x);
-        auto const diffY = static_cast<double>(clientData.y - depotData.y);
-        auto const angle = CircleSector::positive_mod(static_cast<int>(
-            32768. * std::atan2(diffY, diffX) / std::numbers::pi));
-
-        sector.extend(angle);
-    }
-}
-
-void Route::setupRouteTimeWindows()
-{
-    auto *node = &endDepot;
-
-    do  // forward time window segments
-    {
-        auto *prev = p(node);
-        prev->twAfter
-            = TWS::merge(data.durationMatrix(), prev->tw, node->twAfter);
-        node = prev;
-    } while (!node->isDepot());
-}
-
 size_t Route::vehicleType() const { return vehicleType_; }
 
-bool Route::overlapsWith(Route const &other, int const tolerance) const
+bool Route::overlapsWith(Route const &other, double tolerance) const
 {
-    return CircleSector::overlap(sector, other.sector, tolerance);
+    auto const [dataX, dataY] = data.centroid();
+    auto const [thisX, thisY] = centroid;
+    auto const [otherX, otherY] = other.centroid;
+
+    // Each angle is in [-pi, pi], so the absolute difference is in [0, tau].
+    auto const thisAngle = std::atan2(thisY - dataY, thisX - dataX);
+    auto const otherAngle = std::atan2(otherY - dataY, otherX - dataX);
+    auto const absDiff = std::abs(thisAngle - otherAngle);
+
+    // First case is obvious. Second case exists because tau and 0 are also
+    // close together but separated by one period.
+    auto constexpr tau = 2 * std::numbers::pi;
+    return absDiff <= tolerance * tau || absDiff >= (1 - tolerance) * tau;
 }
 
 void Route::update()
@@ -128,12 +99,19 @@ void Route::update()
     Distance distance = 0;
     Distance deltaReversalDistance = 0;
 
+    centroid = {0, 0};
+
     while (!node->isDepot())
     {
         size_t const position = nodes.size();
         nodes.push_back(node);
 
-        load += data.client(node->client).demand;
+        auto const &clientData = data.client(node->client);
+
+        centroid.first += static_cast<double>(clientData.x);
+        centroid.second += static_cast<double>(clientData.y);
+
+        load += clientData.demand;
         distance += data.dist(p(node)->client, node->client);
 
         deltaReversalDistance += data.dist(node->client, p(node)->client);
@@ -149,6 +127,9 @@ void Route::update()
         node = n(node);
     }
 
+    centroid.first /= size();
+    centroid.second /= size();
+
     load += data.client(endDepot.client).demand;
     distance += data.dist(p(&endDepot)->client, endDepot.client);
 
@@ -162,11 +143,18 @@ void Route::update()
     endDepot.twBefore = TWS::merge(
         data.durationMatrix(), p(&endDepot)->twBefore, endDepot.tw);
 
-    setupSector();
-    setupRouteTimeWindows();
-
     load_ = endDepot.cumulatedLoad;
     timeWarp_ = endDepot.twBefore.totalTimeWarp();
+
+    // forward time window segments
+    node = &endDepot;
+    do
+    {
+        auto *prev = p(node);
+        prev->twAfter
+            = TWS::merge(data.durationMatrix(), prev->tw, node->twAfter);
+        node = prev;
+    } while (!node->isDepot());
 }
 
 std::ostream &operator<<(std::ostream &out, pyvrp::search::Route const &route)
diff --git a/pyvrp/cpp/search/Route.h b/pyvrp/cpp/search/Route.h
index ea996e9..22b0e51 100644
--- a/pyvrp/cpp/search/Route.h
+++ b/pyvrp/cpp/search/Route.h
@@ -1,7 +1,6 @@
 #ifndef PYVRP_ROUTE_H
 #define PYVRP_ROUTE_H
 
-#include "CircleSector.h"
 #include "ProblemData.h"
 #include "TimeWindowSegment.h"
 
@@ -56,17 +55,11 @@ private:
     size_t const vehicleType_;
 
     std::vector<Node *> nodes;  // List of nodes in this route, excl. depot
-    CircleSector sector;        // Circle sector of the route's clients
+    std::pair<double, double> centroid;  // Center point of route's clients.
 
     Load load_;          // Current route load.
     Duration timeWarp_;  // Current route time warp.
 
-    // Sets the sector data.
-    void setupSector();
-
-    // Sets forward node time windows.
-    void setupRouteTimeWindows();
-
 public:                // TODO make fields private
     size_t const idx;  // Route index
     Node startDepot;   // Departure depot for this route
@@ -151,11 +144,10 @@ public:                // TODO make fields private
     [[nodiscard]] size_t vehicleType() const;
 
     /**
-     * Tests if this route overlaps with the other route, that is, whether
-     * their circle sectors overlap with a given tolerance.
+     * Tests if this route potentially overlaps with the other route, subject
+     * to a tolerance in [0, 1].
      */
-    [[nodiscard]] bool overlapsWith(Route const &other,
-                                    int const tolerance) const;
+    [[nodiscard]] bool overlapsWith(Route const &other, double tolerance) const;
 
     /**
      * Updates this route. To be called after swapping nodes/changing the
diff --git a/pyvrp/cpp/search/bindings.cpp b/pyvrp/cpp/search/bindings.cpp
index 5729c73..722fee2 100644
--- a/pyvrp/cpp/search/bindings.cpp
+++ b/pyvrp/cpp/search/bindings.cpp
@@ -109,7 +109,7 @@ PYBIND11_MODULE(_search, m)
              &LocalSearch::intensify,
              py::arg("solution"),
              py::arg("cost_evaluator"),
-             py::arg("overlap_tolerance_degrees") = 0)
+             py::arg("overlap_tolerance") = 0.05)
         .def("shuffle", &LocalSearch::shuffle, py::arg("rng"));
 
     py::class_<MoveTwoClientsReversed, NodeOp>(m, "MoveTwoClientsReversed")
diff --git a/pyvrp/search/LocalSearch.py b/pyvrp/search/LocalSearch.py
index a343cd4..54a7509 100644
--- a/pyvrp/search/LocalSearch.py
+++ b/pyvrp/search/LocalSearch.py
@@ -120,12 +120,12 @@ class LocalSearch:
         self,
         solution: Solution,
         cost_evaluator: CostEvaluator,
-        overlap_tolerance_degrees: int = 0,
+        overlap_tolerance: float = 0.05,
     ) -> Solution:
         """
         This method uses the intensifying route operators on this local search
         object to improve the given solution. To limit the computational
-        demands of intensification, the  ``overlap_tolerance_degrees`` argument
+        demands of intensification, the  ``overlap_tolerance`` argument
         can be used to limit the number of route pairs that are evaluated.
 
         Parameters
@@ -134,11 +134,11 @@ class LocalSearch:
             The solution to improve.
         cost_evaluator
             Cost evaluator to use.
-        overlap_tolerance_degrees
+        overlap_tolerance
             This method evaluates improving moves between route pairs. To limit
             computational efforts, by default not all route pairs are
             considered: only those route pairs that share some overlap when
-            considering their center's angle from the depot are evaluated.
+            considering their center's angle to the center of all clients.
             This parameter controls the amount of overlap needed before two
             routes are evaluated.
 
@@ -149,9 +149,7 @@ class LocalSearch:
             solution that was passed in.
         """
         self._ls.shuffle(self._rng)
-        return self._ls.intensify(
-            solution, cost_evaluator, overlap_tolerance_degrees
-        )
+        return self._ls.intensify(solution, cost_evaluator, overlap_tolerance)
 
     def search(
         self, solution: Solution, cost_evaluator: CostEvaluator
diff --git a/pyvrp/search/_search.pyi b/pyvrp/search/_search.pyi
index b30a57a..40da5ba 100644
--- a/pyvrp/search/_search.pyi
+++ b/pyvrp/search/_search.pyi
@@ -50,7 +50,7 @@ class LocalSearch:
         self,
         solution: Solution,
         cost_evaluator: CostEvaluator,
-        overlap_tolerance_degrees: int = 0,
+        overlap_tolerance: float = 0.05,
     ) -> Solution: ...
     def search(
         self, solution: Solution, cost_evaluator: CostEvaluator


Test patch:
diff --git a/pyvrp/search/tests/test_LocalSearch.py b/pyvrp/search/tests/test_LocalSearch.py
index b51688f..448e943 100644
--- a/pyvrp/search/tests/test_LocalSearch.py
+++ b/pyvrp/search/tests/test_LocalSearch.py
@@ -7,6 +7,7 @@ from pyvrp.search import (
     Exchange11,
     LocalSearch,
     NeighbourhoodParams,
+    RelocateStar,
     compute_neighbours,
 )
 from pyvrp.search._search import LocalSearch as cpp_LocalSearch
@@ -269,3 +270,42 @@ def test_bugfix_vehicle_type_offsets():
     improved_cost = cost_evaluator.penalised_cost(improved)
 
     assert_(improved_cost <= current_cost)
+
+
+def test_intensify_overlap_tolerance():
+    data = read("data/RC208.txt", "solomon", round_func="trunc")
+    rng = XorShift128(seed=42)
+
+    neighbours = compute_neighbours(data)
+    ls = LocalSearch(data, rng, neighbours)
+    ls.add_route_operator(RelocateStar(data))
+
+    cost_eval = CostEvaluator(1, 1)
+    sol = Solution.make_random(data, rng)
+
+    # Overlap tolerance is zero, so no routes should have overlap and thus
+    # no intensification should take place.
+    unchanged = ls.intensify(sol, cost_eval, overlap_tolerance=0)
+    assert_equal(unchanged, sol)
+
+    # But with full overlap tolerance, all routes should be checked. That
+    # should lead to an improvement over the random solution.
+    better = ls.intensify(sol, cost_eval, overlap_tolerance=1)
+    assert_(better != sol)
+    assert_(cost_eval.penalised_cost(better) < cost_eval.penalised_cost(sol))
+
+
+@mark.parametrize("tol", [-1.0, -0.01, 1.01, 10.9, 1000])
+def test_intensify_overlap_tolerance_raises_outside_unit_interval(tol):
+    data = read("data/RC208.txt", "solomon", round_func="trunc")
+    rng = XorShift128(seed=42)
+
+    neighbours = compute_neighbours(data)
+    ls = LocalSearch(data, rng, neighbours)
+    ls.add_route_operator(RelocateStar(data))
+
+    cost_eval = CostEvaluator(1, 1)
+    sol = Solution.make_random(data, rng)
+
+    with assert_raises(RuntimeError):  # each tolerance value is outside [0, 1]
+        ls.intensify(sol, cost_eval, overlap_tolerance=tol)
diff --git a/pyvrp/search/tests/test_RelocateStar.py b/pyvrp/search/tests/test_RelocateStar.py
index a4c8823..c518add 100644
--- a/pyvrp/search/tests/test_RelocateStar.py
+++ b/pyvrp/search/tests/test_RelocateStar.py
@@ -32,7 +32,7 @@ def test_exchange10_and_relocate_star_are_same_large_neighbourhoods():
         sol = Solution.make_random(data, rng)
         exchange_sol = ls.search(sol, cost_evaluator)
         relocate_sol = ls.intensify(
-            exchange_sol, cost_evaluator, overlap_tolerance_degrees=360
+            exchange_sol, cost_evaluator, overlap_tolerance=1
         )
 
         # RELOCATE* applies the best (1, 0)-exchange moves between routes. But
@@ -62,7 +62,7 @@ def test_exchange10_and_relocate_star_differ_small_neighbourhoods(size: int):
     sol = Solution.make_random(data, rng)
     exchange_sol = ls.search(sol, cost_evaluator)
     relocate_sol = ls.intensify(
-        exchange_sol, cost_evaluator, overlap_tolerance_degrees=360
+        exchange_sol, cost_evaluator, overlap_tolerance=1
     )
 
     # The original solution was not that great, so after (1, 0)-Exchange it
diff --git a/pyvrp/search/tests/test_SwapStar.py b/pyvrp/search/tests/test_SwapStar.py
index 7b7d2ce..7ddcbc3 100644
--- a/pyvrp/search/tests/test_SwapStar.py
+++ b/pyvrp/search/tests/test_SwapStar.py
@@ -36,7 +36,7 @@ def test_swap_star_identifies_additional_moves_over_regular_swap():
 
         swap_sol = ls.search(sol, cost_evaluator)
         swap_star_sol = ls.intensify(
-            swap_sol, cost_evaluator, overlap_tolerance_degrees=360
+            swap_sol, cost_evaluator, overlap_tolerance=1
         )
 
         # The regular swap operator should have been able to improve the random
@@ -63,9 +63,7 @@ def test_swap_star_on_RC208_instance(seed: int):
     route = list(range(1, data.num_clients + 1))
     split = rng.randint(data.num_clients)
     sol = Solution(data, [route[:split], route[split:]])
-    improved_sol = ls.intensify(
-        sol, cost_evaluator, overlap_tolerance_degrees=360
-    )
+    improved_sol = ls.intensify(sol, cost_evaluator, overlap_tolerance=1)
 
     # The new solution should strictly improve on our original solution, but
     # cannot use more routes since SWAP* does not create routes.