Tuesday, May 27, 2014

Travelling Salesman Problem in Excel Solver

Excel Solver - Using the

Alldifferent Constraint

and the Evolutionary

Method To Select the

Shortest Path That

Reaches All Customers

This is a classic Solver problem that provides a great opportunity to illustrate the use of the Alldifferent Constraint and the Evolutionary Solver. A travelling salesman must visit a given number of customers and pick the shortest path that will reach every customer and bring him back to his starting point.

The Alldifferent Constraint is used to ensure that the salesman visits each customer only once. The Evolutionary method is used because the mathematical path to the Objective contains the Excel Index lookup function, which is a discontinuous function.

 

The Travelling Salesman Problem

A travelling salesman living in Chicago must make stops in these 4 other cities: LA, Denver, Boston, and Dallas. He must start and finish in his home city of Chicago. He must select the order of customers to visit that will minimize the total length of the trip.

Below is the specific information about the distances between each of the 5 cities:


excel solver, solver, travelling salesman problem, traveling salesman problem, excel 2010, excel 2013, optimization (Click Image To See an Enlarged Version)

 

Solver Problem Solving Steps

 

Step 1 – Determine the Objective

In this case, the objective is to minimize the total distance traveled when traveling between all 5 cities. The total distance traveled by the salesman is the Objective to be minimized.

 

Step 2 – Determine the Decision Variables

We are trying to select the order of cities to visit that minimizes the total distance travelled. The cities are designated in the Excel model not by their names but by the row that they appear in the distance chart just shown.

Boston appears in the 1st row of the distance chart. Boston is therefore designated with a “1.” Chicago appears in the 2nd row in the chart and is therefore assigned a designation of “2.” Dallas appears in the 3rd row and is designated “3.” Denver appears in the 4th row and is designated “4.” LA appears in the 5th row and is designated “5.”

We need to determine the order of cities to visit to minimize the total miles travelled. In other words, we are minimizing the sum of distances travelled between consecutive cities.

 

Step 3 – Build the Excel Equations That Combine the Objective With All Decision Variables

excel solver, solver, travelling salesman problem, traveling salesman problem, excel 2010, excel 2013, optimization (Click Image To See an Enlarged Version)

 

Column C – Decision Variables

The Decision Variables are the arrangement of the cities to visit. In the preceding diagram, the Decision Variables are the row designations of each city. These Decision Variables are in cells C10 to C14. The order of the Decision Variables shown above (1, 2, 3, 4, 5) indicate that the cities will be visited in this order: Boston (row 1 in the Distance Chart) to Chicago (row 2 in the Distance Chart) to Dallas (row 3 in the Distance Chart) to Denver (row 4 in the Distance Chart) to LA (row 5 in the Distance Chart) and back to Boston.

This set of 5 Decision Variables are collectively subject to the Alldifferent Constraint. As a result, each 1 of these 5 Decision Variables will be assigned an integer between 1 and 5. None of the 5 Decision Variables in this set can be assigned the same number.

 

Column D – Listing The Cities Attached To Decision Variables

The Excel Index function is used in column D to list the city which corresponds to the Distance Chart row number that appears in column C. For example, cell D10 contains the Excel formula:

=INDEX($B$3:$B$7,$C10,1)

The Index function has the following syntax:

=INDEX(range, row number, column number)

For the above formula, the range is the cells from B3 to B7. This is a range of cells that has only 1 column.

The row number referenced in this Index function is in cell C10. The contents of Cell C10 = 1. The row referenced by this Index function is the 1st row.

The column number referenced in this Index function is 1. This would have to be the case since only 1 column exists within the given range (B3 to B7).

The Index function displays the contents of the cell in the given row (1st row) and column (1st column) of the given range. This Index function will display the contents of the cell in the 1st row and the 1st column of the given range (B3 to B7). The cell in the 1st row and the 1st column of cell range (B3 to B7) is cell B3. Cell B3 contains the word Boston, which is displayed in cell D10.

 

