Help with GIS routing software?

February 6, 2005 5:18 PM

Need some advice on GIS route software.

Let's say hypothetically that I had one van and knew that I could sell X number of widgets in each city of a particular state per day. Anyone aware of a driver route simulation program that can use weighted business opportunity to create a maximized daily itinerary?

posted by machaus to computers & internet (3 comments total)

Some background on your problem...
posted by tss at 5:28 PM on February 6, 2005

Despite the traveling salesman problem's intractability, I'd be surprised if somebody hadn't done something with this... there are pretty good heuristics and even complete solutions for maps with a small number of nodes...

But I'm not, unfortunately, familiar with any software that does what machaus asks.
posted by weston at 8:11 PM on February 6, 2005

The Network Analysis module of ESRI's Arc/Info will do this -- as weston suggests, it is done with a heuristic but produces essentially indistinguishable results from a complete solution for most applications. The travelling salesman heuristics are widely used in "location-allocation" and other distribution problems in transport and retail geography. They take a lot of processor grunt to do so. My limited exposure to this involved setting up a 575 node, >3500 vertice location-allocation problem; it would take my old SG Indy overnight to run 25 iterations, though you could probably do that on a PalmPilot these days.

To weight your business day, so to speak, requires using dynamic segmentation in a program like Arc/Info. Businesses use this for things like, "how do different traffic densities at different times of day affect access to our gas station". Similarly, one can then assign supply and demand at different nodes and search for optimal solutions that go beyond travelling salesman optimality based on vertices, and include economic and cultural attributes of the network nodes. These are widely used for public and private sector facility locations which need to optimize some objective function (e.g., place a fifth school in a school district with four existing schools so that the fewest possible children are more than a twenty minute ride to school at 8.30 a.m. and a fifteen minute ride home at 3.30 pm - this would be a maximum coverage location-allocation model but much simpler implementations - p-median for example - are less assumption ridden)

Overall, the complexity of the problem has yielded somewhat to computer processing advances, but in large network applications, the cutting edge is using distributed software, so called "ants," which can produce optimal real-time solutions as an emergent phenomenon with no centralized control. As a distributed software solution this makes the system much more stable and requires far less processing power, at the expense of no-one knowing exactly how it is working at any given times.

See here for the software I used - Arc/Info is very expensive though widely available at universities - its still basically a unix app. Its dumbed down PC application Arc/View is still expensive (base module + network analysis module will cost you ca. $3,000; the full Arc/Info (6? modules) for a PC much more than that. If you are a student you can get big educational discounts.

There are probably much cheaper standalone programs that will do this -- its basically a matrix/graph theory problem. However, the visual interface of a GIS is invaluable for setting up your problem.
posted by Rumple at 8:54 PM on February 6, 2005