Maximum trip duration
In the Vehicle Routing Problem (VRP), a trip refers to the sequence of nodes visited by a single vehicle, starting from the depot and ending back at the depot. A route can consist of one or more trips, especially when dealing with constraints like maximum trip duration or vehicle capacity. The maximum trip duration constraint limits the total time a vehicle can spend on a single trip.
Maximum Trip Duration:
The maximum trip duration constraint sets an upper limit on the total time a vehicle can be "on the road" during a single trip. This time includes travel time between nodes, service time at each node (e.g., loading/unloading, delivery time), and any other time spent by the vehicle during its route. This constraint is often imposed due to factors like driver working hours regulations, vehicle operating hours, or the perishable nature of the goods being transported.
Trips in the VRP:
A trip, as mentioned earlier, is a continuous sequence of node visits by a single vehicle, beginning and ending at the depot. A vehicle may make multiple trips during its working day, returning to the depot to reload or for driver breaks. Each trip must adhere to the maximum trip duration constraint. A route, therefore, can be composed of one or more trips.
The Relationship Between Maximum Trip Duration and Trips:
The maximum trip duration constraint directly limits the length and complexity of individual trips. It dictates how many nodes a vehicle can realistically serve within a single trip.
Here's how they relate:
- Trip duration must respect the limit: The total time spent by a vehicle on a trip cannot exceed the maximum trip duration.
- Trip length is constrained by duration: The number of nodes that can be visited on a single trip is limited by the maximum trip duration.
- Multiple trips may be required: If the total service time and travel time required to serve all customers exceeds the maximum trip duration, the vehicle will need to make multiple trips.
- Trip duration impacts route planning: The maximum trip duration constraint must be considered when designing routes to ensure feasibility.
Example:
Imagine a delivery company with a maximum trip duration of 8 hours for its drivers. A driver starts at the depot, visits several customers, and returns to the depot. The total time spent on this sequence of visits, including travel time between customers and delivery time at each customer location, must be less than or equal to 8 hours. If the total time exceeds 8 hours, the driver must return to the depot before serving all customers, effectively splitting the route into multiple trips.
SWAT model supports setting this constraint:
Playground
You can try out the Maximum Trip Duration concept using the playground below.
The example defines a vehicle with a max_trip_duration of 3600 seconds (1 hour).
Try adding more nodes or adjusting the duration to see how it affects the route.