Getting From Here to There

Can you remember the first time you came across the Traveling Salesman Problem? "Given a number of cities and the costs of traveling from any city to any other city, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city?"

Yi-Chang Chiu, an assistant professor of Civil Engineering and Engineering Mechanics at the University of Arizona, probably can. While not necessarily tackling the Traveling Salesman Problem, Yi-Chang Chiu has cranked up a notch or two investigations into traveling from one place to another. In his case, Chiu is interested in moving people -- lots of people, not just a single salesman -- in response to some catastrophe, such as a terrorist attack or natural disaster.

"Solving large-scale evacuation problems is overwhelming," Chiu said. "No one can just sit down with a map and draw lines and figure out the best answer to problems like these." (Now he tells me. Pencil and paper was exactly the approach I took the first time I saw the TSP. And I quickly understood the benefit of having a computer handy.) So instead of pencil and paper, Chiu and his team have developed software that can react to a situation in real time, adjusting as conditions on the ground change.

The next generation of the software, currently under development by Chiu, Pitu Mirchandani, and Mark Hickman, is called "Multi-Resolution Assignment and Loading of Traffic Activities" (MALTA), and is designed to respond minute-by-minute to real-time emergencies via parallel processing.

The software package depends on detailed traffic census data that is collected by state and city transportation departments in conjunction with real-time traffic surveillance data. It then considers decisions each driver might make on factors such as when to leave, which route to take, if they listen to radio reports and change their route, if they are slowed by congestion and change routes, or if they react to freeway message boards that carry routing advisories.

Chiu has also used the software to model "value pricing" on toll roads.This concept is uses a sliding toll scale to manage congestion. As traffic increases, the toll increases incrementally to a maximum amount. This information is broadcast to drivers in various ways, with the hope that they will choose a different route, use public transit or delay their trip.

But value pricing on toll roads isn't an academic research project. For instance, based on the results of a seven-month pilot project in Stockholm, Sweden has adopted a road charging system designed by IBM and the Swedish Road Administration. This project saw peak-time road traffic congestion dramatically reduced, air pollutants cut by up to 12 percent, and public transport usage increased by around 40,000 commuters a day. IBM will proceed with the city-wide road charging roll-out in August 2007.

The Stockholm system -- the largest of its kind in Europe -- has 18 barrier-free control points around the charging zone equipped with cameras and a beacon system to identify vehicles and provide evidence to support the enforcement of non-payers. Payment channels include automatic direct debit, a Giro system at banks, over the Internet, and at retail stores such as 7-11.

For more information on road use charging, see the IBM paper entitled Driving the Future of Road User Charging.

And for hands-on (but not behind the steering wheel) experience traffic scheduling, try Mark Hickman's Transit Scheduling Game.

Posted by Jon Erickson at 10:22 AM  Permalink