forked from yorak/VeRyPy
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bing_maps_example.py
189 lines (158 loc) · 7.34 KB
/
bing_maps_example.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#!/usr/bin/env python
"""This script calculates distance matrix for given addresses using Bing maps API.
More specifically:
1) it reads adresses from a file (tab separated fields, one per line format):
addressLine \t postalCode \t locality \t countryRegion [\t goodsDemand]
where addressLine is, e.g., the street and number,
locality is, e.g., the city/town name,
countryRegion is ISO country code, e.g. "US", and
optional goodsDemand is the demand for CVRP
2) geocodes them (gets coordinates) using Bing maps API,
3) and calculates a distance matrix using Bing maps API.
4) Optionally dups the Numpy distance matrix to file.
5) Interpretes the read and computed data as a capacitated vehicle routing problem (CVRP)
and solves it using Clarke and Wright savings heuristic.
To use it you need Bing maps API key. Get it here: https://www.bingmapsportal.com
and place it into a text file named MyBingMapApi.key, where the script reads it."""
# Written in Python 2.7, but try to maintain Python 3+ compatibility
from __future__ import print_function
from __future__ import division
try:
from urllib.parse import urlparse, urlencode, quote
from urllib.request import urlopen, Request
from urllib.error import HTTPError
except ImportError:
from urlparse import urlparse
from urllib import urlencode, quote
from urllib2 import urlopen, Request, HTTPError
__author__ = "Jussi Rasku"
__copyright__ = "Copyright 2020"
__license__ = "MIT"
__version__ = "1.0.0"
__status__ = "Example"
import json
import sys
import pickle
import argparse
from pprint import pprint
import numpy as np
# TODO: include travel mode as a CLI parameter
TRAVEL_MODE = 'driving' #'walking'
BING_DM_API_CUSTOMER_LIMIT = 50 # 50 x 50 = 2500
def completeDataWithGeocoding(addressData, BingMapsKey):
reqData = dict(addressData)
reqData['locality'] = quote(addressData['locality'].strip(), safe='')
reqData['addressLine'] = quote(addressData['addressLine'].strip(), safe='')
reqData['BingMapsKey'] = BingMapsKey
geogodeUrl = ("http://dev.virtualearth.net/REST/v1/Locations"+
"?countryRegion="+str(reqData['countryRegion'])+
"&locality="+str(reqData['locality'])+
"&postalCode="+str(reqData['postalCode'])+
"&addressLine="+str(reqData['addressLine'])+
"&maxResults=1"+
"&key="+str(reqData['BingMapsKey']))
#print(geogodeUrl)
request = Request(geogodeUrl)
response = urlopen(request)
result = json.loads(response.read().decode(encoding='utf-8'))
lat, lon = result['resourceSets'][0]['resources'][0]['point']['coordinates']
retData = dict(addressData)
retData['latitude'] = lat
retData['longitude'] = lon
return retData
def getDistanceMatrix(addressDataList, travelMode, BingMapsAPIKey):
coordinateList = []
for ad in addressDataList:
coordinateList.append( str(ad['latitude'])+","+str(ad['longitude']) )
coordinates = ";".join(coordinateList)
distanceUrl = ("https://dev.virtualearth.net/REST/v1/Routes/DistanceMatrix"+
"?origins="+coordinates+"&destinations="+coordinates+
"&travelMode="+str(travelMode)+
"&distanceUnit=km"+
"&key="+str(BingMapsAPIKey))
#print(distanceUrl)
request = Request(distanceUrl)
response = urlopen(request)
result = json.loads(response.read().decode(encoding='utf-8'))
#pprint(result)
N = len(addressDataList)
D = np.zeros( (N,N) )
for cell in result['resourceSets'][0]['resources'][0]['results']:
D[cell['originIndex'], cell['destinationIndex']] = cell['travelDistance'] # could also be cell['travelDuration']
return D
## CLI specification ##
parser = argparse.ArgumentParser(description=__doc__)
group = parser.add_mutually_exclusive_group(required=True)
group.add_argument('-f', type=argparse.FileType('r'), metavar="address_file", help='address file')
group.add_argument('-D', type=argparse.FileType('rb'), metavar="distance_matrix_file", help='pickled Numpy distance matrix file')
parser.add_argument('-C', type=float, metavar="capacity", help='solve as CVRP with vehicles with this capacity')
parser.add_argument('-o', type=argparse.FileType('wb'), metavar="output", help='output file for pickled Numpy distance matrix')
parser.add_argument('-v', '--verbose', action='store_true', help='verbose output')
args = parser.parse_args()
## Read addresses from the file, geocode them, and compute the distance matrix using Bing maps API ##
locations = []
if args.f:
mapApiKey = ""
try:
mapApiKey = open('MyBingMapApi.key', mode='r').read().strip()
except:
sys.stderr.write("ERROR: No file called \"MyBingMapApi.key\"\n")
sys.stderr.write("It is a text file that should contain your personal Microsoft Bing Maps API key.\n")
sys.stderr.write("You can get one from here: https://www.bingmapsportal.com/\n")
sys.stderr.write("Exiting.\n")
sys.exit(1)
for l in args.f.readlines():
l = l.strip()
if len(l)==0:
continue
parts = l.split('\t')
if len(parts)<4 or len(parts)>5:
sys.stderr.write("ERROR: Invalid address data line \""+l+"\"\n")
sys.stderr.write("Data lines should be in format: addressLine \\t postalCode \\t locality \\t countryRegion [\\t goodsDemand]\n")
sys.stderr.write("Exiting.\n")
sys.exit(1)
location = {
"addressLine":parts[0],
"postalCode":parts[1],
"locality":parts[2],
"countryRegion":parts[3],
"demand":1 if len(locations)>0 else 0
}
if len(parts)==5:
location["demand"]=float(parts[4])
if args.verbose:
sys.stderr.write("INFO: Geocoding \""+location["addressLine"]+"\"\n")
locations.append( completeDataWithGeocoding(location, mapApiKey) )
if args.verbose:
sys.stderr.write("INFO: Filling %d x %d distance matrix."%(len(locations), len(locations)))
if (len(locations)>BING_DM_API_CUSTOMER_LIMIT):
sys.stderr.write("ERROR: Bing Distance Matrix API is limited to a query with %d\n"%(BING_DM_API_CUSTOMER_LIMIT*BING_DM_API_CUSTOMER_LIMIT))
sys.stderr.write("distances. Hence, at most %d coordinates can be queried in one go.\n")
sys.stderr.write("Exiting.\n")
sys.exit(1)
D = getDistanceMatrix(locations, TRAVEL_MODE, mapApiKey)
if args.o:
pickle.dump(D, args.o)
print("D = ", end="");pprint(D)
elif args.D:
D = pickle.load(args.D)
else:
assert(False) # argparse should take care that we never arrive here
pass
## Solve the related CVRP using VeRyPy ##
if args.C:
from classic_heuristics.parallel_savings import parallel_savings_init
from util import sol2routes
if locations:
d = [loc["demand"] for loc in locations]
else:
d = [0.]+[1.0]*(len(D)-1)
if args.verbose:
sys.stderr.write("WARNING: Setting all goods demands to be 1.0 (no data).\n")
if args.verbose:
sys.stderr.write("INFO: Solving a %d customer CVRP with Savings heuristic.\n"%(len(locations)-1))
# Solve and print the resulting routes
solution = parallel_savings_init(D=D, d=d, C=args.C)
print("\nCorresponding CVRP solution is")
for route_idx, route in enumerate(sol2routes(solution)):
print("Route #%d : %s"%(route_idx+1, route))