Which problem option to select? #593

bmorlo · 2024-05-27T10:26:47Z

bmorlo
May 27, 2024

Hi,

my plan is to edit your pyvrp package (on Linux), build it, and then publish it on PyPI to use it also on e.g. a windows PC.
I just came across the option --problem {cvrp, vrptw} - see below. As I am not working with time windows, I was curious, how the cvrp solver differs from the vrptw in terms of performance. Would you recommend simply sticking to the vrptw solver in any case?

Thanks & cheers

morlocb@abcde:~/coding_dir/PyVRP_BM_load_balancing$ poetry run python build_extensions.py --help
usage: build_extensions [-h] [--build_dir BUILD_DIR] [--build_type {debug,debugoptimized,release}] [--problem {cvrp,vrptw}] [--clean] [--verbose] [--use_pgo] [--additional ...]

options:
  -h, --help            show this help message and exit
  --build_dir BUILD_DIR
                        Directory for Meson to use while building extensions.
  --build_type {debug,debugoptimized,release}
                        The type of build to provide. Defaults to release mode.
  --problem {cvrp,vrptw}
                        Which type of solver to compile. Defaults to 'vrptw'.
  --clean               Clean build and installation directories before building.
  --verbose             Whether to print more verbose compilation output.
  --use_pgo             Whether to enable profile-guided optimisation.
  --additional ...      Extra Meson configuration options (passed verbatim to Meson).

Answered by N-Wouda

May 27, 2024

my plan is to edit your pyvrp package (on Linux), build it, and then publish it on PyPI to use it also on e.g. a windows PC.

You don't need to push to PyPI to get the required wheels out - you can download them once the GitHub Action has completed. For us, that's every time the CD runs, for example here.

As I am not working with time windows, I was curious, how the cvrp solver differs from the vrptw in terms of performance. Would you recommend simply sticking to the vrptw solver in any case?

It should be a bit (up to 20-25%?) faster because the CVRP-specific build removes all time window computations from the algorithm. This build option will probably be removed as part of #502, but w…

View full answer

N-Wouda · 2024-05-27T10:30:23Z

N-Wouda
May 27, 2024
Maintainer

my plan is to edit your pyvrp package (on Linux), build it, and then publish it on PyPI to use it also on e.g. a windows PC.

You don't need to push to PyPI to get the required wheels out - you can download them once the GitHub Action has completed. For us, that's every time the CD runs, for example here.

As I am not working with time windows, I was curious, how the cvrp solver differs from the vrptw in terms of performance. Would you recommend simply sticking to the vrptw solver in any case?

It should be a bit (up to 20-25%?) faster because the CVRP-specific build removes all time window computations from the algorithm. This build option will probably be removed as part of #502, but we haven't gotten around to that yet. If you don't need anything duration related, this could be worthwhile. However, the actual performance differences in terms of solution quality will likely be fairly small.

3 replies

bmorlo May 27, 2024
Author

Hi @N-Wouda,

allow me a few questions on your comment, as I'm quite new to working with github and PyPI.

You don't need to push to PyPI to get the required wheels out - you can download them once the GitHub Action has completed. For us, that's every time the CD runs, for example here.

What exactly is 'the GitHub Action' you are referring to?
What is the CD / CD run?
I've successfully pushed to PyPi from Linux using poetry. Unfortunately, it does not appear to be public yet. How did you guys manage to make it visible on PyPI? Anyhow, I can still call pip install --upgrade pyvrp-load_balancing. However, this fails (on Windows) when trying to build wheel. Do you have encountered something similar while working on your project?

Thanks again.

N-Wouda May 30, 2024
Maintainer

Hi, sorry, this took a while.

What exactly is 'the GitHub Action' you are referring to? What is the CD / CD run?

The thing we use to run our continuous integration (CI) and deployment (CD) pipelines. These pipelines are defined in workflows here. They run every time we commit new code to the main branch, or open a PR with code to be merged into main. Basically these are checks that the new code is OK, and that the resulting PyVRP package still does everything we expect it to be able to do.

Part of that is to build a full package for each platform we support, and to check that these packages work. Since we have native extensions compiled from our C codebase, we produce binary packages. These are called 'wheels' in the Python world. Those wheels may be downloaded once the CD completes, and can be installed just like any other package can be (e.g., pip install <path to wheel> works just fine).

Your fork of PyVRP has the CD workflow, which you can run in your forked repository. You can thus produce new Windows versions of your fork of PyVRP really easily using our CD pipeline.

