ABSTRACT
A sales person is planning a business trip that takes her to certain cities in which she has customers (or jobs to perform) and then returns her back home to the city in which she started. Between some of the pairs of cities she has to visit, there is direct air service; between others there is not. Can she plan the trip so that she (a) begins and ends in the same city while visiting every other city only once, and (b) pays the lowest price in airfare possible (assuming she can only buy direct air tickets)? The goal is not just finding a solution—a tour that visits every city on the agenda once—but an optimal solution, one with the lowest airfare.
