Maximum travel time and/or distance per tour

[sebhoerl]

We currently have a use case where we look at cargo bikes that are placed at a central depot to perform deliveries. The idea is that they can do as many tours as necessary during one day, but that their range / travel time is limited per tour. The assumption is that the riders will be active all day, but they can swap batteries in the depot.

I have an implementation for that with two contributions:

• A depot_index is defined per vehicle, defining at which spot tours start and end (and this probably only makes sense in combination with start_index and end_index). This is necessary, because otherwise there is no notion of what is a "tour".
• A max_travel_time_per_tour is introduced that limits the time that can be spent traveling between two subsequent visits of the depot_index.

I'm not sure if this is a relevant point on your roadmap, please let me know if I should send a PR with this. The code is here, and the main change is in RawRoute: master...sebhoerl:vroom:max_tour_travel_time

Update 22 January 2024: See fruther below, there is a more straight-forward and more correct implementation now.

I haven't been writing C++ in quite a while, so this was an interesting exercise to catch up a bit, but clearly there may be room for improvement ;-) I tested it on some of our small test instances (large runs yet to come). I'm not really familar with C++ project setups, I assume there are unit tests somewhere, but not sure how to run them :)

[sebhoerl]

Here is a small example with a vehicle being located at the depot and two pickup/delivery tasks. In the default case the solution will have a total travel time of 3000 with the following route:

Depot > Pickup > Pickup > [1000 TT] > Dropoff >  [1000 TT] > Dropoff > [1000 TT] > Depot

If you set max_travel_time_per_tour to 2500, the total travel time will be 4000 with the following route:

Depot > Pickup > [1000 TT] > Dropoff >  [1000 TT] > Depot > Pickup >  [1000 TT] > Dropoff > [1000 TT] > Depot

So the vehicle goes back to the depot in between to avoid a tour with travel time 3000 as in the initial case.

Instance:
{ "shipments": [ { "pickup": { "id": 0, "location_index": 2, "service": 10 }, "delivery": { "id": 0, "location_index": 0, "service": 10 } }, { "pickup": { "id": 1, "location_index": 2, "service": 10 }, "delivery": { "id": 1, "location_index": 1, "service": 10 } } ], "vehicles": [ { "id": 0, "start_index": 2, "end_index": 2, "profile": "vt", "max_travel_time_per_tour": 4500, "depot_index": 2 } ], "matrices": { "vt": { "costs": [ [ 0, 10, 10], [ 10, 0, 10], [ 10, 10, 0] ], "durations": [ [ 0, 1000, 1000 ], [ 1000, 0, 1000 ], [ 1000, 1000, 0 ] ] } } }

[jcoupey]

This is an interesting use-case and need, thanks for sharing your work on it! I took a quick look at your branch diff and you got the overall picture right: store additional data required for validity checks, implement validity checks for this new constraint, add the relevant new checks wherever needed (heuristic, local search etc.).

One first limitation I can see for including this is that it will currently introduce some computing overhead (checks and data updates) for all situations, even when this constraint is not used at all. This could be evaluated using the usual benchmarks and there are probably ways around that.

I'm also a bit puzzled about how this could be exposed in a more generic way in term of API.

A depot_index is defined per vehicle,

We have no notion of depot so introducing a depot_index matches your need in this specific situation but does not sound "right" in general.

this probably only makes sense in combination with start_index and end_index

Probably less of concern as it could be changed, but we can't really ship a new feature that is only usable if you provide your own matrices and *_index values.

I assume there are unit tests somewhere

Nope, we use several benchmark classes and typical instances as functional and non-regression tests, see https://github.com/VROOM-Project/vroom#functional-tests. I would advise in that regard to add assertions on validity for the new constraint in the route formatting process.

[RichAth]

This is a great implementation. Thanks for sharing. I have a unique use case which I am trying to solve. We have quarry trucks that pickup quarry material from different quarries and then deliver it to construction sites. In our instance it's always a pickup followed by a delivery because the capacity of the truck is always filled at every pickup. Km travelled fully loaded is quite important to us.

One thing I have been trying to achieve is limit the max travel time from delivery to next pickup location, and/or preferring shipments (pickup->delivery) where the duration to the pickup from the current location is smaller than the duration from that pickup to it's delivery. In understanding that the latter is a more complicated task. Would either of you have any suggestions on how to limit the max travel time from delivery to next pickup location?

Similarly any advice on how to possibly achieve preferring shipments (pickup->delivery) where the duration to the pickup from the current location is smaller than the duration from that pickup to it's delivery :)

[jcoupey]

Km travelled fully loaded is quite important to us.

Well, if trucks are always filled at every pickup, then if all shipments are assigned there is nothing to optimize in term of fully loaded distance as it is fixed by the pickup->delivery legs.

limit the max travel time from delivery to next pickup

Since the pickup->delivery legs are fixed and all separated, the travel time from deliveries to next pickup is all that is left to optimize, so this should happen out of the box.