I've successfully pushed to PyPi from Linux using poetry. Unfortunately, it does not appear to be public yet. How did you guys manage to make it visible on PyPI? Anyhow, I can still call pip install --upgrade pyvrp-load_balancing. However, this fails (on Windows) when trying to build wheel. Do you have encountered something similar while working on your project?

See above, which I got from here. You have uploaded a source distribution and a wheel for Linux (with Python 3.10). Thus, when you run pip install pyvrp-load_balancing on Windows, it will try to compile the sources since no wheel could be found that works on Windows. That compilation then fails. The solution is to also upload wheels for Windows - or bypass PyPI altogether and just use the wheels built by the CD directly.

bmorlo May 31, 2024
Author

Okay, thank you very much for the detailed answers. While I do not get everything just yet, it definitely helps with my understanding of your workflow and package management. Since I do not have too much time left, I will continue to run things solely on my Linux PC.
Cheers.

leonlan · 2024-05-27T14:02:44Z

leonlan
May 27, 2024
Maintainer

Hi @bmorlo,

Let me try to steer you a bit in a different direction. You are asking a lot of questions - which is not a problem in itself - but it's about a lot of things that I don't think will help you with your current work. First some clarifying assumptions:

I assume you are working on your thesis based on your first message to me on LinkedIn.
I assume you are trying to build load-balancing into PyVRP for your thesis use case.

You need at least 2 months (full-time) before you can modify the code of PyVRP to your liking, assuming you are already proficient in Python and C . You can read the paper for details on the algorithmic and mathematical background. PyVRP implements a complex local search solver, and if you cannot modify that correctly, you are likely not able to achieve your goal of building a load-balancing feature.

For a master's thesis, adopting a state-of-the-art solver is often too much because of time constraints. Most master's theses implement much simpler (meta-)heuristics, which is perfectly fine. For example, I have seen many master students implement an adaptive large neighborhood search metaheuristic for VRPs, see, e.g., https://alns.readthedocs.io/en/latest/examples/capacitated_vehicle_routing_problem.html. ALNS is easy to understand and implement, and importantly, it works well if implemented correctly. Of course, I'm not your advisor, so you have to check with your own advisor to see if that fits the scope of your thesis.

If you find yourself new to GitHub, consider starting with smaller projects first. For instance, the ALNS package I mentioned is considerably simpler than PyVRP; it was actually the first project I contributed to. Read the documentation, use StackExchange, ask GPT questions, etc., to get yourself familiar with all the Git(hub) bells and whistles. Additionally, if you're interested in learning about Python packaging, I recommend checking out this guide on creating a Python package. Although it's from 2022, most of the information remains relevant and current.

I hope this advice helps you further in your thesis. Wishing you the best of luck, and feel free to reach out if you need more tips.

4 replies

bmorlo May 27, 2024
Author

Hi @leonlan,

I really appreciate your remarks! Thank you so much for that! And yes, your assumptions are correct regarding my master's thesis and my current implementation goal.

Let me explain a few more things about me and my work (I have another two weeks to get the load balancing feature to work with pyvrp and I'm afraid I will have to try at least this week day and night):

I studied Vidals' HGA quite a lot in the last weeks (reading the papers) and my thesis is set to evolve around that
I've been working with the pyvrp package for the last two months
I am fairly proficient in python and C
I haven't really worked with GitHub before (I'm already getting better, I have a good friend that offered to help me from now on)
I haven't modified or created a python package before (I believe I can figure this out)

Allow me further to propose my approach regarding the implementation of a load balancing feature. It would be awesome to get you guys' feedback on that.

I plan to stick very closely to your price collecting implementation.
I was thinking to only modify the objective function and add new variables to the route class and the solution class. Using these variable (and some find_maximum_capacity_gap function) I believe I could already make sure I get a (much) worse objective value whenever there is a highly underutilized vehicle in the solution (a very low number of visited clients, relative to the other routes aka a large capacity gap)
You mentioned I would have to modify the local search method. Would this still be the case here? I'm probably mistaken, but shouldn't the code still work just as good if I do not touch your granular neighborhood search?

leonlan May 27, 2024
Maintainer

I respect your drive to work on this, and it's good to know that you're familiar with the literature & code, so let's make the best out of this then the next two weeks. :-)

I was thinking to only modify the objective function and add new variables to the route class and the solution class. Using these variable (and some find_maximum_capacity_gap function) I believe I could already make sure I get a (much) worse objective value whenever there is a highly underutilized vehicle in the solution (a very low number of visited clients, relative to the other routes aka a large capacity gap)

