search

yorak / VeRyPy

A python library with implementations of 15 classical heuristics for the capacitated vehicle routing problem.
MIT License
263 stars 55 forks source link

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

Closed Suppharutchaya closed 3 years ago

Suppharutchaya commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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

yorak commented 3 years ago

Closing as this is shown to be possible.