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.
Map from http://www.freeworldmaps.net/asia/southeastasia/physical.html
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.
Please send me email if you would like to learn more about this and keen to get the Excel Solver TSP model.