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.
: