search

reinterpretcat / vrp

A Vehicle Routing Problem solver
https://reinterpretcat.github.io/vrp/
Apache License 2.0
331 stars 68 forks source link

Vehicle Job Duration #101

Closed arbarlow closed 1 year ago

arbarlow commented 1 year ago

Hi @reinterpretcat , Thanks for all the work on this project so far.

I am wondering how much work you think it might be, to add a multiplier per vehicle for job durations?

We have many drivers of different ability levels, some new and some experienced. We'd like to set their level and then slowly progress them to do faster deliveries.

Whilst the traffic multiplier is available. This can only be used to a certain point, as setting this speed faster than is actually possible, legal or safe is counter productive. If there a large distance between 2 stops (like the distance to the first stop) a percentage multiplier can be very harmful to the correct ETA.

In our case, we want to serve many, fairly quick stops (parcel delivery) and just an extra 30 seconds or a minute per stop can have a huge difference over 50-80 stops, whereas the driving time between those stops should be similar.

I think this would work great with the new compact-tour objective and really help us to hit ETAs.

I'm also happy to help as a Rust user!

reinterpretcat commented 1 year ago

Hi, thanks for feedback!

At the moment, there is no such feature, but it can be added on top with not so big effort (in general). However, there are some corners cases possible which requires clarifications and might need to work differently depending on specific requirements.

Also, you initially wrote "add a multiplier per vehicle for job durations", but later you mentioned " just an extra 30 seconds or a minute per stop". In general, job != stop,=: if jobs have the same locations, there is a change that they will be added to the same stop.

One possible workaround is to preprocess matrices for specific drivers to add extra duration. Then use multiple profiles and assign them accordingly on vehicles. However, it has clearly disadvantages as more matrices needs to be created and they used to be a bit heavy in processing (depending on their size).

arbarlow commented 1 year ago

Sorry for the confusion in terms.

In this context, I'm only referring to job duration, we use the term "stops" as jobs. Hence the confusion.

When it comes to clustering and grouping jobs into a single stop. I'd be happy for those values to remain constant. i.e parking time etc

reinterpretcat commented 1 year ago

Job duration is easier: no need to handle some corners cases (e.g depot stops). It would require adding a new implementation of ActivityCosts trait instead of default:

https://github.com/reinterpretcat/vrp/blob/master/vrp-core/src/models/problem/costs.rs#L36-L40

Code-wise, you would need to have here a mapping from specific Vehicle (available through route.actor.vehicle) and specific job duration (available through activity.job) to desired actual service time.