Touring Montana

by Vince Devlin

Quick: What’s the fastest way to visit all 56 Montana county seats?

The answer depends on whether you’re a crow or a computer whiz. A crow can fly the shortest route in 2,469.64 miles. That would allow it to zip over the Bitterroot Mountains from Hamilton to Superior while skipping Missoula, and make straight shots from Terry to Baker and from Baker to Ekalaka and Broadus. Following roads, that crow would drive 3,147 miles.

So figures Jim Ullrich, a retired University of Montana computer science professor.

Montana’s mountains and rivers force some lengthy detours. On the map, Ullrich’s path from Anaconda to Deer Lodge to Butte to Boulder to Helena looks like a jagged EKG around the Continental Divide.

“I had no idea where a lot of these places were,” Ullrich said of his midwinter mind exercise on Montana geography. “And there were a couple I’d never heard of.”

It was also an exercise in the “traveling salesman” problem – find the most efficient route through a set
of unequal distances. Politicians love to claim they’ve visited all 56 counties in the 147,040 square miles of Big Sky Country. If they wanted to stand before every courthouse door, what’s the best route?

Until recently, humans and computers were on almost equal footing trying to crack a big traveling
salesman task. That’s because there’s no good algorithm – no formula – for finding an answer. The
computer simply has to tally up each possible route and announce the shortest.

Shortest-route-to-all-county-seats-proofIf that seems simple, consider that Ullrich’s problem involves 56 stops. That requires a factorial equation
to solve: 56x55x54x53 … x3x2x1=? (Actually, it’s the “!” key on your kid’s fancy programmable calculator, if you want to get punctual).

That produces a number with 75 digits. And that’s not the answer. That’s just the number of tests you’ve
got to make to get the answer.

Cory Palmer specializes in the mathematical discipline of combinatorics – the study of counting and combinations. The traveling salesman problem falls in that field, and it remains a puzzler.

“It’s one of the most famous problems known as NP-Complete,” Palmer said from his office at the
University of Montana. “That’s a class of problems we don’t know how to solve quickly. It’s quite possible
there’s no solution. Computer power is just so massive, but we’re still brute-forcing it.”

At the Missoula Children’s Theatre, they don’t even try. MCT’s iconic Little Red Trucks deliver pairs of
actors/teachers to hundreds of schools throughout North America year-round. Right now, 33 trucks are
traveling from Texas to Saskatchewan, Florida to Washington, every Sunday between shows.

“We are not efficient in that regard at all,” MCT marketing director Jonna Michelson said of the
route planning.

“There are so many variables at play in making a residency week successful. We have to find a piano player, lodging for the team, make sure we’re not returning a show the community has had recently, what passes are safe to drive, whether the parks are open to get through. The teams have a schedule in advance, but most of the routing is done on the ground, weekly.”

Semitrailer drivers confront that all the time.

“It’s always a challenge,” said Dave Wanzenreid, a former Missoulian who retired from Watkins and
Shepard Trucking five years ago. “You’re always trying to figure out the shortest distance and the least gas. But you can look at the map and say – no that doesn’t make any sense. You can’t drive a truck from A to B legally – you’ve got to find something different.”

Ideally, a trucker would pick up a load of machinery in Iowa, and have drop locations in South Dakota, Montana and Oregon. But then something comes up, or something gets misplaced, and you’re driving from Billings to Seattle by way of Laramie.

“Usually you’re just responding to someone saying,‘Can you do this?’ ” Wanzenreid said. “Life is never
predictable.”

Edulog, the Missoula-based company specializing in traffic routing, does this for school buses all the
time. Ullrich knew some of the folks who founded that company – their initial crack at reprogramming
the Great Falls school buses saved the district about $100,000 in the first year.

Ullrich wasn’t trying to save gas money on next summer’s road trip across Montana. He was enjoying
the boost in computer power he’s experienced over the years.

“When I started, the first computer language I used would take a couple of years to make a program that
would solve a problem,” he said. “The next language I learned could do it in a summer. The third language could do it in about three pages of code. For this, it only took me three lines of code.”

Ullrich used a program called Mathematica, based on the Wolfram computer language. Most of us
picture computer language as a series of commands: “multiply,” “divide,” “sort,” “copy.” Mathematica has a command “find shortest tour” that swallows the whole city mileage index in the lower left corner of
the Montana state road map and spits up a traveling salesman route.

“Another line of code built the whole graph,” Ullrich said.

“Typing in the names of the towns and the mileages was more work than writing the program itself.”

Mathematica has more purpose than helping Ullrich figure out it’s more efficient to go from Kalispell south to Hamilton rather than east to Cut Bank.

The program juggles multiple variables that tell an aircraft engineer how much more weight a wing
design can carry when it gets longer or wider, or how many office floors an architect will gain by using a
different earthquake reinforcement.

It helps stock brokers make sense of company valuations and sports bookies predict Super Bowl outcomes. But the traveling salesman problem remains on the outer edge of its capability.