JMaravalhasSilva
commented
1 year ago Can you tell me a bit more about this project?
Sure. This project was made for an assignment that @JoaoFilipeResende and I had in the first year of our PhD program. For this assignment we could choose whatever optimization problem we wanted to solve, so we used a research project that I was working on at the time - NetTag (EASME/EMFF/2017/1.2.1.12/S2/02/SI2.789121, see also here) - as "inspiration" for a made-up problem. The actual research project was never in need for a solution to our "item recovery problem".
About the choice of the optimization algorithm itself, well, besides having a problem with many constraints, our solutions have non-fixed sizes and additionally contain "implicit" information regarding the "weight" that is carried by the AUV at a given time (Table 1 of the report, notice how the available carrying capacity must be inferred from the solution and the carrying capacity itself). This makes the more traditional heuristics difficult to adapt to this situation. Given this, ALNS seemed like a really good fit.
With ALNS, the only thing we needed was a greedy repair algorithm that was able to repair "bad" solutions, and a bunch of destruction algorithms which would either completely wreck a "good" solution, or just "slightly break it". Developing these custom "methods" in isolation is much, much easier than developing an entirely custom optimization algorithm to solve our very specific and complex problem. Additionally, since ALNS selects the next methods to use based on past performance, we have direct feedback on which methods are not so great, and since the methods are relatively simple due to being self-contained, it makes it easier to analyze the reasons why they are not working properly. For instance, we have concluded in our report that one destruction method did not work properly, and it is easy to see why given the way our repair method works.
In our opinion, the only thing that ALNS lacks is awareness on which pairs of destruction+repair methods work best. In our work, we only implemented one repair method, but had we implemented multiple repair methods, it is possible that our "bad" destruction method could have actually work well when paired with a second repair method. Unfortunately, given that ALNS selects methods based on their individual success rates, this would likely result in frequent, useless runs of said destruction method with the original repair method. Unfortunately, this is something we only realized once we already delivered the report :laughing:
Is it published somewhere, and if so, how can I cite it?
You are free to pretty much just do whatever you see fit in your paper, as long as you cite our names and the repository itself. You can cite our names as they appear in the PDF report, or you can write them as "J. Resende" and "J. Maravalhas-Silva" for simplicity. Other than that, just make sure to follow your journal's guidelines.
There are no proper peer-reviewed publications regarding our use of the ALNS approach to solve our made-up problem. If you absolutely must cite a paper, you could additionally cite NetTag's conference paper as the source of inspiration for our work. However, beware that this paper contains no reference whatsoever to the work on this repository and that @JoaoFilipeResende is also not an author of that paper since he was working on another research project at the time. So yeah, the paper cannot be used as a substitute for citing the repository.
N-Wouda
I'm working on a JOSS publication of ALNS, which you have used in this repo. As part of that publication, I intend to cite a few use cases other people have had. Can you tell me a bit more about this project? Is it published somewhere, and if so, how can I cite it?