Very Large VRP

Maybe someone can comment on what I’m doing regarding a potential very large VRP problem.

Order of magnitude size of problem:1000 vehicles, all different depot addresses and 100000 stops.

I had a request whether I can do this very large VRP-type problem. As yet I don’t have any more details except for the numbers stated above. I want to make another appointment with my contact and both present to him my line of thinking to solve the problem and seeking more clarification on the application.

My approach is to use Jsprit to do this and then to address both related hardware and software issues.

1 Software
I plan to first break the problem into a number of smaller problems, solve them separately and then combine the different solution as an initial solution for the global application.

What I have done is the following:

a) Generating the problem
I started with 16 addresses evenly spaced on my grid, and then generated 16 depot addresses with a small random difference from the evenly spaced addresses. The result is 16 addresses that deviates a bit from 16 evenly spaced addresses.
Then I generated 8 random addresses, using not a normal but a power law distribution, around each of the depot addresses.

b) Solve the global problem using standard Jsprit
I got a solution that looks good using about 90 seconds optimisation time on my laptop.

c) Generating 4 depot clusters using Jsprit
I defined 16 stops with the addresses of my depots
Calculate the average of these 16 stops’ latitudes as the latitude of my new defined depot and thesame for the longitude.
I now have a different small problem with one depot in the middle of all the original depots and stops where all the original depots were.
I now specify 4 vehicles, all with the same depot addresses.
I solve this problem using Jsprit.
The solution gives me 4 clusters of 4 depots each.
The Jsprit optimisation time for this is about 1.2 seconds

d) Assigning stops for each of the 4 clusters of depots.
I calculated the average latitude and average longitude for each of the four clusters of depots
Define a depot for each of the four clusters
Specify 4 vehicles - one each for each of the 4 clusters and capacity of 8 per vehicle
Use all of the 128 original stops.
Use standard Jsprit to solve the problem.
The stops assigned to each of the 4 vehicles are now the stops four each of the 4 different smaller problems.
The Jsprit optimisation time for this is about 1.8 seconds.

e) Solve the 4 smaller problems separately
Each of the 4 Jsprit optimisation runs is about 3 seconds = 12 seconds for all four.

d) Combine the 4 smaller solutions as initial solution for the global optimisation.
The optimisation run time is much faster per iteration and you need less iterations to get to a good solution.
I haven’t tested this thoroughly yet, but the indications are that you get a good solution after 500 iterations instead of the default 2000 that I use.
Jsprit optimisation time for this = 11 seconds.
I want to play around with the alpha parameter, because I suspect one could probably hone in faster rather than allowing for much worse solutions. I don’t know?

The result is that this “breaking up” algorithm gives a similar result in maybe 30% of the optimisation time compared to just solve the global solution.
One mus be careful to extrapolate times because optimisation time is a very non-linear function of problem size.

2 Hardware
a) Using a CPU with more cores
My laptop’s CPU has 4 cores and I tested a large VRP that runs for about 2 hours to run using the default and about 1 hour if I specify 5 threads.
So using a server with a CPU with many cores will reduce the time.
But I tested a VRP problem with 100 addresses (not the one described above) and using the standard Jsprit it solves in about 75 seconds.
I made the problem similar bu increased the size to 200 addresses and Jprit solved it in about 1500 seconds.
A doubling in problem size resulted in 20 times longer optimisation time, so I’m not very enthusiastic about finding a powerful enough CPU to solve my big problem in a reasonable time.
But it is on my agenda to explore the use of a powerful local server.

b) Using cloud servers
We have some Amazon Web Services credit available for testing and it seems you can get a very powerful cloud virtual CPU. I haven’t explored this and it is on my agenda to explore

c) Using GPU (Graphical Processing Units)
It seems you can get an “affordable” GPU that runs Java on a number of “software” CPU’s on the one GPU card.
I haven’t explored this, but there are plenty good info on this available. There’s even a MOOC on this.
It will be an option to combine this with the software component of the solution described above.

c) Using Field Programmable Logic Array (FPGA)
With a FPGA you can configure a large number of CPU’s on the chip. There’s apparently a FPGA card for a PC available for about 500 USD.
The disadvantage is that it’s not so easy to use as a GPU. It uses a C-type programming language, so if we go this route we will probably translate Jsprit to the FPGA-C-type language.
The possible advantage is that it seems to be much more powerful than a GPU
A plus point for me could be that I have “in-family-expertise” on FPGA’s; my daughter is very knowledgeable on using FPGA’s and she will support me on an after-hours basis.

d) Building a cluster of Raspberry Pi computers.
The latest Raspberry Pi computer comes in at a basic price of about 5USD a piece.
Building a cluster of say 100 Raspberry Pi’s and the combine the “breaking up of the problem in smaller problems” algorithm and ship a large number of small problems to each of a large number of Raspberry Pi’s could be an option.

2 Likes

Hi Pieter,
Thanks for sharing this. I really appreciate it since I think that we can all learn a lot from this.
Can you write us some more details about the nature of the problem? My first thought was that in average each vehicle has 100 stops. This sounds like a typical last mile delivery tour, e.g. parcel service or smth like this. If it is then I assume that the problem does not only refer to one city but to several? Thus, I think the first step is to split the problem according to geographical area? You can for example calculate like 4hour isochrones to estimate which stops can actually be accessed from your vehicle locations (assuming an 8hour working day). But maybe it is not as simple as I think therefore I d like to learn more about the nature of your problem.
Best,
Stefan
Edit: Actually, I do not think that solving the problem is simple at all. This “simple” just refers to clustering the problem

Latter seems to be very promising. It even uses a large neighborhood search as well. The idea is to constantly divide the large scale problem into subproblems that can then be solved independently and fast. These subproblem solutions can be merged easily to have this large scale problem again and so on …

1 Like

I see several things to look at when it comes to calculating this with jsprit:

  • the initial neighborhood creation needs to be much more efficient (currently it has a complexity of n^2 just for the neighborhood creation).

  • most of the overall computation time is spent for identifying the best insertion position. This can be further parallelized.

  • evaluating good insertion positions can be restricted to promising routes. This is actually what Geoffrey did with his Nearby Selection.

BTW: we can also use Geoffrey’s large vrp instance to benchmark our algorithm :slight_smile:

1 Like

Hi Stefan,

I really appreciate your enthusiastic response.

It’s just that, other that the order of magnitude of the problem, I don’t yet have more information on the actual application. It’s a case that my contact is evaluating my ability to do it before divulging more information. The order of magnitude of the problem is 1000 vehicles and 100 000 stops.

I’m very happy to share the details of the test cases that I generated, it’s just that I have family commitments this weekend and can’t spend time on this till early next week. I plan to reply with more details of what I have done early next week.

Best,
Pieter

1 Like

Hi Stefan,

I have details of my test case in the public Dropbox excel file https://dl.dropboxusercontent.com/u/91388348/test%20case%20with%20results.xlsx

Regards,
Pieter

1 Like

Hi Folks, I am late in the party. is there any update in large scale VRP.

Powered by Discourse