05 Jun Intelligent Traveling Salesmen

Another Sample Problem

Several specific reasoning or inference problems have provided fodder for AI textbooks and experiments. One of these is the traveling salesman problem (Get an explanation and an example applet here):

• Given a traveling salesman who must get to x number of cities,
• find the shortest route the salesman can travel to reach them all.

In our quaint, large midwestern county, we have a river, ten towns, and some roads whose distances we know. We must start and end in Deville, our home town. For today’s problem, we will simply assume that we must get to all ten towns. Next month we will add four more towns and calculate hotel rates. Before long, we will need to budget the amount of time we spend in each town based on its population and make sure our driving times all occur within daylight hours.

Understanding Context Cross-Reference
Click on these Links to other posts and glossary/bibliography references

Section 7 #13

Table of Context

No matter how many constraints we add, we can use computers to solve the traveling salesman problem simply by creating a data structure for the model, creating rules that constrain the possibilities, searching through it for all possible answers, then choosing the best one out of the bunch. This is not, however, the most elegant approach. By creating search trees, then traversing the paths, we may be able to speed the search for an optimum answer, and possibly avoid searching parts of the space that cannot provide an answer.

The more we choose to use search to solve problems, the more critical it is for us to develop eloquent searching approaches to increase system efficiency. Some of MIPUS‘s problems may seem simple compared to the traveling salesman problem, but because of the fuzziness of MIPUS’s options, his problems may actually be more difficult.

DIRECTS System: Banta Catalog Group

I was once asked to solve an instance of this problem with a large number of constraints and possibilities. In this application, the company, who printed direct mail marketing materials and catalogues, needed to minimize mailing costs by drop-shipping to the lowest level postal facility. The lower the level, the greater the savings per piece of mail compared to putting them in the mail stream at the printing location in Minnesota. The mail was sorted, so we knew which local post office each piece went to, and we knew which of the 180 Sectional Center Facilities (SCFs) served the post office, and which of the 32 Bulk Mail Centers (BMCs) served the SCF.

DIRECTS (I forgot what the acronym means) uses a combination of forward chaining rules and visual cues to make very complex decisions about how to most “drop ship” printed materials into the postal stream as close to the destination mailbox as is cost-effectively possible. At the time, the US Postal Service gave printers like Banta postage fee discounts for drop shipping the materials they printed at the BMCs and SCFs closest to the final recipient – the closer, the better the discount. Each of the companies that created the materials provided “windows” of time in which the materials were to arrive. The rules, therefor, were a combination of the “Traveling Salesman” problem with multiple additional constraints including the capacity of the truck, the number of pieces for each BMC or SCF, the time the materials are expected to come off the press vs. all other materials from the printer going to the same postal region, and several other constraints.

To handle the complexity and the unknown variables of when the materials were actually completed, I developed a forward chaining inference system to do the heavy lifting of routing the trucks most efficiently and assigning the 20 million pieces of mail per week to the trucks. This is the bottom up or forward-chaining component. I then built a “person-in-the-loop” visual display of US geography, the trucks, their loads and destinations to add the manual top-down or goal-oriented rules in which an experienced planner could visually adjust the loads and the routes as unexpected events changed the constraints. The system saved the company more than 10 times what they paid me to build it in the first year and continued to get smarter thereafter.

With a forward-chaining inference model a graphical interface, in the first year of operation, we were able to save the company 15x the cost of developing the software. Is it possible that intelligent traveling salesmen will plug the cities into their smart phone and let it tell them where to go when? There may already be an app. The knowledge-based computers of the future should be able to do that as one of many core capabilities. If we can get them to be able to understand human intent through language, this would be a trivial add-on, possibly using the same core pattern matching and reasoning heuristics.

Click below to look in each Understanding Context section

Leave This Blank:Leave This Blank Too:Do Not Change This:

Your email: