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

Design and Architecture of project #334

Closed
trumboosahil opened this issue Apr 23, 2020 · 3 comments
Closed

Design and Architecture of project #334

trumboosahil opened this issue Apr 23, 2020 · 3 comments
Labels

Comments

@trumboosahil
Copy link

trumboosahil commented Apr 23, 2020

  1. What algorithms are used in the project.
  2. If want built .net version. Will that be achievable.
  3. Does it uses some specific functions of C that are not available in .net

Your input will be appreciated

@jcoupey
Copy link
Collaborator

jcoupey commented Apr 24, 2020

What algorithms are used in the project.

Do you mean "how does the solving approach works"? Or rather "what are the dependency for the project"?

If want built .net version. Will that be achievable.

I have no knowledge of .net so I wouldn't be able to comment much. If you aim at building the project on Windows, then I know of a couple users that have done that successfully (please browse closed tickets for more insights). If you want to use the C code directly, then please check #42 and this example.

Does it uses some specific functions of C that are not available in .net

We use the C 17 standard. How it's available and usable in .net is beyond the scope here.

@trumboosahil
Copy link
Author

Do you mean "how does the solving approach works"? Or rather "what are the dependency for the project"?

Yes i mean how does the solving approach work?

@VROOM-Project VROOM-Project deleted a comment from trumboosahil Apr 24, 2020
@jcoupey
Copy link
Collaborator

jcoupey commented Apr 24, 2020

I should get around to writing a more comprehensive explanation about this and push it to the wiki, but the short answer is:

  1. We apply heuristic approaches to find some initial solutions (starting from scratch, decide what vehicle's route to fill next, then decide incrementally what jobs to include in the route up to the point it's full and go on to the next vehicle).
  2. We run a fast local search phase where we try incrementally improving the current solution by applying several operators that make basic changes to routes or pair of routes.
  3. In addition to the local search step, we have a way to "loosen" the routes once in a while by removing a number of jobs that are good candidates for potential gains and re-inserting them in (hopefully) a better way. This specific step is a way to try reaching some solutions that are inaccessible with the basic operators we apply.

Because heuristic tuning is tricky depending on the kind of problem, we usually run several instances of the above in parallel with different parameters, then pick the best solution.

For more details, you may be interested in this talk for SoTM 2018. The features have significantly increased since but the overall principle is described in more details with some examples. I'm afraid if you then really want to go deeper into how it works, you'll have to dive into the code.

@jcoupey jcoupey closed this as completed May 2, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants