Python TSP

August 02, 2014

Reading time ~12 minutes

The problem

Wikipedia states, the travelling salesman problem as this: “The travelling salesman problem asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”

The actual equation behind this formula is very complex and the explanation of this is is probably best left to the Wikipedia Page

My use case

I wrote an application that takes X number of orders, and has to split them between 9 vehicles, based on their, weight dimension and delivery location. I was first going to use my own formula to do this, but the time and power taken to run this in production, is a bit out of the question. So instead, I decided to sort all of the orders out into what vehicle they would end up in (code available for sale).

Now, I have 10-15 different addresses that I need to calculate the most efficient route for. So instead of writing a system from scratch, I decided to connect to a third party API.

It started with Google…

So I first wrote the following script in python, to work with the Google Maps API. (I didn’t realise they wanted £7,500 a year ex VAT to use their API, so I moved onto an open source solution). If you are a Google maps user and want to take advantage of my code, it is shown below with comments: (it could be compressed a lot more, but I have tried to make it easy to read for those from a less technical background) 

################################################################### Start and finish at same place ######## go via, with route optimise ##
# this method takes advantage of the optimisiation that Google lets us use.
url= "https://maps.googleapis.com/maps/api/directions/json?origin=Portsmouth,UK&destination=Portsmouth,UK&waypoints=optimize:true|Southampton,UK|Poole,UK|Reading,UK|Bridport,Dorset&sensor=false&key=YOURAPIKEYHERE"
# set the waypoints in the url
import urllib2
data = urllib2.urlopen(url)

# now get the json response
pre_json = data.read()
import json
obj = json.loads(pre_json)
data_new = json.dumps(obj, indent=2)
#load into dict
d = json.loads(data_new)

routes = []
# get the starting address
start_address = d['routes'][0]['legs'][0]['start_address']
start_lat = d['routes'][0]['legs'][0]['start_location'][u'lat']
start_long = d['routes'][0]['legs'][0]['start_location'][u'lng']

routes.append({'address': start_address, 'lat': start_lat, 'lng': start_long})
total_time = 0
total_distance = 0
for x in d['routes'][0]['legs']:
	total_time += x['duration']['value']
	total_distance += x['distance']['value']
	address = x['end_address']
	lat = x['end_location'][u'lat']
	lng = x['end_location'][u'lng']
	routes.append({'address': address, 'lat': lat, 'lng': lng})
print '##############################################################################'
print 'Optimised Route'
print '##############################################################################'
tt = (total_time / 3600.00)
td = total_distance*0.000621371192
print "Total Time %.2f hours" % round(tt,2)
print "Total Distance %.2f miles" % round(td,2)
for x in routes:
	print x

## ORIG ROUTE ##
# Now we put the route in, without any optimisation flags so we can compare
url2 = "https://maps.googleapis.com/maps/api/directions/json?origin=Portsmouth,UK&destination=Portsmouth,UK&waypoints=|Southampton,UK|Poole,UK|Reading,UK|Bridport,Dorset&sensor=false&key=YOURAPIKEYHERE"
data2 = urllib2.urlopen(url2)

pre_json2 = data2.read()
import json
obj2 = json.loads(pre_json2)
data_new2 = json.dumps(obj2, indent=2)
#load into dict
d2 = json.loads(data_new2)

routes2 = []

start_address2 = d2['routes'][0]['legs'][0]['start_address']
start_lat2 = d2['routes'][0]['legs'][0]['start_location'][u'lat']
start_long2 = d2['routes'][0]['legs'][0]['start_location'][u'lng']

routes2.append({'address': start_address, 'lat': start_lat, 'lng': start_long})
total_time2 = 0
total_distance2 = 0

for x in d2['routes'][0]['legs']:
	total_time2 += x['duration']['value']
	total_distance2 += x['distance']['value']
	address = x['end_address']
	lat = x['end_location'][u'lat']
	lng = x['end_location'][u'lng']
	routes2.append({'address': address, 'lat': lat, 'lng': lng})
print '##############################################################################'
print 'Original Route'
print '##############################################################################'
tt2 = (total_time2 / 3600.00)
td2 = total_distance2*0.000621371192
print "Total Time %.2f hours" % round(tt2,2)
print "Total Distance %.2f miles" % round(td2,2)
for x in routes2:
	print x

print '##############################################################################'
print 'Summary'
print '##############################################################################'
total_saving_time = tt2 - tt
total_saving_distance = td2 - td
print 'The optimised route is %.2f miles shorter' % round(total_saving_distance,2)
print 'And also saves %.2f hours of time' % round(total_saving_time,2)

Here is an example output:

##############################################################################
Optimised Route
##############################################################################
Total Time 5.95 hours
Total Distance 274.23 miles
{'lat': 50.8166745, 'lng': -1.0833259, 'address': u'Portsmouth, UK'}
{'lat': 51.4544776, 'lng': -0.9781547, 'address': u'Reading, UK'}
{'lat': 50.7150463, 'lng': -1.9872525, 'address': u'Poole, UK'}
{'lat': 50.7335746, 'lng': -2.7583416, 'address': u'Bridport, Dorset DT6, UK'}
{'lat': 50.9096948, 'lng': -1.4047779, 'address': u'Southampton, UK'}
{'lat': 50.8166745, 'lng': -1.0833259, 'address': u'Portsmouth, UK'}
##############################################################################
Original Route
##############################################################################
Total Time 7.32 hours
Total Distance 334.71 miles
{'lat': 50.8166745, 'lng': -1.0833259, 'address': u'Portsmouth, UK'}
{'lat': 50.9096948, 'lng': -1.4047779, 'address': u'Southampton, UK'}
{'lat': 50.7150463, 'lng': -1.9872525, 'address': u'Poole, UK'}
{'lat': 51.4544776, 'lng': -0.9781547, 'address': u'Reading, UK'}
{'lat': 50.7335746, 'lng': -2.7583416, 'address': u'Bridport, Dorset DT6, UK'}
{'lat': 50.8166745, 'lng': -1.0833259, 'address': u'Portsmouth, UK'}
##############################################################################
Summary
##############################################################################
'''
The optimised route is 60.48 miles shorter
And also saves 1.36 hours of time
'''

###############################################################################
time python tsp.py
real	0m5.843s
user	0m0.128s
sys	0m0.040s
###############################################################################

Open Source Style..

Now, lets do the same thing, but with a FREE licence and using Open Source data, using the brilliant API from MapQuest

import requests
import json

# set your app key
my_app_key = "YOUR_KEY"

# add points to the route
route = {"locations":[]}
route['locations'].append( {"latLng":{"lat":51.524410144966154,"lng":-0.12989273652335526}})
route['locations'].append( {"latLng":{"lat":51.54495915136182,"lng":-0.16518885449221493}})
route['locations'].append( {"latLng":{"lat":51.52061842826141,"lng":-0.1495479641837033}})
route['locations'].append( {"latLng":{"lat":51.52850609658769,"lng":-0.20170525707760403}})

# url to post of API
url = "http://open.mapquestapi.com/directions/v2/optimizedroute?key=" + my_app_key
url_basic = "http://open.mapquestapi.com/directions/v2/route?key=" + my_app_key
# Important, we need to add headers saying we are posting JSON
headers = {'Content-type': 'application/json', 'Accept': 'text/plain'}

# build the request
r = requests.post(url, data=json.dumps(route), headers=headers)
r_basic = requests.post(url_basic, data=json.dumps(route), headers=headers)
# load the json respone into the praser 
route_json = json.dumps(r.json(), indent=2)
route_json_basic = json.dumps(r_basic.json(), indent=2)
# load into a python data structure
data = json.loads(route_json)
data_basic = json.loads(route_json_basic)

# Map URL to generate a map showing the routes we are taking on this trip
map_placeholder = "http://open.mapquestapi.com/staticmap/v4/getmap?key={my_app_key}&bestfit={bestfit}&shape={shape}&size=600,600&type=map&imagetype=jpeg"

# Define some functions to return clean data
def get_bounding_box(data):
	# load the bounding box data which forms the edges
	# of the static map we will be using
	bestfit = "{lat1},{long1},{lat2},{long2}"
	bestfit_clean = bestfit.format(lat1=data['ul']['lat'], 
		long1=data['ul']['lng'], lat2=data['lr']['lat'], 
		long2=data['lr']['lng'])
	# now return the clean variable for use in the static map url
	return bestfit_clean

def get_shape(data):
	seq = ""
	for x in data['locations']:
		latLng = str(x['displayLatLng']['lat']) + ',' + str(x['displayLatLng']['lng']) + ','
		seq = seq + latLng
	# remove last trailing comma
	shape_clean = seq[:-1]
	return shape_clean

# run data through the functions
shape_basic = get_shape(data_basic['route'])
shape_optimised = get_shape(data['route'])
bestfit_basic = get_bounding_box(data_basic['route']['boundingBox'])
bestfit_optimised = get_bounding_box(data['route']['boundingBox'])

# generate map URL
map_basic = map_placeholder.format(my_app_key=my_app_key, bestfit=bestfit_basic, 
	shape=shape_basic)
map_optimised = map_placeholder.format(my_app_key=my_app_key, bestfit=bestfit_optimised,
	shape=shape_optimised)

# Get a printout of the data
print '>------------<'
print 'Original Route'
print '>------------<'
# Show original order
for x in data_basic['route']['locationSequence']:
	print route['locations'][int(x)]['latLng']['lat']
print "Total Distance " + str(data_basic['route']['distance']) + ' miles'
print "Total Fuel Used " + str(data_basic['route']['fuelUsed']) + ' litres'
print "Total Time " +  str(data_basic['route']['formattedTime'])
print 'Map ' + map_basic
print ''
print '>-------------<'
print 'Optimised Route'
print '>-------------<'
# Show optimised order
for x in data['route']['locationSequence']:
	print route['locations'][int(x)]
print "Total Distance " + str(data['route']['distance']) + ' miles'
print "Total Fuel Used " + str(data['route']['fuelUsed']) + ' litres'
print "Total Time " +  str(data['route']['formattedTime'])
print 'Map ' + map_optimised

The results shown below, you can use their free GeoCoding service to take address strings and turn them into coordinates. 

luke@xbu64:~/python$ python open_tsp.py 
>------------<
Original Route
>------------<
51.524410145
51.5449591514
51.5206184283
51.5285060966
Total Distance 8.482 miles
Total Fuel Used 0.52 litres
Total Time 00:25:13
Map http://open.mapquestapi.com/staticmap/v4/getmap?key=YOURKEY&bestfit=51.547508,-0.201385,51.519817,-0.127893&shape=51.524410145,-0.129892736523,51.5449591514,-0.165188854492,51.5206184283,-0.149547964184,51.5285060966,-0.201705257078&size=600,600&type=map&imagetype=jpeg

>-------------<
Optimised Route
>-------------<
{'latLng': {'lat': 51.524410144966154, 'lng': -0.12989273652335526}}
{'latLng': {'lat': 51.52061842826141, 'lng': -0.1495479641837033}}
{'latLng': {'lat': 51.54495915136182, 'lng': -0.16518885449221493}}
{'latLng': {'lat': 51.52850609658769, 'lng': -0.20170525707760403}}
Total Distance 7.116 miles
Total Fuel Used 0.43 litres
Total Time 00:21:37
Map http://open.mapquestapi.com/staticmap/v4/getmap?key=YOURKEY&bestfit=51.547508,-0.201385,51.519962,-0.130076&shape=51.524410145,-0.129892736523,51.5206184283,-0.149547964184,51.5449591514,-0.165188854492,51.5285060966,-0.201705257078&size=600,600&type=map&imagetype=jpeg

The above code also generates a static map so you can see a visual representation of the route you just solved :)

Need any help with a project that uses Maps, Geo-positional or GIS? Hit me up luke@pumalo.org

Read More

How to scale a web application with one docker container

Load everything inside one docker container, not multiple containers. Continue reading

Why I stopped using Django

Published on July 21, 2014

PostgreSQL cheat sheet

Published on July 20, 2014