Column E – Calculating Distances Between Each City and the Previously Visited City

The distances between each city and the previous city visited are shown to the right in column E. For example, the distance between Boston and the previous city of LA is 3036 miles. The distance between Chicago and the previous city of Boston is 983 miles. The distance between Dallas and the previous city of Chicago is 1205 miles. The distance between Denver and the previous city of Dallas is 801 miles. The distance between LA and the previous city of Denver is 1174.

Distances between each city and its previous city are found by using the Index function. This function looks up in the Distances chart and locates and displays the distance between a city and its previously visited city.

The distances shown in Column E are as follows:

The distance between Boston and the previous city of LA is 3036 miles.

The distance between Chicago and the previous city of Boston is 983 miles.

The distance between Dallas and the previous city of Chicago is 1205 miles.

The distance between Denver and the previous city of Dallas is 801 miles.

The distance between LA and the previous city of Denver is 1174.

The Excel Index functions which generated each of these distances are shown to the right of each distance. An explanation of this use of the Index function is as follows:

The Index function has the following syntax:

=INDEX(range, row number, column number)

For the above formula, the range is the cells from C3 to G7. This cell range holds the distances in the Distance Chart.

The row number corresponds to the previous city visited. This row number is the previous city’s row number in the Distance chart.

The column number corresponds to the current city. This column number is the current city’s column number in the Distance chart.

All of the distances between cities are listed in cells C3 to G7. The Index function locates the cell that holds the distance between each city and the previous city. Each distance will be found in the row number of the that previous city and column number of the current city.

The order of the cities (actually, the order of the city row numbers in column C) are arranged so that sum of the distances between each city and the previous city is minimized.

 

Step 4 – List All Constraints

This problem provides an excellent opportunity to showcase the Alldifferent Constraint. We are visiting each city only once so we need each city (actually the city’s row number in the Distance Chart) to be listed only one time without repeating.

Each city’s unique row number in the Distance Chart must be assigned to only 1 of the 5 Decision Variable cells. We must therefore apply the Alldifferent Constraint to all of the Decision Variable cells (cells C10 to C14) simultaneously as a group. As a result of the Alldifferent Constraint, these 5 cells will hold the integers 1 to 5. No 2 cells in this group will be assigned the same number. This ensures that each city will be visited only once and that all cities will be visited.

The following Solver Dialogue box shows the set of 5 Decision Variables (Cells C10 to C14) subject collectively to the Alldifferent Constraint.


excel solver, solver, travelling salesman problem, traveling salesman problem, excel 2010, excel 2013, optimization (Click Image To See an Enlarged Version)

 

Step 5 – Test the Excel Spreadsheet

This spreadsheet can be very easily tested by varying the integer values in the Decision Variable cells (cells C10 to C14). The city names and distances between cities should correctly change to match the new Decision Variable integer values corresponding to different rows.

 

Step 6 – Insert All Data into the
Solver Dialogue Box

Once again here is the completed Solver dialogue box:


excel solver, solver, travelling salesman problem, traveling salesman problem, excel 2010, excel 2013, optimization (Click Image To See an Enlarged Version)

The Travelling Salesman Problem provides an excellent opportunity to demonstrate the use of the Evolutionary method. The Evolutionary method must be used if the Mathematical Path to the Objective contains any cells holding non-smooth or discontinuous formulas.

Common non-smooth Excel functions are MIN, MAX, and ABS.

Common discontinuous Excel functions are INDEX, HLOOKUP, VLOOKUP, LOOKUP, INT, ROUND, COUNT, CEILING, FLOOR, IF, CHOOSE, NOT AND, OR, GREATER THAN, LESS THAN, and EQUAL TO.

The INDEX function in this problem appears in cells that are part of the Clear Mathematical Path to the Objective. We therefore must select the Evolutionary method to solve this problem.

