search

VROOM-Project / vroom

Vehicle Routing Open-source Optimization Machine
http://vroom-project.org/
BSD 2-Clause "Simplified" License
1.34k stars 336 forks source link

Assert error in RawRoute::update_amounts() caused by RouteSplit operator #981

Closed torinori closed 1 year ago

torinori commented 1 year ago

Command: 

vroom -i input_cap_assert_matrix.json

Error:

vroom: structures/vroom/raw_route.cpp:100: void vroom::RawRoute::update_amounts(const vroom::Input&): Assertion `_current_loads.back() <= capacity' failed.
Aborted (core dumped)

Vroom version: vroom 1.14.0-dev

GDB stack trace:

#0  __pthread_kill_implementation (no_tid=0, signo=6, threadid=140737339455040) at ./nptl/pthread_kill.c:44
#1  __pthread_kill_internal (signo=6, threadid=140737339455040) at ./nptl/pthread_kill.c:78
#2  __GI___pthread_kill (threadid=140737339455040, signo=signo@entry=6) at ./nptl/pthread_kill.c:89
#3  0x00007ffff7242476 in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
#4  0x00007ffff72287f3 in __GI_abort () at ./stdlib/abort.c:79
#5  0x00007ffff722871b in __assert_fail_base (fmt=0x7ffff73dd150 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n", assertion=0x5555556bfe80 "_current_loads.back() <= capacity", file=0x5555556bf4b0 "structures/vroom/raw_route.cpp", line=100, 
    function=<optimized out>) at ./assert/assert.c:92
#6  0x00007ffff7239e96 in __GI___assert_fail (assertion=0x5555556bfe80 "_current_loads.back() <= capacity", file=0x5555556bf4b0 "structures/vroom/raw_route.cpp", line=100, 
    function=0x5555556bfcd8 "void vroom::RawRoute::update_amounts(const vroom::Input&)") at ./assert/assert.c:101
#7  0x0000555555662a96 in vroom::RawRoute::update_amounts (this=0x7ffff00c0130, input=...) at structures/vroom/raw_route.cpp:100
#8  0x000055555567b782 in vroom::TWRoute::replace<__gnu_cxx::__normal_iterator<unsigned short*, std::vector<unsigned short, std::allocator<unsigned short> > > > (this=0x7ffff00c0130, input=..., delivery=..., first_job=..., last_job=..., 
    first_rank=<optimized out>, last_rank=0) at structures/vroom/tw_route.cpp:1442
#9  0x000055555565773f in vroom::vrptw::RouteSplit::apply (this=0x7ffff00b30e0) at problems/vrptw/operators/route_split.cpp:74
#10 0x00005555555e0796 in vroom::ls::LocalSearch<vroom::TWRoute, vroom::vrptw::UnassignedExchange, vroom::vrptw::CrossExchange, vroom::vrptw::MixedExchange, vroom::vrptw::TwoOpt, vroom::vrptw::ReverseTwoOpt, vroom::vrptw::Relocate, vroom::vrptw::OrOpt, vroom::vrptw::IntraExchange, vroom::vrptw::IntraCrossExchange, vroom::vrptw::IntraMixedExchange, vroom::vrptw::IntraRelocate, vroom::vrptw::IntraOrOpt, vroom::vrptw::IntraTwoOpt, vroom::vrptw::PDShift, vroom::vrptw::RouteExchange, vroom::vrptw::SwapStar, vroom::vrptw::RouteSplit>::run_ls_step (this=0x7ffff71fe710) at algorithms/local_search/local_search.cpp:1709
#11 0x00005555555e3d16 in vroom::ls::LocalSearch<vroom::TWRoute, vroom::vrptw::UnassignedExchange, vroom::vrptw::CrossExchange, vroom::vrptw::MixedExchange, vroom::vrptw::TwoOpt, vroom::vrptw::ReverseTwoOpt, vroom::vrptw::Relocate, vroom::vrptw::OrOpt, vroom::vrptw::IntraExchange, vroom::vrptw::IntraCrossExchange, vroom::vrptw::IntraMixedExchange, vroom::vrptw::IntraRelocate, vroom::vrptw::IntraOrOpt, vroom::vrptw::IntraTwoOpt, vroom::vrptw::PDShift, vroom::vrptw::RouteExchange, vroom::vrptw::SwapStar, vroom::vrptw::RouteSplit>::run (this=this@entry=0x7ffff71fe710) at algorithms/local_search/local_search.cpp:1867
#12 0x000055555562d39a in vroom::VRP::solve<vroom::TWRoute, vroom::ls::LocalSearch<vroom::TWRoute, vroom::vrptw::UnassignedExchange, vroom::vrptw::CrossExchange, vroom::vrptw::MixedExchange, vroom::vrptw::TwoOpt, vroom::vrptw::ReverseTwoOpt, vroom::vrptw::Relocate, vroom::vrptw::OrOpt, vroom::vrptw::IntraExchange, vroom::vrptw::IntraCrossExchange, vroom::vrptw::IntraMixedExchange, vroom::vrptw::IntraRelocate, vroom::vrptw::IntraOrOpt, vroom::vrptw::IntraTwoOpt, vroom::vrptw::PDShift, vroom::vrptw::RouteExchange, vroom::vrptw::SwapStar, vroom::vrptw::RouteSplit> >(unsigned int, unsigned int, std::optional<std::chrono::duration<long, std::ratio<1l, 1000l> > > const&, std::vector<vroom::HeuristicParameters, std::allocator<vroom::HeuristicParameters> > const&, std::vector<vroom::HeuristicParameters, std::allocator<vroom::HeuristicParameters> > const&, std::vector<vroom::HeuristicParameters, std::allocator<vroom::HeuristicParameters> > const&) const::{lambda(std::vector<unsigned long, std::allocator<unsigned long> > const&)#2}::operator()(std::vector<unsigned long, std::allocator<unsigned long> > const&) const (__closure=0x7ffff0084d10, sol_ranks=...) at ./problems/vrp.h:236
#13 0x00007ffff76dc253 in ?? () from /lib/x86_64-linux-gnu/libstdc++.so.6
#14 0x00007ffff7294b43 in start_thread (arg=<optimized out>) at ./nptl/pthread_create.c:442
#15 0x00007ffff7326a00 in clone3 () at ../sysdeps/unix/sysv/linux/x86_64/clone3.S:81

After removing RouteSplit from list of operators, it works fine.

Standalone problem instance: input_cap_assert_matrix.json.txt

jcoupey commented 1 year ago

Thanks for sharing the details and instance, I can reproduce with current master. This kind of assert is here to make sure we're in a normal/valid state, here wrt capacity constraints.

So at first sight, I'd say we're trying to apply the operator in a way that breaks the capacity constraints, and the assert catches that. The bottom line here is the validity checks for capacities in the RouteSplit operator are probably too loose .

jcoupey commented 1 year ago

There was indeed a flaw in the capacity validity checks performed inside RouteSplit. As a result a split was wrongly considered valid and applied, leading to an over-capacity route.

The tricky part is that this could only happen in a situation mixing job pickups and deliveries (e.g. with the provided instance), so the problem never arose with the usual HVRP benchmarks that are delivery-only.

It should now be fixed in #998.

jcoupey commented 1 year ago

Something I noticed is that while we had one check that was too loose in some situations, another capacity check was actually too tight so we were discarding possible valid splits, including in delivery-only situations. This means that we can expect the fix to also have an impact on benchmark results. I'll report on that directly on the PR.