the duration to the pickup from the current location is smaller than the duration from that pickup to it's delivery

Not sure I get this correctly, maybe there is a business rule behind this?

All in all, I'm not sure this has much to do with the initial "travel time per tour" topic, maybe we should move that discussion to a dedicated ticket?

[sebhoerl]

@jcoupey Coming back to the initial topic, I was thinking that it would be nice to include this somehow in the main stream of VROOM as we are using this feature quite a lot, but we are a bit stuck with the version back then. What about these two options:

• Define a max_travel_time_after_pickup: Means that we don't care where is the depot. In our case, the pickup is always at the same place, so implicitly this will work. We only limit the travel time after each pickup.

• Define a max_travel_time_from_start: We interpret the vehicle start location as the depot and apply a travel time constraint that is reset whenever the vehicle visits the start location.

Both would produce the behaviour that we want without defining explicitly a depot_index. Alternatively, we could also introduce a depot_location per vehicle that works similarly as the start location given in coordinates, i.e., it is mapped automatically. It is only tricky then to identify which pickups are at the depot, because we would compare by float coordinates.

[jcoupey]

@sebhoerl thanks for coming up with alternative suggestions, it is indeed a good approach to try and get something as generic as possible. My main concern about this is that accounting for a specific situation, albeit in a more generic way, could fall short for slightly different use-cases. We don't want to hard-code some specific assumptions in the solving approach because we'd implement something too targeted and would then be stuck for anything beyond that.

Define a max_travel_time_after_pickup

Relies on the assumption that "the pickup is always at the same place": this constraint would not make much sense in a situation with pickups spread all around. Also would not cover the situation where pickup place and battery-swapping facility are different (e.g. with the symmetric problem where you collect all things to bring them to the depot).

Define a max_travel_time_from_start

Again assumes that the start place has another role beyond just being the first step in the route, which feels wrong in the semantics of the API. Would fall short as soon as someone would come up with a variant:

• start point is different than the pickup facility (think riders starting from home on the first tour);
• autonomy should be reset at the end location, that is different from start (makes sense if you're collecting various things around and bringing everything back to a depot which is then where all deliveries happen);
• autonomy could be (also) reset at an arbitrary given location.

I guess my point is that in order to do things properly we should probably get back to the initial business requirement you expressed in your original post: "they can swap batteries". In your case it happens at a specific point known in the model but the general case is that this could be pretty much anywhere and we don't want to make (too much) assumptions on this.

I realize this is not helping much in the short-term because while the work-around you already have kinda works for your use-case, solving for the bigger picture is actually a much more complex problem.

[sebhoerl]

For those who are interested, I made a new implementation based on 176f57.

It can be found here:
https://github.com/sebhoerl/vroom/tree/tour_constraints

• Previously some operators were destroying the travel time constraint when removing jobs from a vehicle schedule. This is now fixed, the constraints are tested whenever compatibility with time windows is tested.
• This also means that the new code is correct, but only works when you define an overall time window for your vehicle.
• The code now supports to configure both constraints on the vehilce level:
  • max_tour_travel_time: 3600 # in seconds
  • max_tour_distance: 20000 # in meters (or whatever is in your distance matrix
• For the distance constraint to work, you will need to define a distance matrix (otherwise 0 is assumed)

The footprint of this implelmentation has been reduced considerably and the start location of the vehicle is considered as the depot where the distance/travel time constraints are reset.

[sebhoerl]

@jcoupey Not sure what you think of the new version, it is relatively low-key with not a lot of code added. It could become a "hidden" feature for experts, but for you to decide ;) sebhoerl@16e2cbd Probably would make sense to add another if on top to avoid running the calculations all together if no constraints are set. One could probably even hide this from the declaration of TWRoute.

[jcoupey]

@sebhoerl I just checked sebhoerl@16e2cbd which is indeed kind of self-contained and is a straightforward expression of your requirement: you check cumulative duration/distance against the max_tour_* values for any excessive value, while resetting the sums to zero whenever going back to the depot (aka start point).

My main concerns would be:

1. This is still not quite generic as it is based on the max_travel_time_from_start idea from above and thus does not raise concerns from Maximum travel time and/or distance per tour #918 (comment).
2. You're imposing that a vehicle TW is set, while the point of this kind of range constraint is precisely to express a timing restriction in a more flexible way than with a TW. Arguably, this is only a technical limitation related to the fact that you've coupled your new check with the existing TWRoute::is_valid_addition_for_tw.
3. The new TWRoute::check_tour_constraints function has a complexity that is linear in the route size: except if a violation is found on the way, the full route is checked to assert validity. I expect this to have a huge impact on computing times.

That last point is a deep change to the approach we have so far as the current complexity for all validity checks is linear in the size of the inserted range. If you take for example a very simple local search operator as Relocate (try moving one job from a route to another route), then we basically have constant-time checks to decide its validity, including time-wise. The new fonction means adding a lookup through the whole target route just to decide validity. For this simple operator, the big O complexity is one order of magnitude higher.