Repository: PyVRP/PyVRP (python)

Issue:
Bring back support for release times
We removed release times in https://github.com/PyVRP/PyVRP/commit/3065a577076d92326f3f03aa701976bd8a2bd7e0. Since release times are quite common in VRPs, it's probably good to add this back again. I also would like to use the PyVRP solver for my research on dynamic vehicle routing.

----
- [ ] Include release times crossover::greedyRepair? https://github.com/PyVRP/PyVRP/blob/3065a577076d92326f3f03aa701976bd8a2bd7e0/pyvrp/cpp/crossover/crossover.cpp

Pull request:
Release times
This PR:

- [x] Closes #244.
- [x] Adds and passes relevant tests.
- [x] Has well-formatted code and documentation.

<details>

**Notes**:

- It is essential that you add a test 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.

</details>


Patch:
diff --git a/pyvrp/Model.py b/pyvrp/Model.py
index c38189b..0acb2f7 100644
--- a/pyvrp/Model.py
+++ b/pyvrp/Model.py
@@ -20,7 +20,6 @@ Depot = Client
 
 
 class Edge:
-
     __slots__ = ["frm", "to", "distance", "duration"]
 
     def __init__(self, frm: Client, to: Client, distance: int, duration: int):
@@ -106,6 +105,7 @@ class Model:
         service_duration: int = 0,
         tw_early: int = 0,
         tw_late: int = 0,
+        release_time: int = 0,
         prize: int = 0,
         required: bool = True,
     ) -> Client:
@@ -120,6 +120,7 @@ class Model:
             service_duration,
             tw_early,
             tw_late,
+            release_time,
             prize,
             required,
         )
@@ -128,7 +129,11 @@ class Model:
         return client
 
     def add_depot(
-        self, x: int, y: int, tw_early: int = 0, tw_late: int = 0
+        self,
+        x: int,
+        y: int,
+        tw_early: int = 0,
+        tw_late: int = 0,
     ) -> Depot:
         """
         Adds a depot with the given attributes to the model. Returns the
diff --git a/pyvrp/_ProblemData.pyi b/pyvrp/_ProblemData.pyi
index 78a3e3c..0185753 100644
--- a/pyvrp/_ProblemData.pyi
+++ b/pyvrp/_ProblemData.pyi
@@ -23,6 +23,10 @@ class Client:
         Earliest time at which we can visit this client. Default 0.
     tw_late
         Latest time at which we can visit this client. Default 0.
+    release_time
+        Earliest time at which this client is released, that is, the earliest
+        time at which a vehicle may leave the depot to visit this client.
+        Default 0.
     prize
         Prize collected by visiting this client. Default 0.
     required
@@ -35,9 +39,9 @@ class Client:
     service_duration: int
     tw_early: int
     tw_late: int
+    release_time: int
     prize: int
     required: bool
-
     def __init__(
         self,
         x: int,
@@ -46,6 +50,7 @@ class Client:
         service_duration: int = 0,
         tw_early: int = 0,
         tw_late: int = 0,
+        release_time: int = 0,
         prize: int = 0,
         required: bool = True,
     ) -> None: ...
@@ -64,7 +69,6 @@ class VehicleType:
 
     capacity: int
     num_available: int
-
     def __init__(self, capacity: int, num_available: int) -> None: ...
 
 class ProblemData:
diff --git a/pyvrp/_Solution.pyi b/pyvrp/_Solution.pyi
index 46bc8e4..9c237a1 100644
--- a/pyvrp/_Solution.pyi
+++ b/pyvrp/_Solution.pyi
@@ -49,6 +49,10 @@ class Route:
         """
         Total waiting duration on this route.
         """
+    def release_time(self) -> int:
+        """
+        Release time of visits on this route.
+        """
     def prizes(self) -> int:
         """
         Total prize value collected on this route.
diff --git a/pyvrp/_TimeWindowSegment.pyi b/pyvrp/_TimeWindowSegment.pyi
index 419d7e8..5f0e2e3 100644
--- a/pyvrp/_TimeWindowSegment.pyi
+++ b/pyvrp/_TimeWindowSegment.pyi
@@ -11,6 +11,7 @@ class TimeWindowSegment:
         time_warp: int,
         tw_early: int,
         tw_late: int,
