Error when using per-vehicle costs

[sebhoerl]

I just started playing around with the per-vehicle costs feature in the current master (865d22e). To test, I constructed a minimal example with one pickup and one dropoff and two vehicles with equal distance costs and different per-vehicle cost. The idea was simply to verify that the vehicle with the lower fixed costs is chosen.

However, I get the following error message:

vroom: algorithms/local_search/local_search.cpp:1737: void vroom::ls::LocalSearch<Route, UnassignedExchange, CrossExchange, MixedExchange, TwoOpt, ReverseTwoOpt, Relocate, OrOpt, IntraExchange, IntraCrossExchange, IntraMixedExchange, IntraRelocate, IntraOrOpt, IntraTwoOpt, PDShift, RouteExchange, SwapStar, RouteSplit>::run_ls_step() [with Route = vroom::TWRoute; UnassignedExchange = vroom::vrptw::UnassignedExchange; CrossExchange = vroom::vrptw::CrossExchange; MixedExchange = vroom::vrptw::MixedExchange; TwoOpt = vroom::vrptw::TwoOpt; ReverseTwoOpt = vroom::vrptw::ReverseTwoOpt; Relocate = vroom::vrptw::Relocate; OrOpt = vroom::vrptw::OrOpt; IntraExchange = vroom::vrptw::IntraExchange; IntraCrossExchange = vroom::vrptw::IntraCrossExchange; IntraMixedExchange = vroom::vrptw::IntraMixedExchange; IntraRelocate = vroom::vrptw::IntraRelocate; IntraOrOpt = vroom::vrptw::IntraOrOpt; IntraTwoOpt = vroom::vrptw::IntraTwoOpt; PDShift = vroom::vrptw::PDShift; RouteExchange = vroom::vrptw::RouteExchange; SwapStar = vroom::vrptw::SwapStar; RouteSplit = vroom::vrptw::RouteSplit]: Assertion `new_eval + best_gain == previous_eval' failed.
Aborted (core dumped)

If I set any of the two fixed costs to zero, no error is produced and the one with zero costs is selected.

Here is a minimal test problem:

{"matrices": {"vtA": {"durations": [[0, 500], [500, 0]], "costs": [[0, 2500], [2500, 0]]}, "vtB": {"durations": [[0, 500], [500, 0]], "costs": [[0, 2500], [2500, 0]]}}, "shipments": [{"pickup": {"id": 0, "location_index": 1, "service": 60}, "delivery": {"id": 0, "location_index": 0, "service": 60}, "amount": [1]}], "vehicles": [{"id": 0, "profile": "vtA", "start_index": 1, "end_index": 1, "capacity": [4], "time_window": [0, 28800], "costs": {"fixed": 1000}}, {"id": 1, "profile": "vtB", "start_index": 1, "end_index": 1, "capacity": [4], "time_window": [0, 28800], "costs": {"fixed": 2000}}]}

[sebhoerl]

I just noticed that there is no problem if I remove the time windows from the vehicles (and it works with the maximum travel time constraint, which solves the problem for now in my case).

[jcoupey]

Thanks for testing and sharing. I can definitely reproduce the problem, there is probably a flaw in the cost evaluation related to one of the local search operator. Given the instance size, this should be straightforward to debug. I'll give it a go as soon as I can (I'm off in the next few days) and publish a new release candidate with a fix.

[jcoupey]

The problem lies in the PDShift operator. In cvrp::PDShift, we first take into account adding the fixed cost upon moving a shipment in an empty route:

https://github.com/VROOM-Project/vroom/blob/9ccb8862dc755d8caaea3bc12c77f006a648a817/src/problems/cvrp/operators/pd_shift.cpp#L51-L53

Then we account for the actual route cost:

https://github.com/VROOM-Project/vroom/blob/9ccb8862dc755d8caaea3bc12c77f006a648a817/src/problems/cvrp/operators/pd_shift.cpp#L71

Now for vrptw::PDShift the first part is already done upon calling the cvrp:PDShift parent ctor, but a silly mistake erases that value later on, instead of subtracting the other cost:

https://github.com/VROOM-Project/vroom/blob/9ccb8862dc755d8caaea3bc12c77f006a648a817/src/problems/vrptw/operators/pd_shift.cpp#L63

[jcoupey]

I just merged the branch from #860 in both master and release/1.13, and tagged a new v1.13.0-rc.2 release candidate.

[nilsnolde]

same for docker repo, trying to keep up;) if you could open an issue there it'd be best, I might miss it otherwise. maybe some folks prefer docker to test release candidates.

[sebhoerl]

Thanks, works perfectly!