That could work. I still don't know what "load-balancing" formally means in your context but if it's simply penalizing underutilized vehicle then you can try to mimic the principles of hwo loadPenalty is calculated. Instead of taking "capacity" you can introduce some "target capacity" which updates based on the average (?) route capacity utilization of your solution and add objective penalty based on that.

You mentioned I would have to modify the local search method. Would this still be the case here? I'm probably mistaken, but shouldn't the code still work just as good if I do not touch your granular neighborhood search?

That's correct, I was wrong here. Only changing CostEvaluator could be enough.

I haven't modified or created a python package before (I believe I can figure this out)

Maybe I understand it wrong but why do you need to make a Python package? If you can run it in your Linux environment, why not continue there? If you want to make it work for Windows you need to build it specifically for Windows using a compatible toolchain. You can check out our CD to see how we do that with Github. (This is also the answer to your earlier questions on the Github Action & CD run.)

bmorlo May 27, 2024
Author

Load balancing (as far as I know) simply is the additional objective to have each vehicle cover a similar amount of demand. In my case, as I'm working with delivery=1 for all clients, this gets me to the "makespan minimization" that I was thinking about two weeks ago. I would like to actively optimize for tours of similar lengths in the solutions.
You're right. I can definitely deprioritize the package for now. I will try to get things implemented by Wednesday. I'll keep you updated. Thanks again for the support 😎

bmorlo May 31, 2024
Author

Hi @leonlan,
I am happy to report that I was able to make the necessary modifications in CostEvaluator.h , Solution.h, Solution.cpp to run my forked repository as a pyvrp_load_balancing package, see here. Everything is working as expected, as far as I can tell.

A short summary of what I did: I stuck very close to your code lines for price collecting. Now, whenever the CostEvaluator evaluates a solution, a very high penalty term gets added to the objective function. This penalty term is: $penalty = a * \max_k (vehicleCapacity_k - numberVisits_k)$, where k is the vehicle index and a is a scaling parameter. I currently simply set a to e.g. 10000 for my current test instance).

I now have a few questions:

Whenever I push a modification to my forked repository, I get the message CD: Build wheels on ubuntu-22.04 failed. Is this simply because your checks detect something that should not be there or because there is a fundamental problem with what I added?

Some time ago @N-Wouda explained to me regarding your price collecting penalties: To make the distance worth travelling the prizes should be high enough. It really depends on your application what "high enough" entails exactly. In a problem I'm currently working on, my prizes relate to a probability estimate of some event happening at each client location. The estimate is in [0, 1]. I scale that estimate by a parameter b to balance it with the distance estimates. Finding the right value of b requires some tuning on the topology of the problem.

Now my question on this would be: How do I actually go about determining the right value of my scaling parameter a in my load balancing approach? Right now I am simply using a very high value. However, I would like to leave the solver with some degrees of freedom to be able to find a best solution even with slightly unequal routes. I was thinking about something like $a = \max_{i,j} (edgeDistance_{i,j})$. As I am currently working through the literature anyway, I will try to find something on that. But I thought I might as well ask you guys how you are actually getting to those fine-tuned values in your problems.

leonlan · 2024-06-01T05:41:09Z

leonlan
Jun 1, 2024
Maintainer

A short summary of what I did: I stuck very close to your code lines for price collecting. Now, whenever the CostEvaluator evaluates a solution, a very high penalty term gets added to the objective function. This penalty term is: , where k is the vehicle index and a is a scaling parameter. I currently simply set a to e.g. 10000 for my current test instance).

This kind of works, but the algorithm is not complete. You still need to change a few things in CostEvaluator to have the correct behavior HGS.

Whenever I push a modification to my forked repository, I get the message CD: Build wheels on ubuntu-22.04 failed. Is this simply because your checks detect something that should not be there or because there is a fundamental problem with what I added?

CI/CDs fail simply because the checks in place do not pass. See https://github.com/bmorlo/PyVRP_load_balancing/actions for the details.

Now my question on this would be: How do I actually go about determining the right value of my scaling parameter a in my load balancing approach? Right now I am simply using a very high value. However, I would like to leave the solver with some degrees of freedom to be able to find a best solution even with slightly unequal routes. I was thinking about something like . As I am currently working through the literature anyway, I will try to find something on that. But I thought I might as well ask you guys how you are actually getting to those fine-tuned values in your problems.

That's a matter of parameter tuning, I cannot say what works and what does not work for your problem.

12 replies