After we have selected the Evolutionary method, we hit Solve and solution shown in several pages is reached.

This solution could be interpreted as follows:

The salesman stars in his home town of Chicago. He then visits Denver, LA, Dallas, Boston, and finally back to Chicago in that order. The total miles travelled on this route are 6,447 miles. This is the shortest route that will cover all 5 cities starting and ending in Chicago.

Note that no special provision has to be made to ensure that the starting point is Chicago.

Following are views of the Excel model before solving and then after solving with Excel Solver’s Evolutionary method:

Before Running Solver


excel solver, solver, travelling salesman problem, traveling salesman problem, excel 2010, excel 2013, optimization (Click Image To See an Enlarged Version)

 

After Running Solver


excel solver, solver, travelling salesman problem, traveling salesman problem, excel 2010, excel 2013, optimization(Click Image To See an Enlarged Version)

 

Solver Answer Report

 

Part 1

Note:

- The Solver Result

- How long Solver took to solve the problem (especially important in this case – This time could be reduced by several of the Options settings.)

- The Solver Engine that was used and the Solver Options settings

- Where the Objective Cell was labeled in the Excel model for its name to appear as it does in Part 1 of the Answer Report


excel solver, solver, travelling salesman problem, traveling salesman problem, excel 2010, excel 2013, optimization
(Click Image To See an Enlarged Version)

Note the solution time of 164 seconds. This could have been reduced by limiting the maximum allowable run time, iterations, or subproblems using the Options menu.

 

Part 2 – Variable Cells

- Note that the Variable Cells contain the Decision Variables

- Note where the labels for each Decision Variable are placed in the Excel model so that the Decision Variable’s name will appear here in Part 2 of the Answer Report as it does

- Note the type of variable - Either Continuous or Integer (Integer, Binary, or Alldifferent)

- Note the Before and After values of each Decision Variable

 

Part 3 - Constraints

- Note how each Constraint is labeled in the Excel model in order for the Constraint’s name to appear here in Part 3 of the Answer Report as it does.

- Note which Constraints are binding (had their limits hit) and which aren’t.

- Note how much slack is still available in any Constraint that has not had its limit hit.

- Note any Integer Constraints (Integer, Binary, Alldifferent)


excel solver, solver, travelling salesman problem, traveling salesman problem, excel 2010, excel 2013, optimization
(Click Image To See an Enlarged Version)

Note that Cells C10 to C14 were set to AllDiff simultaneously as a group.

 

Solver Population Report

The Population Report is made available when the Evolutionary method is used. The Population Report provides indication about whether and how you can make improvements to the model or to the Evolutionary method Options.

The Population Report can be valuable if successive runs of the Evolutionary method produce different answers for the Objective. The setting of the Mean Value and Standard Deviation during successive runs provide insight into whether your successive solutions are getting closer to the most optimal solution. See the section on a detail description of this report for more information about this topic.


excel solver, solver, travelling salesman problem, traveling salesman problem, excel 2010, excel 2013, optimization (Click Image To See an Enlarged Version)

 

Excel Master Series Blog Directory

Statistical Topics and Articles In Each Topic

 

Posted by at

4 comments:

  1. ALLAN SAMJune 19, 2018 at 10:20 PM

    Hi, Great work. I have also have an video here explaining the TSP and solution in excel. https://www.youtube.com/watch?v=fQLBn6p6dp4
    hope this helps for all.
    gud day!

    ReplyDelete
  2. TSPJuly 16, 2018 at 6:11 AM

    Here is the video tutorial

    ReplyDelete
  3. aws cloud databasesJuly 25, 2022 at 7:36 AM

    we are here to facilitate you with the best. Oscale can assist you to migrate and updating your legacy databases on the AWS cloud platform

    ReplyDelete
  4. Tall Escorts Daly CityNovember 7, 2024 at 8:18 PM

    Hi nice readiing your blog

    ReplyDelete

Subscribe to: Post Comments (Atom)