on Code

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”) )
conn.setCharset(“”)

map = conn.loadMap( GetConfigStr(“par_MapName”) )

‘ set image size
map.setImageSize( GetConfigInt(“par_Width”), GetConfigInt(“par_Height”) )

‘ set location
Dim location
location = new Location()
location.setString(GetConfigStr(“par_Location”))
map.setLocation(location)

‘ set measure units
map.setMeasureUnits( GetConfigInt(“par_Units”) )

OpenMap = map
End Function

Public Function GetConfigStr(keyName As String) As String
GetConfigStr = CStr(ConfigurationSettings.AppSettings(keyName))
End Function

Public Function GetConfigInt(keyName As String) As Long
GetConfigInt = CInt(ConfigurationSettings.AppSettings(keyName))
End Function

Now we’ll create a class to handle our stops.

Class GeoLocation
Public label
Public x
Public y

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
End Sub
End Class

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
End Function

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
s
SqlDataReader
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)
mySqlConnection.Open()
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;”)
conn.Open()
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”) &amp; “ “ & myreader(“num_y_coord”) & “)’, 2264), 4326)) as xcoord, y(transform(GeomFromText(‘POINT(“ & myreader(“num_x_coord”) &amp; “ “ & myreader(“num_y_coord”) & “)’, 2264), 4326)) as ycoord”
dr = command.ExecuteReader()
dr.Read()
stops(n_counter) = new GeoLocation( map, myreader(“address”), dr.Item(“ycoord”), dr.Item(“xcoord”))
n_counter = n_counter + 1
loop

conn.Close()

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))
rStop.setLabel( stops(i).label)
rProblem.addStop (rStop)
Next

Finally we can set our routing parameters and output the route:

rProblem.setHighwayPreference( 50)
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
oRouting.setRoute( RouteID)
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)
End If
Next

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)%>”
width=”<%=map.getImageWidth()%>” height=”<%=map.getImageHeight()%>”>

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.