Helping the Traveling Salesman with RouteMapIMS
The traveling salesman problem is an old one in mathematics. The problem itself is simple: given a collection of stops and the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all of the stops and returning to your starting point. Despite being one of the most intensely studied problems in computational mathematics, no effective mathematical solution method is known for the general case (if you have any hot ideas, there’s still a million dollar prize available for the solution). You have to essentially brute-force the problem - try every solution and pick the optimum one from the result set.
As long as our computer hardware is up to the task, however, the PC doesn’t really care about the math end of it (the PC still believes to this day that one should not perform mathematical operations on letters of the alphabet). I was tasked with finding out if ESRI’s RouteMapIMS could handle a traveling salesman problem of a decent-size (35+ stops) so we could use it as a tool for our clients rather than the fantastically expensive ArcLogistics. I’m truly shocked to say the answer is yes.
Let’s look at the code. We’re using RouteMapIMS 3.0, which has a .NET wrapper for it’s native COM objects, so we’ll be coding in ASP.NET.
First, some standard declarations. We’re going to nab the RouteMapIMS namespace, along one for SQL Server (for our master address table) and one for PostgreSQL (so we can project our points).
<%@ Page Language=”VB” %>
<%@ Import Namespace=”com.esri.rmims” %>
<%@ Import Namespace=”system” %>
<%@ Import Namespace=”system.data” %>
<%@ Import Namespace=”System.Data.SqlClient” %>
<%@ Import Namespace=”npgsql” %>
Next we’ll have some public functions to nab some of the necessary RouteMapIMS server variables. Note I’m grabbing these from the web.config from a standard ASP.NET output from Map Author.
Public Function OpenMap()
Dim conn, map
conn = new IMSConnection()
conn.setConnectionURL( GetConfigStr(“par_ServerUrl”) )
conn.setGroup( GetConfigStr(“par_Groupid”) )
conn.setUserName( GetConfigStr(“par_Uid”) )
conn.setLocale( GetConfigStr(“par_Lang”), GetConfigStr(“par_Country”) )
map = conn.loadMap( GetConfigStr(“par_MapName”) )
‘ set image size
map.setImageSize( GetConfigInt(“par_Width”), GetConfigInt(“par_Height”) )
‘ set location
location = new Location()
‘ set measure units
map.setMeasureUnits( GetConfigInt(“par_Units”) )
OpenMap = map
Public Function GetConfigStr(keyName As String) As String
GetConfigStr = CStr(ConfigurationSettings.AppSettings(keyName))
Public Function GetConfigInt(keyName As String) As Long
GetConfigInt = CInt(ConfigurationSettings.AppSettings(keyName))
Now we’ll create a class to handle our stops.
Sub New( map, ilabel, ilat, ilon)
Dim proj, pt
proj = map.getProjection()
pt = proj.project( ilat, ilon)
label = ilabel
x = pt.x
y = pt.y
Finally we make a function to set the map extent.
Function inflateRect(ByRef r, percVal)
Dim dx, dy
dx = ((r.right - r.left) * percVal) / 100.0
dy = ((r.top - r.bottom) * percVal) / 100.0
r.left = r.left - dx
r.top = r.top + dy
r.right = r.right + dx
r.bottom = r.bottom - dy
inflateRect = r
Phew! That’s a lot of set up just to try this out. If you can imagine the PC writing this, you can insert a good deal of swearing between the GetConfigInt function and the end of the inflateRect function (fortunately ESRI had some sample code that stopped outright mouse-rage). Now let’s look at some real code.
Here we set up some of our base variables.
Dim map : map = OpenMap()
Dim oRouting, DSeg, rProblem, i, rStop, RouteID, r, DDirs
‘ get the RoutingProblem object
rProblem = map.getRouting().createRoutingProblem()
‘set the number of stops
dim n_stops as integer = 35
Next we’ll get some random addresses from the master address table. This was interesting in itself - the NEWID() function in SQL Server randomly makes a new unique ID column on the table so new random records are grabbed every time. This isn’t exactly an efficient SQL query, so you should probably make sure your database administrator is significantly smaller than you before you try it.
‘Get random addresses from MAT
Dim myReader a
Dim mySqlConnection as SqlConnection
Dim mySqlCommand as SqlCommand
mySqlConnection = new SqlConnection(“server=’server’; user id=’username’; password=’password’; database=’database’; pooling=false;”)
mySqlCommand = new SqlCommand(“SELECT TOP “ & n_stops & “ num_x_coord, num_y_coord, txt_street_number + ‘ ‘ + rtrim(nme_street) + ‘, ‘ + nme_city as address FROM reltables.sde.tb_physical_address where num_x_coord > 0 and cde_status = ‘A’ ORDER BY NEWID()”, mySqlConnection)
myReader = mySqlCommand.ExecuteReader()
Next we’ll make a connection to PostgreSQL so we can use one of it’s functions to transform the master address table coordinates from state plane to decimal degrees.
‘open postgres connection
Dim conn As NpgsqlConnection = New NpgsqlConnection(“Server=server;Port=5432;User Id=username;Password=password;Database=database;”)
Dim command As New NpgsqlCommand
command.connection = conn
Dim dr As NpgsqlDataReader
OK, now let’s run some code. We’re going to make an instance of our GeoLocation class and add our addresses to it. Note the SQL code here - we’re using a select statement in PostgreSQL and it’s transform function to project the coordinates to decimal degrees.
Dim stops(n_stops) as GeoLocation
dim n_counter as integer = 0
do while (myReader.Read())
command.commandtext = “select x(transform(GeomFromText(‘POINT(“ & myreader(“num_x_coord”) & “ “ & myreader(“num_y_coord”) & “)’, 2264), 4326)) as xcoord, y(transform(GeomFromText(‘POINT(“ & myreader(“num_x_coord”) & “ “ & myreader(“num_y_coord”) & “)’, 2264), 4326)) as ycoord”
dr = command.ExecuteReader()
stops(n_counter) = new GeoLocation( map, myreader(“address”), dr.Item(“ycoord”), dr.Item(“xcoord”))
n_counter = n_counter + 1
Next we’ll add the stops to our routing problem.
‘ add routing stops
For i = 0 To UBound( stops) - 1
rStop = new RoutingStop
rStop.setStop( new GeoPoint( stops(i).x, stops(i).y))
Finally we can set our routing parameters and output the route:
rProblem.setWeight( RoutingProblem.rmShortest) ‘ to find quickest use rmQuickest
rProblem.setOptimize( true) ‘ optimization - set true for traveling salesman
oRouting = map.getRouting()
RouteID = oRouting.findRoute(rProblem, true, -1)
‘ show the route
r = oRouting.getDrivingDirections( RouteID).getExtent()
map.setExtent( inflateRect(r, 10)) ‘ increase borders
‘ print driving directions
DDirs = oRouting.getDrivingDirections( RouteID)
Response.Write( “<p>” & DDirs.getStartText() & “<br>” & vbCrLf)
Response.Write( DDirs.getFinishText() & “<br>” & vbCrLf)
Response.Write( DDirs.getTotalText() & “<p>” & vbCrLf)
For i = 0 To DDirs.getSegmentCount()-1
DSeg = DDirs.getSegment( i)
Response.Write( (i+1) & “. “ & DSeg.getText() & “<br>” & vbCrLf)
‘ if there is TimeLengthText
If DSeg.getSegmentType <> DirectionsSegmentType.rmArrive AND _
DSeg.getSegmentType() <> DirectionsSegmentType.rmDepart Then
Response.Write( DSeg.getTimeLengthText() & “<br>” & vbCrLf)
If we want to dump out the map as well, in the HTML portion of the page we can use:
<img src=”<%= map.getMapImageURL(map.getImageWidth(), map.getImageHeight(), ImageFormat.rmDefault)%>”
Wow - the PC is worn out just from copying and pasting. It works, however, and that’s the main thing. You can do a traveling salesman problem with 50 addresses (more than hopefully anybody will need on a given day) in about 15 seconds. A more realistic 20 addresses goes in under 10 seconds. Viola - the traveling salesman can make his or her rounds without having to buy fantastically expensive software.
Of course, there is an obvious problem. If you have a colletion of 25 addresses you need to visit, for your traveling salesman solution to be worth it’s weight in blog space, all 25 really need to match. If you have 25 stops to make and someone gives you an optimized route for 20 of them, what good is that? A few different stops may change the route entirely, and you have a route that won’t get you everywhere you need to go in any event. That helps to emphasize why we should be validating all of our addresses - not just in GIS, but with any system that enters an address.
Enjoy, and if you do come up with a mathematical solution to the TSP, a thank you to the PC somewhere in your Nobel acceptance speech would be greatly appreciated.