Early Start and ASAP Service

[tklie]

Hello,

I am trying to solve a VRP for a use case, where all vehicles always start their daily route at a given time and should service each job as fast as possible, as additional jobs may be added during the course of the day. This means, that in addition to minimizing travel distance and duration, I also need to minimize the delay at which a vehicle arrives at / services a job after the earliest possible time.

Example

In this example, the vehicle starts at about 30 minutes distance from the jobs, but the three jobs are very close together, with Job 1 being closest, then 2 and 3.

Vehicle: 08:00 - 16:00

Job 1:   09:00 - 16:00
Job 2:   14:00 - 14:15
Job 3:   13:00 - 14:30

Route:   Vehicle ------------------------> Job 1 ---> Job 2 ---> Job 3

Current behaviour (approx.) minimizing cost (travel time):

Vehicle starts route at 13:25

Arrive  Job 1 at 13:55
Service Job 1 at 13:55

Arrive  Job 2 at 14:00
Service Job 2 at 14:00

Arrive  Job 3 at 14:05
Service Job 3 at 14:05

Desired behaviour:

Vehicle starts route at 08:00 (fixed)

Arrive  Job 1 at 08:30
Service Job 1 at 09:00 (after 30min wait)

Arrive  Job 3 at 09:05
Service Job 3 at 13:00 (after 3h 55min wait)

Arrive  Job 2 at 13:05
Service Job 2 at 14:00 (after 55min wait)

Background

First of, this reduces the risk of violating appointments, i.e. Job 2 has a very narrow time window with 14:00 - 14:15. Arriving at Job 2 early and waiting for 55 minutes is preferable to planning an arrival at 14:00 and then getting stuck in traffic with only 15 minutes left on the clock.

In addition, this allows for adding jobs dynamically during the course of the day. If new jobs come in while the vehicle is waiting for almost 4 hours as Job 3, I can let the vehicle quickly service these new nearby jobs in the meantime. This wouldn't be possible if the vehicle waited until 13:30 to start its route.

This is not to say that long waiting times are desirable. However, it is more preferable to have the vehicle enter its service region than to not start the route at all. Optimizing for low service delays would even help in reducing waiting times (as we often have scenarios like Job 2 and 3, where the current implementation prefers waiting until 14:00 at Job 2 and then driving to Job 3 afterwards because this reduces overall travel time, even though this drastically increases waiting time, which is suboptimal for vehicle utilization).

Feature

Of course, all this cannot break the current optimization goals. I'm imagining an optional parameter on the vehicle to force a fixed start time and/or maybe a new property on the vehicle's costs object to define a penalty (e.g. service_delay) for each second that a job is serviced after its earliest possible time, and/or maybe even an additional property to penalize waiting_time.

Do you think any of this lies in the realm of possibilty? Thanks in advance and kind regards

[jcoupey]

Optimizing for operational cost (current behavior) and optimizing for "low service delays" are very different objectives. They also are often conflicting in the sense that you can get a solution that is good on operational costs but arbitrarily poor on the "service delay" (see your example). On the other hand, the optimal solution wrt to "service delay" can be arbitrarily bad in term of operational cost. Think of a situation with $n$ jobs that have the same time window start: the optimal solution in term of service delay is to get zero delay by sending $n$ vehicles perform each a single job right on time, no matter how close those jobs are.

Of course the point of using a "penalty" cost is precisely to try to blend those conflicting objectives into a single one. Unfortunately that's not something we could easily do:

1. Having an additional layer of ponderation involves some tuning that sounds totally non-trivial. You'd have to translate the subjective "it is more preferable" to actual factors. How much you're prepared to degrade the solution quality (as seen from the usual cost we have) would in fact have to account for things that are not known when submitting the problem, e.g. jobs that will show up in the future somewhere.
2. We don't store actual task times while solving, we only deal with earliest and latest dates for each task to account for validity. This allows to speed-up a lot of things internally, but then some things are only decided when formatting the chosen solution. Among those: actual task ETA (hence service delays), exact waiting times.

Point 1 is mostly a concern about the suggested approach, point 2 is a blocker on a technical level.

See also #466.