# TSP

## Travelling Salesman Problem (TSP)

A person wants to travel all cities. The travel will start from a city, with each city visited only once, and return to the original city after all cities visited. The objective is to minimize the travel distance / cost.

The TSP problem is highly popular in computer science field. It was first defined in 1800. TSP problem is difficult to solve. It is an NP-hard problem. That means if there are n cities to travel, there are (n-1) factorial possibilities for the travel sequence. Assuming similar distance for both travel directions between two cities, for a 10-city problem there will be 9!/2 or 181,440 combinations to try.

The complete TSP formulation with sub-tour elimination can be written as follows:

Let’s try to solve 10 ASEAN capital cities problem. This is relatively a large problem but thanks to today’s powerful computing hardware and software, we can even solve this using Excel Solver.

The distances between the cities are as follow.

 Country Capital Airport BWN PNH CGK VTE KUL NYT MNL SIN BKK HAN Brunei Bandar Seri Begawan BWN 1330 1534 1977 1487 2603 1255 1278 1833 2060 Cambodia Phnom Penh PNH 1330 1975 757 1038 1289 1782 1138 504 1081 Indonesia Jakarta CGK 1534 1975 2719 1129 3083 2788 882 2297 3042 Laos Vientiane VTE 1977 757 2719 1697 694 2007 1857 517 495 Malaysia Kuala Lumpur KUL 1487 1038 1129 1697 1970 2490 297 1221 2102 Myanmar Naypyidaw NYT 2603 1289 3083 694 1970 2696 2202 819 1016 Philippines Manila MNL 1255 1782 2788 2007 2490 2696 2375 2188 1773 Singapore Singapore SIN 1278 1138 882 1857 297 2202 2375 1417 2218 Thailand Bangkok BKK 1833 504 2297 517 1221 819 2188 1417 995 Vietnam Hanoi HAN 2060 1081 3042 495 2102 1016 1773 2218 995

We enter these data into an Excel spreadsheet. We also setup a rectangle area in the Excel which will be used as decision variable in the model.

The formulations and named ranges required are shown below.

We need to enable Excel Solver before we can use it. From Excel, select File then Option. Select Add-Ins. The Add-Ins manager will then appear. At the bottom of the screen, hit the “Go” radio button next to Manage Excel Adds-Ins. Check the Solver Add-In box and Solver will be enabled. To access Excel Solver, go to Data and the Solver radio button will appear.

The TSP mathematical formulation are partially in the spreadsheet cells. We need to enter the objective cell, decision variables, and the constraints into Excel Solver dialog box as shown below.

Hit Solve to get the solution as shown below.

The solution above can be shown graphically as below:

The TSP textbook formulation can be applied directly to solve real-world problems. In electronic assembly, TSP is used to minimize drill head travel during PCB drilling and component placement time by surface mount machines. An extended version of TSP model is used by transportation companies to decide the routes of pickup and delivery vehicles.