+        release_time: int,
     ) -> None:
         """
         Creates a time window segment.
@@ -18,9 +19,9 @@ class TimeWindowSegment:
         Parameters
         ----------
         idx_first
-            Index of the first customer in the route segment.
+            Index of the first client in the route segment.
         idx_last
-            Index of the last customer in the route segment.
+            Index of the last client in the route segment.
         duration
             Total duration, including waiting time.
         time_warp
@@ -28,7 +29,9 @@ class TimeWindowSegment:
         tw_early
             Earliest visit moment of the first client.
         tw_late
-            Latest visit moment of the last client.
+            Latest visit moment of the first client.
+        release_time
+            Earliest moment to start the route segment.
         """
     @overload
     @staticmethod
diff --git a/pyvrp/cpp/ProblemData.cpp b/pyvrp/cpp/ProblemData.cpp
index c989854..c8fb9c6 100644
--- a/pyvrp/cpp/ProblemData.cpp
+++ b/pyvrp/cpp/ProblemData.cpp
@@ -12,6 +12,7 @@ ProblemData::Client::Client(Coordinate x,
                             Duration serviceDuration,
                             Duration twEarly,
                             Duration twLate,
+                            Duration releaseTime,
                             Cost prize,
                             bool required)
     : x(x),
@@ -20,6 +21,7 @@ ProblemData::Client::Client(Coordinate x,
       serviceDuration(serviceDuration),
       twEarly(twEarly),
       twLate(twLate),
+      releaseTime(releaseTime),
       prize(prize),
       required(required)
 {
diff --git a/pyvrp/cpp/ProblemData.h b/pyvrp/cpp/ProblemData.h
index 6879d10..4fd7caa 100644
--- a/pyvrp/cpp/ProblemData.h
+++ b/pyvrp/cpp/ProblemData.h
@@ -19,6 +19,7 @@ public:
         Duration const serviceDuration;
         Duration const twEarly;      // Earliest possible start of service
         Duration const twLate;       // Latest possible start of service
+        Duration const releaseTime;  // Earliest possible time to leave depot
         Cost const prize = 0;        // Prize for visiting this client
         bool const required = true;  // Must client be in solution?
 
@@ -28,6 +29,7 @@ public:
                Duration serviceDuration = 0,
                Duration twEarly = 0,
                Duration twLate = 0,
+               Duration releaseTime = 0,
                Cost prize = 0,
                bool required = true);
     };
