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

degradation of initial solution #126

Open
Gorniker opened this issue Aug 17, 2023 · 6 comments
Open

degradation of initial solution #126

Gorniker opened this issue Aug 17, 2023 · 6 comments

Comments

@Gorniker
Copy link

We are trying to use vrp-cli (v. 1.22) to improve some vrp solutions, but the resulting solutions are often incorrect in capacity constraints.
The problem can be described with this example: the first run

vrp-cli solve pragmatic problem.json -m matrix.json -o solution_1.json

gives correct solution in solution_1.json (max load in tour is equal to the capacity of the vehicle), but the second run

vrp-cli solve pragmatic problem.json -m matrix.json -i solution_1.json -o solution_2.json

gives incorrect solution in solution_2.json (max load in tour is bigger the the capacity of the vehicle).
We have already tried different init-size values, but it didn't help.
The files from example:
example.zip

@reinterpretcat
Copy link
Owner

Hi, thanks for reporting!

So far sounds like an issue in init solution logic related to reload functionality. Anyway, I'll check it.

@reinterpretcat
Copy link
Owner

I think I found the reason of the problem: when initial solution is constructed from user provided, inserted jobs are not analyzed whether they should be promoted to locked as normally solver does for specific types (e.g. reload/break). If the job is not locked, it can be removed from the solution which might cause such issues.

Looking how I can fix it in nice way..

@reinterpretcat
Copy link
Owner

I've added a fix in the master branch, will be available in the next release

@Gorniker
Copy link
Author

Thanks a lot

reinterpretcat added a commit that referenced this issue Aug 26, 2023
* `experimental` recharge stations feature to support basic electric VRP
* apply refactorings to some core api
* update dependencies
* reload is removed from the solution passed as initial (#126)
@Gorniker
Copy link
Author

Hi. I've tested the last release and the solver gets correct solution on the represented example. But it still gets incorrect solutions on problems with more than two points.
The file with the minimal failing example (with the same sequence of runs):
example_2.zip

@reinterpretcat
Copy link
Owner

Actually, there is no really issue (well, maybe some missing validation rule), just a bit misuse of a tag: try to specify different values for each reload and use the corresponding ones in the init solution (should be added automatically).

Root cause: as the same tag is used on each reload, the solver assigns the same reload job multiple times and removes them together incorrectly later when processing initial solution. This can be fixed by throwing some validation error in init reader or make it smarter.

reinterpretcat added a commit that referenced this issue Dec 22, 2023
This release combines many changes, but essentials are:
- internal route state api simplification
- increased performance
- several experimental features
- bug fixes

* original job place index in activity place to simplify activity-job
 place matching
* `experimental`: a new type of location in pragmatic format to model
 zero distance/duration from it to any other location.
  This could be useful to model optional vehicle start location.
* allow user to pass alternative objectives in goal context to guide
 the search
* `experimental`: a new `fast-service` objective function to serve jobs
 as soon as possible

* experimental `dispatch` feature

* apply code style refactoring
* improve selection sampling search
* update dependencies
* improve a bit documentation
* refactor route state
* do not use hashmaps to store activity states

* double reload assignment when initial solution is used (#126)
* unexpected total_order behavior in dynamic heuristic (#128)
* improve validation rule for break with time offset  (#129)
* fix issue with skills (#133)
* do not cluster jobs if they are defined in relations (#141)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants