Can it apply coordinate map distance from api in this work?

[Suppharutchaya]

It is a great work but I wonder that can we use coordinate map distance from google api in order to get the real distance or not?

[yorak]

Hi @Suppharutchaya ,

yes, certainly. The algorithms take a full (dense) distance matrix D as an input. Hence, one can use, e.g., Google Maps Distance Matrix API to generate the D based on a set of GPS coordinates. If one has street addresses, a geocoding step is required prior to that.

Your question inspired me to create an example that illustrates using real world distances. Instead of the Google APIs, I use the Bing maps API, which has IMO better free tier. Please find the illustrative example in examples/bing_maps_example.py.

The script is used by creating a text file with one customer per line (first line is the address of a depot). The format of each line is <street_address_and_house_number>\t<postal_code>\t<city>\t<language_ISO_code>\t<goods_demand_at_the_customer>
Here, \t is tab character.

After creating a Bing maps API key and placing it in a MyBingMapApi.key and making sure that the VeRyPy is in PYTHONPATH (e.g.
export PYTHONPATH=$PYTHONPATH:/home/jussi/Projects/CVRP:/home/jussi/Projects/CVRP/VeRyPy
on linux or
set PYTHONPATH=%PYTHONPATH%;C:\users\jussi\Projects\CVRP;C:\users\jussi\Projects\CVRP\VeRyPy
on Windows/Anaconda.

Now, call the script as below and if everything is set up correctly, you will get a similar output.

$ python3 bing_maps_example.py -f sample_addresses.tsv -C 2 -v
INFO: Geocoding "Alkionkatu 5"
INFO: Geocoding "Keskuskatu 16"
INFO: Geocoding "Kirkkokatu 18"
INFO: Geocoding "Ylisentie 30"
INFO: Geocoding "Villenraitti 13"
INFO: Geocoding "Könninkatu 4"
D = array([[0.   , 1.121, 0.751, 0.867, 2.421, 0.406],
       [0.874, 0.   , 1.005, 1.511, 3.519, 1.05 ],
       [1.59 , 1.619, 0.   , 1.085, 2.513, 1.183],
       [0.867, 1.826, 1.132, 0.   , 1.982, 0.46 ],
       [2.421, 3.268, 2.574, 1.916, 0.   , 2.014],
       [0.406, 1.297, 0.927, 0.46 , 2.014, 0.   ]])
INFO: Filling 6 x 6 distance matrix.INFO: Solving a 5 customer CVRP with Savings heuristic.

Corresponding CVRP solution is
Route #1 : [0, 1, 0]
Route #2 : [0, 2, 4, 0]
Route #3 : [0, 3, 5, 0]

BR,
Jussi

[yorak]

In case you adapt the script to use Google API, feel free to make a pull request. Thanks.

[yorak]

Closing as this is shown to be possible.