Using actual distance/time in distance matrix for 1000 deliveries

[Manisha Raisinghani]

Hi,

We are trying to run the algorithm with 1000 deliveries and 10 trucks. Here, we are trying to form a distance matrix using solution C given in http://stackoverflow.com/questions/19410972/optaplanner-vrp-edge-weights-need-to-use-actual-gps-data-instead-of-euclidean-di.

Now the problem is that Google allows only 2500 calls a day to find the distance/time (Google Directions Service and Distance Matrix) but we will have to make 499,500 calls [N(N-1)/2] for 1000 deliveries. Any suggestions on how to achieve this or alternatives to Google Maps in India?

Also, how is the performance of the algorithm with 1000 deliveries?

Thanks,

Manisha

[Stefan Schröder]

Use GraphHopper (https://graphhopper.com/). It is incredibly fast and based on open data (OSM). It is open source (it comes with an Apache License) and its Java. You can get an even faster version for many-to-many calculations (it comes with a fee I guess).

When it comes to the performance of jsprit, it depends on many factors (your machine, no. of constraints, the algorithm config, no. threads you use etc.). I suggest you to build your own test case. Just generate 1000 customers in a plane randomly, assign them demands and random time-windows so that it approximates your case (with 10 trucks) and run it with the default euclidean distance calculator. When running problems with this size, it is worth to study the impact of multiple threads. You can .readAndCreate(...) an algorithm with a particular noThreads. When using the VehicleRoutingAlgorithmBuilder you can specify noThreads with .setNuOfThreads(..).

[Karussell]

Thanks Stefan, for mentioning GraphHopper! Yes Manisha, you can achieve that with GraphHopper and we provide a closed source distance matrix add-on (~10 times faster) which will be also available in our web business API.

Regarding the coverage in India. I'm not entirely sure. You could check the routes before here:
https://graphhopper.com/maps/?point=Mumbai%2C%20India&point=Delhi%2C%20india

Here you can see that the activity in India is relative good:

http://tyrasd.github.io/osm-node-density/#4/24.33/445.74

You also could use the following procedure:

1. Pick two random points
2. Use GraphHopper to calculate distance
3. Use one or more commercial router to calculate distance
4. Compare OSM distance vs commercial distance

If you have some experiences - I would be really interested :) !

Kind Regards,

Peter.

PS1: the matrix is not symmetric as the road network contains oneways and other asymmetric features (like speed)

PS2: google also has a special distance matrix API

[Manisha Raisinghani]

Thanks Stefan and Peter for your inputs. Actually we tried Graphhopper before even posting the question here and compared a few directions. Our analysis shows that GraphHopper assumes that the vehicle is moving at 60 kmph, which is not the case in India. 

For example, 

GraphHopper route  ------> 23.6 km, 24 min  but actually it takes around 50-60 min (I take this route everyday). Also, google shows the same depending on the time of the day. (Google route)

Is there any way we can get distance/time considering real-time traffic updates in Graphhopper. 

Stefan - We will try the same in jsprit and share the results with you.

Thanks,

Manisha

[pierredavidbelanger]

Manisha,

I myself use OSM2PO (http://osm2po.de/) and I am quite impressed with its speed.

Its closed source, but free for commercial use.

It works offline with the data from OpenStreetMap.

First you need to convert raw data from OSM into .gph files (the lib include command line utilities to do that).

And after that, you use the java api to load the .gph file and call a couple of methods to generate the distances and times matrix.

PS: I am not the author, I am just a happy user!

[Karussell]

Hi,

we should probably talk about this off-the list or on graphhopper mailing list but yes, you can tweak GraphHopper to your very own custom needs like reducing speed for cars. Or even create several instances depending on the time or create time dependent weightings with only one instance etc.

> Is there any way we can get distance/time considering real-time traffic updates in Graphhopper.

if you have the data you can do it, sure. E.g. have a look at some custom weighting:

https://github.com/graphhopper/graphhopper/blob/master/docs/core/weighting.md

Regards,

Peter.

[Stefan Schröder]

Update: you can test the performance of your algorithm configuration with the benchmark instances from Homberger and Gehring (download them here: http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-with-time-windows-instances/). Just read these instances with jsprit.instance.reader.SolomonReader and solve them with your algorithm config. You can find best known results here: http://www.sintef.no/Projectweb/TOP/VRPTW/Homberger-benchmark/.

To get an impression of how computation time depends on no. of customers, look at the attached figure. It is calculated with a 3.2 GHz machine (4 cores). As you can see, it is worth to use the concurrent mode at about 350 customers (IN THIS BENCHMARK INSTANCE C204 which characterized by a long scheduling horizon and large time windows). It is calculated with the following algo config:

LargeRandomRuin (fraction \(f=0.5\)) and BestInsertion [\(Prob=0.2\)]
LargeRadialRuin (\(f=0.3\)) and BestInsertion [\(Prob=0.2\)]
SmallRandomRuin (\(f=0.1\)) and BestInsertion [\(Prob=0.3\)]
SmallRadialRuin (\(f=0.05\)) and BestInsertion [\(Prob=0.3\)]

along with SchrimpfAcceptance (alpha = 0.1), 20000 iteration and a premature terminator based on variationCoeffciant (500,0.001)