diff --git a/pyvrp/cpp/ProblemData_bindings.cpp b/pyvrp/cpp/ProblemData_bindings.cpp
index 07d28d4..492f5f6 100644
--- a/pyvrp/cpp/ProblemData_bindings.cpp
+++ b/pyvrp/cpp/ProblemData_bindings.cpp
@@ -8,13 +8,22 @@ namespace py = pybind11;
 PYBIND11_MODULE(_ProblemData, m)
 {
     py::class_<ProblemData::Client>(m, "Client")
-        .def(py::init<Value, Value, Value, Value, Value, Value, Value, bool>(),
+        .def(py::init<Value,
+                      Value,
+                      Value,
+                      Value,
+                      Value,
+                      Value,
+                      Value,
+                      Value,
+                      bool>(),
              py::arg("x"),
              py::arg("y"),
              py::arg("demand") = 0,
              py::arg("service_duration") = 0,
              py::arg("tw_early") = 0,
              py::arg("tw_late") = 0,
+             py::arg("release_time") = 0,
              py::arg("prize") = 0,
              py::arg("required") = true)
         .def_property_readonly(
@@ -39,6 +48,10 @@ PYBIND11_MODULE(_ProblemData, m)
                                [](ProblemData::Client const &client) {
                                    return client.twLate.get();
                                })
+        .def_property_readonly("release_time",
+                               [](ProblemData::Client const &client) {
+                                   return client.releaseTime.get();
+                               })
         .def_property_readonly("prize",
                                [](ProblemData::Client const &client) {
                                    return client.prize.get();
diff --git a/pyvrp/cpp/Solution.cpp b/pyvrp/cpp/Solution.cpp
index 14bdbc7..7c6bd66 100644
--- a/pyvrp/cpp/Solution.cpp
+++ b/pyvrp/cpp/Solution.cpp
@@ -203,7 +203,10 @@ Solution::Route::Route(ProblemData const &data,
     if (visits_.empty())
         return;
 
-    Duration time = data.depot().twEarly;
+    for (size_t idx = 0; idx != size(); ++idx)
+        release_ = std::max(release_, data.client(visits_[idx]).releaseTime);
+
+    Duration time = std::max(release_, data.depot().twEarly);
     int prevClient = 0;
 
     for (size_t idx = 0; idx != size(); ++idx)
@@ -284,6 +287,8 @@ Duration Solution::Route::timeWarp() const { return timeWarp_; }
 
 Duration Solution::Route::waitDuration() const { return wait_; }
 
+Duration Solution::Route::releaseTime() const { return release_; }
+
 Cost Solution::Route::prizes() const { return prizes_; }
 
 std::pair<double, double> const &Solution::Route::centroid() const
diff --git a/pyvrp/cpp/Solution.h b/pyvrp/cpp/Solution.h
index 3205d96..39ee7f8 100644
--- a/pyvrp/cpp/Solution.h
+++ b/pyvrp/cpp/Solution.h
@@ -32,6 +32,7 @@ public:
         Duration service_ = 0;   // Total service duration on this route
         Duration timeWarp_ = 0;  // Total time warp on this route
         Duration wait_ = 0;      // Total waiting duration on this route
+        Duration release_ = 0;   // Release time of this route
         Cost prizes_ = 0;        // Total value of prizes on this route
 
         std::pair<double, double> centroid_;  // center of the route
@@ -55,6 +56,7 @@ public:
         [[nodiscard]] Duration serviceDuration() const;
         [[nodiscard]] Duration timeWarp() const;
         [[nodiscard]] Duration waitDuration() const;
+        [[nodiscard]] Duration releaseTime() const;
         [[nodiscard]] Cost prizes() const;
 
         [[nodiscard]] std::pair<double, double> const &centroid() const;
diff --git a/pyvrp/cpp/Solution_bindings.cpp b/pyvrp/cpp/Solution_bindings.cpp
index b738d72..e984ed7 100644
--- a/pyvrp/cpp/Solution_bindings.cpp
+++ b/pyvrp/cpp/Solution_bindings.cpp
@@ -41,6 +41,10 @@ PYBIND11_MODULE(_Solution, m)
              [](Solution::Route const &route) {
                  return route.waitDuration().get();
              })
+        .def("release_time",
+             [](Solution::Route const &route) {
+                 return route.releaseTime().get();
+             })
         .def("prizes",
              [](Solution::Route const &route) { return route.prizes().get(); })
         .def("centroid", &Solution::Route::centroid)
diff --git a/pyvrp/cpp/TimeWindowSegment.h b/pyvrp/cpp/TimeWindowSegment.h
index 3622cc6..cfee152 100644
--- a/pyvrp/cpp/TimeWindowSegment.h
+++ b/pyvrp/cpp/TimeWindowSegment.h
@@ -8,12 +8,13 @@ class TimeWindowSegment
 {
     using TWS = TimeWindowSegment;
 
-    int idxFirst = 0;       // Index of the first client in the segment
-    int idxLast = 0;        // Index of the last client in the segment
-    Duration duration = 0;  // Total duration, incl. waiting and servicing
-    Duration timeWarp = 0;  // Cumulative time warp
-    Duration twEarly = 0;   // Earliest visit moment of first client
-    Duration twLate = 0;    // Latest visit moment of last client
+    int idxFirst = 0;          // Index of the first client in the segment
+    int idxLast = 0;           // Index of the last client in the segment
+    Duration duration = 0;     // Total duration, incl. waiting and servicing
+    Duration timeWarp = 0;     // Cumulative time warp
+    Duration twEarly = 0;      // Earliest visit moment of first client
+    Duration twLate = 0;       // Latest visit moment of first client
+    Duration releaseTime = 0;  // Earliest allowed moment to leave the depot
 
     [[nodiscard]] inline TWS merge(Matrix<Duration> const &durationMatrix,
                                    TWS const &other) const;
@@ -39,7 +40,8 @@ public:
                              Duration duration,
                              Duration timeWarp,
                              Duration twEarly,
-                             Duration twLate);
+                             Duration twLate,
+                             Duration releaseTime);
 };
 
 TimeWindowSegment TimeWindowSegment::merge(
@@ -59,7 +61,8 @@ TimeWindowSegment TimeWindowSegment::merge(
             duration + other.duration + arcDuration + diffWait,
             timeWarp + other.timeWarp + diffTw,
             std::max(other.twEarly - diff, twEarly) - diffWait,
-            std::min(other.twLate - diff, twLate) + diffTw};
+            std::min(other.twLate - diff, twLate) + diffTw,
+            std::max(releaseTime, other.releaseTime)};
 #endif
 }
 
@@ -82,20 +85,25 @@ TimeWindowSegment TimeWindowSegment::merge(
 #endif
 }
 
-Duration TimeWindowSegment::totalTimeWarp() const { return timeWarp; }
+Duration TimeWindowSegment::totalTimeWarp() const
+{
+    return timeWarp + std::max<Duration>(releaseTime - twLate, 0);
+}
 
 TimeWindowSegment::TimeWindowSegment(int idxFirst,
                                      int idxLast,
                                      Duration duration,
                                      Duration timeWarp,
                                      Duration twEarly,
-                                     Duration twLate)
+                                     Duration twLate,
+                                     Duration releaseTime)
     : idxFirst(idxFirst),
       idxLast(idxLast),
       duration(duration),
       timeWarp(timeWarp),
       twEarly(twEarly),
-      twLate(twLate)
+      twLate(twLate),
+      releaseTime(releaseTime)
 {
 }
 
diff --git a/pyvrp/cpp/TimeWindowSegment_bindings.cpp b/pyvrp/cpp/TimeWindowSegment_bindings.cpp
index 0a266d5..f4736e2 100644
--- a/pyvrp/cpp/TimeWindowSegment_bindings.cpp
+++ b/pyvrp/cpp/TimeWindowSegment_bindings.cpp
@@ -22,13 +22,14 @@ template <typename... Args> TWS merge(Matrix<int> const &mat, Args... args)
 PYBIND11_MODULE(_TimeWindowSegment, m)
 {
     py::class_<TWS>(m, "TimeWindowSegment")
-        .def(py::init<int, int, int, int, int, int>(),
+        .def(py::init<int, int, Value, Value, Value, Value, Value>(),
              py::arg("idx_first"),
              py::arg("idx_last"),
              py::arg("duration"),
              py::arg("time_warp"),
              py::arg("tw_early"),
-             py::arg("tw_late"))
+             py::arg("tw_late"),
+             py::arg("release_time"))
         .def("total_time_warp",
              [](TWS const &tws) { return tws.totalTimeWarp().get(); })
         .def_static("merge",
diff --git a/pyvrp/cpp/search/LocalSearch.cpp b/pyvrp/cpp/search/LocalSearch.cpp
index 8b659ce..d2e68db 100644
--- a/pyvrp/cpp/search/LocalSearch.cpp
+++ b/pyvrp/cpp/search/LocalSearch.cpp
@@ -286,7 +286,8 @@ void LocalSearch::loadSolution(Solution const &solution)
                               data.client(client).serviceDuration,
                               0,
                               data.client(client).twEarly,
-                              data.client(client).twLate};
+                              data.client(client).twLate,
+                              data.client(client).releaseTime};
 
         clients[client].route = nullptr;  // nullptr implies "not in solution"
     }
