Fixed cost for a vehicle

[jcoupey]

Current limitation

We lack a way to better model costs related to using different vehicles. Examples of (potentially) unexpected behavior that can be noticed in output for the sake of reducing overall travel time:

• using more vehicles (#495)
• using more expensive vehicles (#359)

The latter is also now probably more bound to happen as we now have multi-profile in place.

API addition ideas

A way to pass this in the API would be to add a cost object at vehicle level holding a v.cost.fixed value. Then we'd have to provide a way to homogenize with current travel-related costs, maybe with a scaling coefficient like v.cost.per_travelled_hour or similar.

Solving approach

This would require to go through all situations where we modify solutions during the local search phase (all neighboring operators, job removals/additions) to account for change in cost.

The fun part here is that we'd then be able to play with many new HVRP instances.

[aardvarkk]

@jcoupey I'm running into what seems like the opposite problem of #495 wherein even though I provide a large fleet of vehicles, only a small subset are being used in the solution.

For example, I provide 10 vehicles and 100 jobs, but only 3 are used and each is doing about 33 jobs. Is that expected behaviour? I would have expected vroom to utilize all of the vehicles to minimize the overall time that the jobs took, but that's not what I'm seeing.

[jcoupey]

I provide 10 vehicles and 100 jobs, but only 3 are used and each is doing about 33 jobs. Is that expected behaviour?

Yes, this is expected because it's probably cheaper overall to use only 3. Our main optimization objective is overall travel time.

I would have expected vroom to utilize all of the vehicles to minimize the overall time that the jobs took

Minimizing completion time is a totally different objective and you' d probably experience a much higher cost in term of overall travel time. See #466 on this.

[aardvarkk]

@jcoupey That issue link and your explanation was very helpful, thank you very much!

I'm starting to understand what you've said elsewhere about hidden requirements or constraints. I'm seeing at least three options to tailor the optimization to utilize more vehicles and what they correspond to in terms of "hidden constraints":

• Set more restrictive time windows ("drivers should be going home earlier!")
• Set capacities on vehicles and jobs ("drivers can't actually fit that much in their vehicles!")
• Set max_tasks for vehicles ("drivers shouldn't perform too much of the overall workload on their own!")

If you think I've missed any, please let me know!

I think I should be able to fiddle with these knobs to get a solution that "feels nicer" in my particular case. When I had previously read that the optimizer tries to reduce "overall travel time" I interpreted that as the "earliest finish time" (which I think you've referred to as the "makespan" elsewhere), when it fact it's the "sum of travel time across all drivers" that's minimized. Understanding the difference between those two makes it easier for me to reason about why certain options are chosen.

Thanks again very much for your work and for pointing me in the right direction!

[hugojanruiter]

@jcoupey quick question on this and a hack to get it started. Would it be possible to mimic fixed cost by adding a break to a vehicle at the beginning of the shift and subtracting the length of the break from the start time of the vehicle?

E.g.

• Original vehicle time window: 09:00 - 18:00
• New time window: 08:00 - 18:00 + break of 60 minutes from 08:00 - 09:00

If I observed correctly this would not work because cost == duration and that excludes service time (which includes service time of the break).

[jcoupey]

No, for the exact reason you mention: the service time of the break is not accounted for in the optimization objective.

[sebhoerl]

Hi, I'm using VROOM for a use case in the H2020 projet LEAD. Our goal is to solve a fleet composition and routing problem at the same time. What we already have is a simple search algorithm that proposes a specific fleet composition (# vehicles per type) and then calls VROOM in a loop to find the configuration that minimizes the added up vehicle costs + the operational costs found by VROOM.

Alternatively, we had an idea to find a solution directly in VROOM. In particular, we have a single depot set-up for a PD-VRP, so we can use the following simple strategy to mimic fixed costs inside VROOM: We place a certain number of vehicles N of each type on a virtual location that connects to the depot location with zero travel time and a cost that equals the fixed vehicle cost (per vehicle profile/type). We then avoid that the vehicles return to that location by imposing very high costs for all connections going to that virtual location and also for those leaving from it, except to the depot. With this setup, we solve the instances as usual. The idea is now to start with a low number N, potentially leading to an infeasible problem, then simply increasing this value until a feasible solution is found (so having N runs of VROOM) and then continuing to increase the value until we find a suboptimal case.

Our results show that this works quite well for small instances (in fact, we achieve the exact same fleet composition and total cost), but deteriorates for larger instances where more vehicles and more mixing is necessary. I'm not really an expert on VRP and certainly not on the implementation in VROOM, but my intuition is that the heuristics are less adapt at handling the cost structure with the high initial cost on the first movement, or that this somehow leads to VROOM finishing the search process quite quickly rather than trying to find better solutions.

I just wanted to add these observations, maybe somebody with more insight into VROOM has some idea / advice?

[jcoupey]

Thanks @sebhoerl for the feedback. You can definitely come up with various iterative ways to reduce number of vehicles and/or total vehicle cost.

deteriorates for larger instances where more vehicles and more mixing is necessary

Setting aside this kind of problems related to how you iteratively define the fleet, the main problem here is that this requires to solve a number of times (variants of) the same problem. So this would scale very badly as the instances size grow and the computing time for a single run starts to be significant.

If we want to have vehicle fixed costs accounted for in the optimization objective, the only way to do it properly is to include this cost component in the core solving approach.

[ilibar-zpt]

I think it would be useful to decouple profiles (which depend on OSRM/etc) from vehicle types, so that it is possible to have custom matrices per custom vehicle type.

• vehicle.profile stays as is
• add vehicle.type
• input.matrices indexed by vehicle.type instead of vehicle.profile

[jcoupey]

I think it would be useful to decouple profiles (which depend on OSRM/etc) from vehicle types

I don't really get what is the limitation with the current setup. Can you share an example of something that would be possible with a profile/type distinction that is not currently possible?

[ilibar-zpt]

• Different vehicles can have different fuel-usage, hence different costs.
• Different vehicles can be taxed/priced differently on toll-roads/ferries/etc, hence different costs.

In both cases costs differ from durations and could be custom values

[ilibar-zpt]

So different vehicle types may need to be created on-demand dynamically based on routing configuration.

Profiles in OSRM, for example, can be created only statically, and OSRM will require a restart. Hence use of profiles from a router is not feasible for configuring dynamic values such as taxes/fuel-consumption/etc.

[jcoupey]

My point is that if you want to use specialized costs such as fuel usage, tolls etc., then you have to compute them yourself outside the routing engine anyway. So what is wrong with providing them as custom matrices with whatever profile name you wish to use?

[ilibar-zpt]

Ah, got it. I was trying it with -g flag, just tried without it and it works, which makes sense, but not that obvious from the docs, thanks.

[ilibar-zpt]

It's still a problem because we lose geometry and distance, but it's doable now. Decoupling of vehicle types and profiles would still be useful then, just not as much

[sebhoerl]

I had already cloned the PR some days ago, but didn't manage to test it yet with our simulations. It's definitely going to happen this or next week! :) Thanks a lot!

[jcoupey]

@sebhoerl looking forward to your feedback then!

[cpprofs]

Dear Jcoupey, I am trying to use the ORS python library (which seems to be outdated). I want to force the algorithm to use all available vehicles by giving costs.fixed value a negative value. I am passing

{ 'fixed':-3600, 'per_hours':3600 }

I do not receive an error, nor do I see any change in the algorithm. Is it even possible to use a negative value?

[jcoupey]

@cpprofs can you please open a dedicated ticket? This one is long closed and was about the initial implementation for fixed costs.