Repository: PyVRP/PyVRP (python)

Issue:
Lower bounding fleet sizes with reloading
Currently, `minimise_fleet` uses demand to estimate a lower bound on the number of needed vehicles:

https://github.com/PyVRP/PyVRP/blob/68d07577540431fe6a6fb26117e7598fcc270226/pyvrp/minimise_fleet.py#L95-L106

This is fine when vehicles are only allowed to execute a single trip. Now, with multiple trips, this relation no longer holds. How do we handle that? 

The easiest is probably to check for `max_trips` and adjust capacity based on that as `capacity * vehicle_type.max_trips`. `max_trips` is already 1 in case reloading is not possible. The downside is that we do not get a very informative lower bound for multi-trip instances, but that should be OK.


Pull request:
Fix multi-trip fleet minimisation
This PR:

- [x] Closes #800.
- [x] Adds and passes relevant tests.
- [x] Has well-formatted code and documentation.

<details>

**Notes**:

Please read our [contributing guidelines](https://pyvrp.org/dev/contributing.html) first.
In particular:

- You must add tests when making code changes.
  This keeps the code coverage level up, and helps ensure the changes work as intended.
- When fixing a bug, you must add a test that would produce the bug in the master branch, and then show that it is fixed with the new code. 
- New code additions must be well formatted. Changes should pass the pre-commit workflow, which you can set up locally using [pre-commit](https://pre-commit.com/#intro). 
- Docstring additions must render correctly, including escapes and LaTeX.
- Finally, it is essential that all contributions in this PR are license-compatible with PyVRP's MIT license.
  Please check that this PR can be included into PyVRP under the MIT license.

</details>


Patch:
diff --git a/pyvrp/minimise_fleet.py b/pyvrp/minimise_fleet.py
index f091a1f..ef02b72 100644
--- a/pyvrp/minimise_fleet.py
+++ b/pyvrp/minimise_fleet.py
@@ -99,8 +99,10 @@ def _lower_bound(data: ProblemData) -> int:
         delivery = sum(c.delivery[dim] for c in data.clients())
         pickup = sum(c.pickup[dim] for c in data.clients())
         demand = max(delivery, pickup)
-        capacity = vehicle_type.capacity[dim]
 
+        # Vehicle capacity applies per trip - if more than one trip is allowed,
+        # the capacity needs to be scaled as well.
+        capacity = vehicle_type.capacity[dim] * vehicle_type.max_trips
         bound = max(int(np.ceil(demand / max(capacity, 1))), bound)
 
     return bound


Test patch:
diff --git a/tests/test_minimise_fleet.py b/tests/test_minimise_fleet.py
index af48f6d..d2c4eac 100644
--- a/tests/test_minimise_fleet.py
+++ b/tests/test_minimise_fleet.py
@@ -74,3 +74,17 @@ def test_X_instance():
     vehicle_type = minimise_fleet(data, MaxIterations(10))
     data = data.replace(vehicle_types=[vehicle_type])
     assert_equal(data.num_vehicles, 13)
+
+
+def test_lower_bound_multi_trip_instance(ok_small_multiple_trips):
+    """
+    Tests that the fleet minimisation procedure adjusts the lower bound based
+    on the vehicle's multi-trip capabilities.
+    """
+    new_veh_type = ok_small_multiple_trips.vehicle_type(0)
+    data = ok_small_multiple_trips.replace(vehicle_types=[new_veh_type])
+
+    # The vehicle capacity is insufficient to visit every client in a single
+    # trip, but this problem can be solved in a single route, as 3 4 | 1 2.
+    vehicle_type = minimise_fleet(data, MaxIterations(10))
+    assert_equal(vehicle_type.num_available, 1)