diff --git a/pyvrp/plotting/plot_route_schedule.py b/pyvrp/plotting/plot_route_schedule.py
index bf8108d..012a1d6 100644
--- a/pyvrp/plotting/plot_route_schedule.py
+++ b/pyvrp/plotting/plot_route_schedule.py
@@ -47,9 +47,7 @@ def plot_route_schedule(
     horizon = depot.tw_late - depot.tw_early
 
     # Initialise tracking variables
-    t = 0
-    wait_time = 0
-    time_warp = 0
+    t = route.release_time()
     drive_time = 0
     serv_time = 0
     dist = 0
@@ -89,12 +87,10 @@ def plot_route_schedule(
         add_traces(dist, t, drive_time, serv_time, load)
 
         if t < stop.tw_early:
-            wait_time += stop.tw_early - t
             t = stop.tw_early
 
         slack = min(slack, stop.tw_late - t)
         if t > stop.tw_late:
-            time_warp += t - stop.tw_late
             timewarp_lines.append(((dist, t), (dist, stop.tw_late)))
             t = stop.tw_late
 
diff --git a/pyvrp/read.py b/pyvrp/read.py
index 1f5dd67..33a53d7 100644
--- a/pyvrp/read.py
+++ b/pyvrp/read.py
@@ -134,6 +134,11 @@ def read(
         service_times = np.zeros(dimension, dtype=int)
         time_windows = np.zeros((dimension, 2), dtype=int)
 
+    if "release_time" in instance:
+        release_times: np.ndarray = round_func(instance["release_time"])
+    else:
+        release_times = np.zeros(dimension, dtype=int)
+
     prizes = round_func(instance.get("prize", np.zeros(dimension, dtype=int)))
 
     # Checks
@@ -152,6 +157,9 @@ def read(
     if service_times[0] != 0:
         raise ValueError("Depot service duration must be 0")
 
+    if release_times[0] != 0:
+        raise ValueError("Depot release time must be 0")
+
     if (time_windows[:, 0] > time_windows[:, 1]).any():
         raise ValueError("Time window cannot start after end")
 
@@ -163,6 +171,7 @@ def read(
             service_times[idx],
             time_windows[idx][0],  # TW early
             time_windows[idx][1],  # TW late
+            release_times[idx],
             prizes[idx],
             np.isclose(prizes[idx], 0),  # required only when prize is zero
         )


Test patch:
diff --git a/pyvrp/tests/data/NonZeroDepotReleaseTime.txt b/pyvrp/tests/data/NonZeroDepotReleaseTime.txt
new file mode 100644
index 0000000..3b29234
--- /dev/null
+++ b/pyvrp/tests/data/NonZeroDepotReleaseTime.txt
@@ -0,0 +1,33 @@
+NAME : TEST
+DIMENSION : 3
+EDGE_WEIGHT_TYPE : EXPLICIT
+EDGE_WEIGHT_FORMAT : FULL_MATRIX
+CAPACITY : 100
+NODE_COORD_SECTION
+1	2334	726
+2	226	1297
+3	590	530
+EDGE_WEIGHT_SECTION
+0	1544	1944
+1726	0	1992
+1965	1975	0
+DEMAND_SECTION
+1 0
+2 5
+3 5
+TIME_WINDOW_SECTION
+1 0 50
+2 10 50
+3 10 50
+RELEASE_TIME_SECTION
+1 10
+2 10
+3 10
+SERVICE_TIME_SECTION
+1 0
+2 5
+3 5
+DEPOT_SECTION
+1
+-1
+EOF
diff --git a/pyvrp/tests/data/OkSmallReleaseTimes.txt b/pyvrp/tests/data/OkSmallReleaseTimes.txt
new file mode 100644
index 0000000..cc7f28b
--- /dev/null
+++ b/pyvrp/tests/data/OkSmallReleaseTimes.txt
@@ -0,0 +1,47 @@
+NAME : TEST
+COMMENT : Small problem instance with four customers
+DIMENSION : 5
+EDGE_WEIGHT_TYPE : EXPLICIT
+EDGE_WEIGHT_FORMAT : FULL_MATRIX
+CAPACITY : 10
+VEHICLES : 3
+NODE_COORD_SECTION
+1    2334   726
+2    226    1297
+3    590    530
+4    435    718
+5    1191   639
+EDGE_WEIGHT_SECTION
+0     1544  1944  1931  1476
+1726     0  1992  1427  1593
+1965  1975     0  621   1090
+2063  1433   647  0     818
+1475  1594  1090  828   0
+DEMAND_SECTION
+1    0
+2    5
+3    5
+4    3
+5    5
+TIME_WINDOW_SECTION
+1    0      45000
+2    15600  22500
+3    12000  19500
+4    8400   15300
+5    12000  19500
+SERVICE_TIME_SECTION
+1    0
+2    360
+3    360
+4    420
+5    360
+RELEASE_TIME_SECTION
+1    0
+2    20000
+3    5000
+4    5000
+5    1000
+DEPOT_SECTION
+1
+-1
+EOF
diff --git a/pyvrp/tests/test_Model.py b/pyvrp/tests/test_Model.py
index d7b4131..a2101c3 100644
--- a/pyvrp/tests/test_Model.py
+++ b/pyvrp/tests/test_Model.py
@@ -68,7 +68,8 @@ def test_add_client_attributes():
         service_duration=4,
         tw_early=5,
         tw_late=6,
-        prize=7,
+        release_time=7,
+        prize=8,
         required=False,
     )
 
@@ -78,7 +79,8 @@ def test_add_client_attributes():
     assert_equal(client.service_duration, 4)
     assert_equal(client.tw_early, 5)
     assert_equal(client.tw_late, 6)
-    assert_equal(client.prize, 7)
+    assert_equal(client.release_time, 7)
+    assert_equal(client.prize, 8)
     assert_(not client.required)
 
 
diff --git a/pyvrp/tests/test_ProblemData.py b/pyvrp/tests/test_ProblemData.py
index 51fe069..86c65f0 100644
--- a/pyvrp/tests/test_ProblemData.py
+++ b/pyvrp/tests/test_ProblemData.py
@@ -8,14 +8,15 @@ from pyvrp.tests.helpers import read
 
 
 @mark.parametrize(
-    "x,y,demand,service_duration,tw_early,tw_late,prize",
+    "x,y,demand,service_duration,tw_early,tw_late,release_time,prize",
     [
-        (1, 1, 1, 1, 0, 1, 0),  # normal
-        (1, 1, 1, 0, 0, 1, 0),  # zero duration
-        (1, 1, 0, 1, 0, 1, 0),  # zero demand
-        (1, 1, 1, 1, 0, 0, 0),  # zero length time interval
-        (-1, -1, 1, 1, 0, 1, 0),  # negative coordinates
-        (0, 0, 1, 1, 0, 1, 1),  # positive prize
+        (1, 1, 1, 1, 0, 1, 0, 0),  # normal
+        (1, 1, 1, 0, 0, 1, 0, 0),  # zero duration
+        (1, 1, 0, 1, 0, 1, 0, 0),  # zero demand
+        (1, 1, 1, 1, 0, 0, 0, 0),  # zero length time interval
+        (-1, -1, 1, 1, 0, 1, 0, 0),  # negative coordinates
+        (1, 1, 1, 1, 0, 1, 1, 0),  # positive release time
+        (0, 0, 1, 1, 0, 1, 0, 1),  # positive prize
     ],
 )
 def test_client_constructor_initialises_data_fields_correctly(
@@ -25,38 +26,43 @@ def test_client_constructor_initialises_data_fields_correctly(
     service_duration: int,
     tw_early: int,
     tw_late: int,
+    release_time: int,
     prize: int,
 ):
-    client = Client(x, y, demand, service_duration, tw_early, tw_late, prize)
+    client = Client(
+        x, y, demand, service_duration, tw_early, tw_late, release_time, prize
+    )
     assert_allclose(client.x, x)
     assert_allclose(client.y, y)
     assert_allclose(client.demand, demand)
     assert_allclose(client.service_duration, service_duration)
     assert_allclose(client.tw_early, tw_early)
     assert_allclose(client.tw_late, tw_late)
+    assert_allclose(client.release_time, release_time)
     assert_allclose(client.prize, prize)
 
 
 @mark.parametrize(
-    "x,y,demand,service_duration,tw_early,tw_late,prize",
+    "x,y,demand,service,tw_early,tw_late,release_time,prize",
     [
-        (1, 1, 1, 1, 1, 0, 0),  # late < early
-        (1, 1, 1, -1, 0, 1, 0),  # negative duration
-        (1, 1, -1, 1, 0, 1, 0),  # negative demand
-        (1, 1, 1, 1, 0, 1, -1),  # negative prize
+        (1, 1, 1, 1, 1, 0, 0, 0),  # late < early
+        (1, 1, 1, -1, 0, 1, 0, 0),  # negative service duration
+        (1, 1, -1, 1, 0, 1, 0, 0),  # negative demand
+        (1, 1, 1, 1, 0, 1, 0, -1),  # negative prize
     ],
 )
 def test_raises_for_invalid_client_data(
     x: int,
     y: int,
     demand: int,
-    service_duration: int,
+    service: int,
     tw_early: int,
     tw_late: int,
+    release_time: int,
     prize: int,
 ):
     with assert_raises(ValueError):
-        Client(x, y, demand, service_duration, tw_early, tw_late, prize)
+        Client(x, y, demand, service, tw_early, tw_late, release_time, prize)
 
 
 def test_depot_is_first_client():
diff --git a/pyvrp/tests/test_Solution.py b/pyvrp/tests/test_Solution.py
index c7f9f30..6e46ca7 100644
--- a/pyvrp/tests/test_Solution.py
+++ b/pyvrp/tests/test_Solution.py
@@ -176,6 +176,26 @@ def test_feasibility():
     assert_(not sol.has_time_warp())
 
 
+def test_feasibility_release_times():
+    data = read("data/OkSmallReleaseTimes.txt")
+
+    # Client 1 is released at 20'000, but client 2 time window ends at 19'500,
+    # so this solution must be infeasible due to time-warping. We arrive at
+    # client 1 at time 20'000 + 1'544 = 21'544 before the TW closes (22'500).
+    # We arrive at client 2 at 21'544 + 360 + 1'992 = 23'896, so we incur a
+    # time warp of 23'896 - 19'500 = 4'396.
+    sol = Solution(data, [[1, 2], [3], [4]])
+    assert_(not sol.is_feasible())
+    assert_equal(sol.time_warp(), 4396)
+
+    # Visiting clients 2 and 3 together is feasible: both clients are released
+    # at time 5'000. We arrive at client 2 at 5'000 + 1'944 and wait till the
+    # TW opens (12'000). We arrive at client 3 at 12'000 + 360 + 621 = 12'981,
+    # which is before the TW closes (15'300).
+    sol = Solution(data, [[1], [2, 3], [4]])
+    assert_(sol.is_feasible())
+
+
 def test_distance_calculation():
     data = read("data/OkSmall.txt")
 
@@ -290,6 +310,18 @@ def test_route_time_warp_and_wait_duration():
     assert_equal(routes[1].wait_duration(), 12_000 - 1_944)
 
 
+def test_route_release_time():
+    data = read("data/OkSmallReleaseTimes.txt")
+    sol = Solution(data, [[1, 3], [2, 4]])
+    routes = sol.get_routes()
+
+    # The client release times are 20'000, 5'000, 5'000 and 1'000.
+    # So the first route has a release time of max(20'000, 5'000) = 20'000,
+    # and the second route has a release time of max(5'000, 1'000) = 5'000.
+    assert_allclose(routes[0].release_time(), 20000)
+    assert_allclose(routes[1].release_time(), 5000)
+
+
 @mark.parametrize(
     "dist_mat",
     [
diff --git a/pyvrp/tests/test_TimeWindowSegment.py b/pyvrp/tests/test_TimeWindowSegment.py
index 0a520dd..219999a 100644
--- a/pyvrp/tests/test_TimeWindowSegment.py
+++ b/pyvrp/tests/test_TimeWindowSegment.py
@@ -7,13 +7,13 @@ from pyvrp._TimeWindowSegment import TimeWindowSegment
 
 @mark.parametrize("existing_time_warp", [2, 5, 10])
 def test_total_time_warp(existing_time_warp):
-    tws1 = TimeWindowSegment(0, 0, 0, existing_time_warp, 0, 0)
+    tws1 = TimeWindowSegment(0, 0, 0, existing_time_warp, 0, 0, 0)
     assert_equal(tws1.total_time_warp(), existing_time_warp)
 
 
 def test_merge_two():
-    tws1 = TimeWindowSegment(0, 0, 5, 0, 0, 5)
-    tws2 = TimeWindowSegment(1, 1, 0, 5, 3, 6)
+    tws1 = TimeWindowSegment(0, 0, 5, 0, 0, 5, 0)
+    tws2 = TimeWindowSegment(1, 1, 0, 5, 3, 6, 0)
 
     mat = Matrix([[1, 4], [1, 2]])
     merged = TimeWindowSegment.merge(mat, tws1, tws2)
@@ -26,11 +26,17 @@ def test_merge_two():
     # time window. So we get a final time warp of 5 + 3 = 8.
     assert_equal(merged.total_time_warp(), 8)
 
+    # Now, let's add a bit of release time (3), so that the total time warp
+    # should become 8 + 3 = 11.
+    tws2 = TimeWindowSegment(1, 1, 0, 5, 3, 6, 3)
+    merged = TimeWindowSegment.merge(mat, tws1, tws2)
+    assert_equal(merged.total_time_warp(), 11)
+
 
 def test_merge_multiple():
-    tws1 = TimeWindowSegment(0, 0, 5, 0, 0, 5)
-    tws2 = TimeWindowSegment(1, 1, 0, 0, 3, 6)
-    tws3 = TimeWindowSegment(2, 2, 0, 0, 2, 3)
+    tws1 = TimeWindowSegment(0, 0, 5, 0, 0, 5, 0)
+    tws2 = TimeWindowSegment(1, 1, 0, 0, 3, 6, 0)
+    tws3 = TimeWindowSegment(2, 2, 0, 0, 2, 3, 2)
 
     mat = Matrix([[1, 4, 1], [1, 2, 4], [1, 1, 1]])
     merged1 = TimeWindowSegment.merge(mat, tws1, tws2)
@@ -41,8 +47,9 @@ def test_merge_multiple():
     assert_equal(merged3.total_time_warp(), merged2.total_time_warp())
 
     # After also merging in tws3, we should have 3 time warp from 0 -> 1, and 7
-    # time warp from 1 -> 2, for 10 total time warp.
-    assert_equal(merged3.total_time_warp(), 10)
+    # time warp from 1 -> 2. Since there's also a release time of 2, the total
+    # time warp is 12.
+    assert_equal(merged3.total_time_warp(), 12)
 
 
 # TODO test two previously merged segments, e.g. merge(merge(1, 2),
diff --git a/pyvrp/tests/test_read.py b/pyvrp/tests/test_read.py
index ec236c0..cf262fe 100644
--- a/pyvrp/tests/test_read.py
+++ b/pyvrp/tests/test_read.py
@@ -16,6 +16,7 @@ from pyvrp.tests.helpers import read
         ("data/MoreThanOneDepot.txt", ValueError),
         ("data/NonZeroDepotServiceDuration.txt", ValueError),
         ("data/NonZeroDepotOpenTimeWindow.txt", ValueError),
+        ("data/NonZeroDepotReleaseTime.txt", ValueError),
         ("data/NonZeroDepotDemand.txt", ValueError),
         ("data/TimeWindowOpenLargerThanClose.txt", ValueError),
         ("data/EdgeWeightsNoExplicit.txt", ValueError),
@@ -124,11 +125,14 @@ def test_reading_En22k4_instance():  # instance from CVRPLIB
     assert_equal(data.dist(0, 1), 493)
     assert_equal(data.dist(1, 0), 493)
 
-    # This is a CVRP instance, so time window data should all be zeroed out.
+    # This is a CVRP instance, so all other fields should have default values.
     for client in range(data.num_clients + 1):  # incl. depot
         assert_equal(data.client(client).service_duration, 0)
         assert_equal(data.client(client).tw_early, 0)
         assert_equal(data.client(client).tw_late, 0)
+        assert_equal(data.client(client).release_time, 0)
+        assert_equal(data.client(client).prize, 0)
+        assert_equal(data.client(client).required, True)
 
 
 def test_reading_RC208_instance():  # Solomon style instance
@@ -167,6 +171,12 @@ def test_reading_RC208_instance():  # Solomon style instance
     for client in range(1, data.num_clients + 1):  # excl. depot
         assert_equal(data.client(client).service_duration, 100)
 
+    # This is a VRPTW instance, so all other fields should have default values.
+    for client in range(data.num_clients + 1):  # incl. depot
+        assert_equal(data.client(client).release_time, 0)
+        assert_equal(data.client(client).prize, 0)
+        assert_equal(data.client(client).required, True)
+
 
 def test_warns_about_scaling_issues(recwarn):
     # But 100 million is too large. That's really close to INT_MAX, and might