The “traveling salesperson problem” has a long history in operations research. A traveling salesperson must visit each of n cities exactly once, minimizing the total cost of travel and returning to the city of origin. What route should be taken? If the cities form a nice circle, the answer is obvious. However, in other cases the answer is not obvious at all, and, due to potential backtracking, it is often not best to go to the next-closest city upon leaving one. This problem applies to other decisions as well, such as vehicle routing problems and certain job scheduling problems.

We define dij as the distance (or cost) of going from city i to city j. We further define the following binary decision variables:

At first glance, it would appear that this can be set up as an assignment model (section 5.6) because we need constraints ensuring that every city is entered exactly once and every city must be left exactly once. That’s not enough, however. Formulating the traveling salesperson problem as an assignment model would not eliminate “subtours,” meaning, for example, that an answer for a four-city problem might come back as X₁₂ = 1, X₂₁ = 1, X₃₄ = 1, and X₄₃ = 1, in which case there’s nothing connecting cities 1 and 2 to cities 3 and 4. The ingenious answer to the subtour problem is to introduce a set of additional constraints that will eliminate any subtours. These constraints utilize regular nonnegative variables ti, one for each city i except for city 1.

The formulation is provided below. Create a template in Excel, including all the appropriate Solver settings, that would accommodate a standard traveling salesperson problem with 5 cities. (Note: The traveling salesperson formulation is computationally cumbersome. Adding each new city significantly increases solution time. After about 10 cities, more powerful software than Excel should probably be used.)

Transcribed Image Text:

J1 if city j is visited immediately following city i X; = O otherwise