Associate Cost to Waiting Time

[K-Leon]

Hello, first of thanks for your hard work! I was experimenting a bit with your VRP planner again. While using the TSP Features and optimizing the order in a single route i noticed an issue around waiting times.

If there are time windows floating around and there is a lot of time overall to finish everything, the solver seems to prefer waiting for an hour then doing a few meters more and coming back later. This seems to happen if you have 6 jobs that need to be finished until 13:00 with different start times and one job starting from 14:00. The first 6 jobs aren't processed as fast as possible. This isn't optimal if there will be stops added over the course of the day.

Is there a quick way to modify / influence the cost function to account for waiting time? I would love to have a hint where i could look at :)

[reinterpretcat]

Hi, thanks for feedback!

Have you tried to experiment with costs e.g. make distance higher than duration? Or, additionally, run the solver longer? In general, it is hard to say without looking at problem.

[K-Leon]

Hi, thanks for your fast reply! yes i tried to experiment with it. may i send you an mail? I can provide one including matrix.

I noticed that there is already an internal representation and the cost associated to waiting could be tuned independently.

https://github.com/reinterpretcat/vrp/blob/ff90527293b01e9420ac362d7a4aa0beb8b0c45e/vrp-pragmatic/src/format/problem/fleet_reader.rs#L97

My goal is it to make it cost wise expensive to not deliver a shipment as fast as possible. (or do you see downsides in raising cost for waiting time / e.g. could it work?)

[reinterpretcat]

Yes, it can be tweaked, but this is not yet exposed from pragmatic format.

For sharing data, you can either replace locations with indices referring to matrix to avoid sharing customer data and/or yes, send me email (ilya. builuk at gmail com) . Please try to minimize the amount of jobs/vehicles - this helps analysis (and motivation to dig into details - easier at lower scale). However, I would need to find time for it.

My goal is it to make it cost wise expensive to not deliver a shipment as fast as possible.

Additionally, you can try to use minimize-arrival-time objective (put it above cost ones).

[K-Leon]

Thank you so much! I shot you an email with a minimal example. (1 Vehicle with 7 stops or something like that)

I tried this objective before, but it leads to all unassigned with "reasons": "NO_REASON_FOUND:unknown"

[reinterpretcat]

I've quickly prototyped passing high waiting time costs, seems helped to reduce a bit waiting time at a price of driving time:

old:

"distance": 65044,
    "duration": 26751,
    "times": {
      "driving": 5685,
      "serving": 1200,
      "waiting": 19866,
      "break": 0,
      "commuting": 0,
      "parking": 0
    }

new statistic:

    "distance": 70328,
    "duration": 26751,
    "times": {
      "driving": 6093,
      "serving": 1200,
      "waiting": 19458,
      "break": 0,
      "commuting": 0,
      "parking": 0
    }

The overall duration of the tour cannot be reduced because of the later fixed time job. That's why minimize-arrival-time objective doesn't work. I think the optimal way would be to introduce a new objective which explicitly defines the goal of optimization. As I understood it, the goal is to serve jobs as early as possible. Such objective could help to guide search in the proper direction (just setting high waiting cost seems doesn't help).

[K-Leon]

Thank you very much! This is exactly the tradeoff we need to do. A bit more kilometers and less time on the truck is preferable.

My naive idea would be to associate cost to a package for every second it gets delivered after the earliest arrival date (and is loaded on a vehicle)

But I have no idea if this is a feasible approach given the current algorithm and architecture.

[reinterpretcat]

I've added some experimental objective in the separate branch:

https://github.com/reinterpretcat/vrp/tree/fast_service

With it, I have the following statistic:

"distance": 78907,
    "duration": 26751,
    "times": {
      "driving": 6683,
      "serving": 1200,
      "waiting": 18868,
      "break": 0,
      "commuting": 0,
      "parking": 0
}

So, waiting is further reduced. You can add it using objectives property as below:

  "objectives": [
    [{ "type": "minimize-unassigned" }],
    [{ "type": "fast-service" }],
    [{ "type": "minimize-cost" }]
  ]

It is WIP, missing interoperability with other features (mentioned in TODO), need to add some tests to make sure that it works as intended, etc. I would need to find some time to finalize it.

[K-Leon]

I tested a bit - also with different examples - it looks really good! Thank you very much!

The only feature that may be nice to somehow balance the cost inflicted by deliveries happening later then expected.

[K-Leon]

Just btw: I think it would be great thing to expose waiting_time cost in the config object. This may help tune this solution a bit more.

[reinterpretcat]

You mean a separate cost for waiting time in addition to the time? E.g:

"costs": {                                                                                                                                                                                                        
   "fixed": 20,                                                                                                                                                                                                    
   "distance": 0.0002,                                                                                                                                                                                             
   "time": 0.5,                                                                                                                                                                                                    
   "waiting": 10                                                                                                                                                                                              
} 

Here, time is for all costs except waiting. If waiting is omitted then it could behave as usual.

[K-Leon]

Exactly - This would be awesome! Thanks!

[ilibar-zpt]

Just an idea to decouple time cost parameter into separate service/waiting/driving components to be more explicit and granular

[reinterpretcat]

Yes, this could be done easily as it is already decoupled internally, just not exposed on pragmatic format level.

[K-Leon]

This would be awesome! I played a lot with the fast-service objective.

It works quiet well, but i felt it is from time to time a bit flakey/unpredictable and selects solutions that are a little too bad. Is it thinkable to make it adjustable "how strong" this rule kicks in? I'm not 100% sure after reading your code if this is somehow possible.

[reinterpretcat]

Is it thinkable to make it adjustable "how strong" this rule kicks in?

Theoretically, this can be achieved by moving minimize-cost and fast-service on the same level and adding some additional parameters to say "how strong" it should prefer one objective over another. The problem is how to quantify these parameters.

[K-Leon]

I think we need to differentiate cost wise between "clearing" waiting time and extended driving duration / distance.

From the business point of view there are two scenarios that need to be addressed:

a) The above example - minimizing waiting time b) Preventing the algorithm from skipping de tours of 500 meters to come back in the noon. Earliest delivery wins.

For example around 10% more on a single route level is - depending on the business constraints - for faster deliveries justifiable. At least this may be one approach to configure it.

But I'm still not sure how a convincing function could be designed - i'm testing a bit around and try to grasp the possible knobs in your vrp project.

Actually it intersects a little bit with a different issue i'm trying to model "from the outside" by a heuristic and running multiple calculations parallel with different inputs. Trying to handle appointments as soft constraints and dropping the constraints depending on heuristics and results.

At the end it is business wise all about the question: Do I want the shortest route or do I want a route that feels naturally right for a human and that takes small tradeoffs.

[reinterpretcat]

I included an updated fast-service objective into master branch. Also I've added tolerance parameter to it which might help to balance a bit trade-off between this objective and others (e.g. min-cost)