bmorlo Jun 3, 2024
Author

skipLoad skips the load calculation for the delta cost evaluation. Whether that's useful or not for your case depends on whether you have cases where you should skip it or not.

I currently cannot think of any cases where you would skip the load calculation in the delta cost. This would essentially mean one would not penalizing excess load, right? Maybe you have an example in mind that makes this clearer for me @leonlan

leonlan Jun 3, 2024
Maintainer

SwapStar has many places where load calculations are skipped. The code snippet that you referenced includes an explanation.

bmorlo Jun 3, 2024
Author

Right, thanks for the hint. Now things make sense. I will adjust my fork. Will report back tomorrow. I believe then this discussion can be closed. Cheers

bmorlo Jun 4, 2024
Author

Things still work well after I have modified SwapStar. However: I noticed that I'm getting only feasible solutions (this was also the case before I modified SwapStar) when using very high penalties for "underutilized" solutions and routes. From my understanding this is fine and to be expected. When you penalize "underutilized" routes as heavily as I do, the chances of getting a (capacity violating) infeasible solution are very low.

My question now is: Does only getting feasible solutions impact the performance of the solver from your point of view? I'm unsure here.

On the one hand I understand that it is important to also explore infeasible (in terms of excessLoad) solutions to find the best solutions since these are most likely close to infeasibility.
However, in my case, I am interested in solutions that exhibit a minimum load in any of their routes which is as close to the capacity limit as possible. This balances the load between routes since underutilized routes get a penalty. I believe it is only natural that no infeasible solutions appear when I'm penalizing quite strictly in my scenario. Indeed if I decrease the penalty, I get also infeasible solutions. With this lower penalty, the best solution exhibits a more uneven vehicle utilization but has a better objective value.

leonlan Jun 4, 2024
Maintainer

Does only getting feasible solutions impact the performance of the solver from your point of view?

Yes, which is precisely the reason why we have infeasible solutions. I cannot comment on your case whether it matters or not. You have to run your own benchmarks to figure it out.

bmorlo · 2024-06-06T20:30:53Z

bmorlo
Jun 6, 2024
Author

Alright. I benchmarked the latest version of my code on one of your test sets (which I modified to set a fixed number of vehicles and also have unit-demand per client) against your original PyVRP version. The performance with very even tours is only about 1% worse. See the two screenshots below (unfortunately I cut off the tours... so you gotta believe me her xD). The printed progress and the time stamps look good too. (If you see something that is off please let me know!) This should more than work for my thesis.

I'll leave the link to my final repository here
Cheers, Benedikt.

PyVPR-standard:
Load balancing:

1 reply

N-Wouda Jun 6, 2024
Maintainer

Great!

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Which problem option to select? #593

{{title}}

Replies: 4 comments 20 replies

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

Select a reply

Which problem option to select? #593

bmorlo May 27, 2024

Replies: 4 comments · 20 replies

N-Wouda May 27, 2024 Maintainer

bmorlo May 27, 2024 Author

N-Wouda May 30, 2024 Maintainer

bmorlo May 31, 2024 Author

leonlan May 27, 2024 Maintainer

bmorlo May 27, 2024 Author

leonlan May 27, 2024 Maintainer

bmorlo May 27, 2024 Author

bmorlo May 31, 2024 Author

leonlan Jun 1, 2024 Maintainer

bmorlo Jun 3, 2024 Author

leonlan Jun 3, 2024 Maintainer

bmorlo Jun 3, 2024 Author

bmorlo Jun 4, 2024 Author

leonlan Jun 4, 2024 Maintainer

bmorlo Jun 6, 2024 Author

N-Wouda Jun 6, 2024 Maintainer

bmorlo
May 27, 2024

Replies: 4 comments 20 replies

N-Wouda
May 27, 2024
Maintainer

bmorlo May 27, 2024
Author

N-Wouda May 30, 2024
Maintainer

bmorlo May 31, 2024
Author

leonlan
May 27, 2024
Maintainer

bmorlo May 27, 2024
Author

leonlan May 27, 2024
Maintainer

bmorlo May 27, 2024
Author

bmorlo May 31, 2024
Author

leonlan
Jun 1, 2024
Maintainer

bmorlo Jun 3, 2024
Author

leonlan Jun 3, 2024
Maintainer

bmorlo Jun 3, 2024
Author

bmorlo Jun 4, 2024
Author

leonlan Jun 4, 2024
Maintainer

bmorlo
Jun 6, 2024
Author

N-Wouda Jun 6, 2024
Maintainer