Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Infinite loop on small instance with v1.14.0.rc-2 #1038

Closed
jcoupey opened this issue Nov 17, 2023 · 2 comments · Fixed by #1039
Closed

Infinite loop on small instance with v1.14.0.rc-2 #1038

jcoupey opened this issue Nov 17, 2023 · 2 comments · Fixed by #1039

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Nov 17, 2023

I have a small test case (1 vehicle and 20 jobs) with various priority values:

jq '.jobs[].priority' test.json | sort -n | uniq -c
     11 0
      2 2
      7 10

It used to get solved in a breeze with v1.13.0 but the current release candidate is stuck on it. Only one thread remains active so probably one of the local search processes is hitting an infinite loop while applying moves.

@jcoupey jcoupey added this to the v1.14.0 milestone Nov 17, 2023
@jcoupey
Copy link
Collaborator Author

jcoupey commented Nov 17, 2023

OK when doing some debug output, turns out we're doing two PriorityReplace moves alternatively in a loop:

N5vroom5vrptw15PriorityReplaceE: 0 -> 0, gain = 6755
* route before: 17	16	19	5	9	8	3	7	11	12	13	14	1	4	6	10	15	
* route after: 17	16	19	5	9	8	3	18	
  * try_job_additions add job: 10
  * try_job_additions add job: 11
  * try_job_additions add job: 12
  * try_job_additions add job: 15
N5vroom5vrptw15PriorityReplaceE: 0 -> 0, gain = 4707
* route before: 17	16	19	5	9	8	3	15	12	11	10	18	
* route after: 17	16	19	5	9	8	3	14	
  * try_job_additions add job: 11
  * try_job_additions add job: 12
  * try_job_additions add job: 13
  * try_job_additions add job: 7
  * try_job_additions add job: 10
  * try_job_additions add job: 6
  * try_job_additions add job: 4
  * try_job_additions add job: 1
  * try_job_additions add job: 15
N5vroom5vrptw15PriorityReplaceE: 0 -> 0, gain = 6755
* route before: 17	16	19	5	9	8	3	7	11	12	13	14	1	4	6	10	15	
* route after: 17	16	19	5	9	8	3	18	
  * try_job_additions add job: 10
  * try_job_additions add job: 11
  * try_job_additions add job: 12
  * try_job_additions add job: 15
N5vroom5vrptw15PriorityReplaceE: 0 -> 0, gain = 4707
* route before: 17	16	19	5	9	8	3	15	12	11	10	18	
* route after: 17	16	19	5	9	8	3	14	
  * try_job_additions add job: 11
  * try_job_additions add job: 12
  * try_job_additions add job: 13
  * try_job_additions add job: 7
  * try_job_additions add job: 10
  * try_job_additions add job: 6
  * try_job_additions add job: 4
  * try_job_additions add job: 1
  * try_job_additions add job: 15

Jobs 14 and 18 have same priority (10) and the rest of the jobs in the replaced chunks have priority 0. The flaw here is that we're allowing a PriorityReplace with 0 priority gain, so the gain in cost comes with reducing the route size, which then can happen without guaranteeing that we converge.

@jcoupey
Copy link
Collaborator Author

jcoupey commented Nov 17, 2023

We already do check there is a possibility of a net gain at all:

const auto best_current_priority =
std::max(begin_priority_gain, end_priority_gain);
if (best_current_priority > 0 &&
best_priorities[source] <= best_current_priority) {

But that is not enough: in the above example the net gain is at the beginning, but since replacing the start of the route is not valid for other reasons, we end up replacing the end with a zero priority gain.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant