# 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:

*(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 1^{st} row of the distance chart. Boston is therefore designated with a “1.” Chicago appears in the 2^{nd} row in the chart and is therefore assigned a designation of “2.” Dallas appears in the 3^{rd} row and is designated “3.” Denver appears in the 4^{th} row and is designated “4.” LA appears in the 5^{th} 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

*(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 1^{st} 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 (1^{st} row) and column (1^{st} column) of the given range. This Index function will display the contents of the cell in the 1^{st} row and the 1^{st} column of the given range (B3 to B7). The cell in the 1^{st} row and the 1^{st} 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.

*(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:

*(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**

*(Click Image To See an Enlarged Version)*

**After Running Solver**

*(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

*(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)

*(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.

*(Click Image To See an Enlarged Version)*

**Excel Master Series Blog Directory**

Statistical Topics and Articles In Each Topic

- Histograms in Excel
- Bar Chart in Excel
- Combinations & Permutations in Excel
- Normal Distribution in Excel
- Overview of the Normal Distribution
- Normal Distribution’s PDF (Probability Density Function) in Excel 2010 and Excel 2013
- Normal Distribution’s CDF (Cumulative Distribution Function) in Excel 2010 and Excel 2013
- Solving Normal Distribution Problems in Excel 2010 and Excel 2013
- Overview of the Standard Normal Distribution in Excel 2010 and Excel 2013
- An Important Difference Between the t and Normal Distribution Graphs
- The Empirical Rule and Chebyshev’s Theorem in Excel – Calculating How Much Data Is a Certain Distance From the Mean
- Demonstrating the Central Limit Theorem In Excel 2010 and Excel 2013 In An Easy-To-Understand Way

- t-Distribution in Excel
- Binomial Distribution in Excel
- z-Tests in Excel
- Overview of Hypothesis Tests Using the Normal Distribution in Excel 2010 and Excel 2013
- One-Sample z-Test in 4 Steps in Excel 2010 and Excel 2013
- 2-Sample Unpooled z-Test in 4 Steps in Excel 2010 and Excel 2013
- Overview of the Paired (Two-Dependent-Sample) z-Test in 4 Steps in Excel 2010 and Excel 2013

- t-Tests in Excel
- Overview of t-Tests: Hypothesis Tests that Use the t-Distribution
- 1-Sample t-Tests in Excel
- 1-Sample t-Test in 4 Steps in Excel 2010 and Excel 2013
- Excel Normality Testing For the 1-Sample t-Test in Excel 2010 and Excel 2013
- 1-Sample t-Test – Effect Size in Excel 2010 and Excel 2013
- 1-Sample t-Test Power With G*Power Utility
- Wilcoxon Signed-Rank Test in 8 Steps As a 1-Sample t-Test Alternative in Excel 2010 and Excel 2013
- Sign Test As a 1-Sample t-Test Alternative in Excel 2010 and Excel 2013

- 2-Independent-Sample Pooled t-Tests in Excel
- 2-Independent-Sample Pooled t-Test in 4 Steps in Excel 2010 and Excel 2013
- Excel Variance Tests: Levene’s, Brown-Forsythe, and F Test For 2-Sample Pooled t-Test in Excel 2010 and Excel 2013
- Excel Normality Tests Kolmogorov-Smirnov, Anderson-Darling, and Shapiro Wilk Tests For Two-Sample Pooled t-Test
- Two-Independent-Sample Pooled t-Test - All Excel Calculations
- 2- Sample Pooled t-Test – Effect Size in Excel 2010 and Excel 2013
- 2-Sample Pooled t-Test Power With G*Power Utility
- Mann-Whitney U Test in 12 Steps in Excel as 2-Sample Pooled t-Test Nonparametric Alternative in Excel 2010 and Excel 2013
- 2- Sample Pooled t-Test = Single-Factor ANOVA With 2 Sample Groups

- 2-Independent-Sample Unpooled t-Tests in Excel
- 2-Independent-Sample Unpooled t-Test in 4 Steps in Excel 2010 and Excel 2013
- Variance Tests: Levene’s Test, Brown-Forsythe Test, and F-Test in Excel For 2-Sample Unpooled t-Test
- Excel Normality Tests Kolmogorov-Smirnov, Anderson-Darling, and Shapiro-Wilk For 2-Sample Unpooled t-Test
- 2-Sample Unpooled t-Test Excel Calculations, Formulas, and Tools
- Effect Size for a 2-Independent-Sample Unpooled t-Test in Excel 2010 and Excel 2013
- Test Power of a 2-Independent Sample Unpooled t-Test With G-Power Utility

- Paired (2-Sample Dependent) t-Tests in Excel
- Paired t-Test in 4 Steps in Excel 2010 and Excel 2013
- Excel Normality Testing of Paired t-Test Data
- Paired t-Test Excel Calculations, Formulas, and Tools
- Paired t-Test – Effect Size in Excel 2010, and Excel 2013
- Paired t-Test – Test Power With G-Power Utility
- Wilcoxon Signed-Rank Test in 8 Steps As a Paired t-Test Alternative
- Sign Test in Excel As A Paired t-Test Alternative

- Hypothesis Tests of Proportion in Excel
- Hypothesis Tests of Proportion Overview (Hypothesis Testing On Binomial Data)
- 1-Sample Hypothesis Test of Proportion in 4 Steps in Excel 2010 and Excel 2013
- 2-Sample Pooled Hypothesis Test of Proportion in 4 Steps in Excel 2010 and Excel 2013
- How To Build a Much More Useful Split-Tester in Excel Than Google's Website Optimizer

- Chi-Square Independence Tests in Excel
- Chi-Square Goodness-Of-Fit Tests in Excel
- F Tests in Excel
- Correlation in Excel
- Pearson Correlation in Excel
- Spearman Correlation in Excel
- Confidence Intervals in Excel
- z-Based Confidence Intervals of a Population Mean in 2 Steps in Excel 2010 and Excel 2013
- t-Based Confidence Intervals of a Population Mean in 2 Steps in Excel 2010 and Excel 2013
- Minimum Sample Size to Limit the Size of a Confidence interval of a Population Mean
- Confidence Interval of Population Proportion in 2 Steps in Excel 2010 and Excel 2013
- Min Sample Size of Confidence Interval of Proportion in Excel 2010 and Excel 2013

- Simple Linear Regression in Excel
- Overview of Simple Linear Regression in Excel 2010 and Excel 2013
- Complete Simple Linear Regression Example in 7 Steps in Excel 2010 and Excel 2013
- Residual Evaluation For Simple Regression in 8 Steps in Excel 2010 and Excel 2013
- Residual Normality Tests in Excel – Kolmogorov-Smirnov Test, Anderson-Darling Test, and Shapiro-Wilk Test For Simple Linear Regression
- Evaluation of Simple Regression Output For Excel 2010 and Excel 2013
- All Calculations Performed By the Simple Regression Data Analysis Tool in Excel 2010 and Excel 2013
- Prediction Interval of Simple Regression in Excel 2010 and Excel 2013

- Multiple Linear Regression in Excel
- Basics of Multiple Regression in Excel 2010 and Excel 2013
- Complete Multiple Linear Regression Example in 6 Steps in Excel 2010 and Excel 2013
- Multiple Linear Regression’s Required Residual Assumptions
- Normality Testing of Residuals in Excel 2010 and Excel 2013
- Evaluating the Excel Output of Multiple Regression
- Estimating the Prediction Interval of Multiple Regression in Excel
- Regression - How To Do Conjoint Analysis Using Dummy Variable Regression in Excel

- Logistic Regression in Excel
- Logistic Regression Overview
- Logistic Regression in 6 Steps in Excel 2010 and Excel 2013
- R Square For Logistic Regression Overview
- Excel R Square Tests: Nagelkerke, Cox and Snell, and Log-Linear Ratio in Excel 2010 and Excel 2013
- Likelihood Ratio Is Better Than Wald Statistic To Determine if the Variable Coefficients Are Significant For Excel 2010 and Excel 2013
- Excel Classification Table: Logistic Regression’s Percentage Correct of Predicted Results in Excel 2010 and Excel 2013
- Hosmer- Lemeshow Test in Excel – Logistic Regression Goodness-of-Fit Test in Excel 2010 and Excel 2013

- Single-Factor ANOVA in Excel
- Overview of Single-Factor ANOVA
- Single-Factor ANOVA in 5 Steps in Excel 2010 and Excel 2013
- Shapiro-Wilk Normality Test in Excel For Each Single-Factor ANOVA Sample Group
- Kruskal-Wallis Test Alternative For Single Factor ANOVA in 7 Steps in Excel 2010 and Excel 2013
- Levene’s and Brown-Forsythe Tests in Excel For Single-Factor ANOVA Sample Group Variance Comparison
- Single-Factor ANOVA - All Excel Calculations
- Overview of Post-Hoc Testing For Single-Factor ANOVA
- Tukey-Kramer Post-Hoc Test in Excel For Single-Factor ANOVA
- Games-Howell Post-Hoc Test in Excel For Single-Factor ANOVA
- Overview of Effect Size For Single-Factor ANOVA
- ANOVA Effect Size Calculation Eta Squared in Excel 2010 and Excel 2013
- ANOVA Effect Size Calculation Psi – RMSSE – in Excel 2010 and Excel 2013
- ANOVA Effect Size Calculation Omega Squared in Excel 2010 and Excel 2013
- Power of Single-Factor ANOVA Test Using Free Utility G*Power
- Welch’s ANOVA Test in 8 Steps in Excel Substitute For Single-Factor ANOVA When Sample Variances Are Not Similar
- Brown-Forsythe F-Test in 4 Steps in Excel Substitute For Single-Factor ANOVA When Sample Variances Are Not Similar

- Two-Factor ANOVA With Replication in Excel
- Two-Factor ANOVA With Replication in 5 Steps in Excel 2010 and Excel 2013
- Variance Tests: Levene’s and Brown-Forsythe For 2-Factor ANOVA in Excel 2010 and Excel 2013
- Shapiro-Wilk Normality Test in Excel For 2-Factor ANOVA With Replication
- 2-Factor ANOVA With Replication Effect Size in Excel 2010 and Excel 2013
- Excel Post Hoc Tukey’s HSD Test For 2-Factor ANOVA With Replication
- 2-Factor ANOVA With Replication – Test Power With G-Power Utility
- Scheirer-Ray-Hare Test Alternative For 2-Factor ANOVA With Replication

- Two-Factor ANOVA Without Replication in Excel
- Randomized Block Design ANOVA in Excel
- Repeated-Measures ANOVA in Excel
- Single-Factor Repeated-Measures ANOVA in 4 Steps in Excel 2010 and Excel 2013
- Sphericity Testing in 9 Steps For Repeated Measures ANOVA in Excel 2010 and Excel 2013
- Effect Size For Repeated-Measures ANOVA in Excel 2010 and Excel 2013
- Friedman Test in 3 Steps For Repeated-Measures ANOVA in Excel 2010 and Excel 2013

- ANCOVA in Excel
- Normality Testing in Excel
- Creating a Box Plot in 8 Steps in Excel
- Creating a Normal Probability Plot With Adjustable Confidence Interval Bands in 9 Steps in Excel With Formulas and a Bar Chart
- Chi-Square Goodness-of-Fit Test For Normality in 9 Steps in Excel
- Kolmogorov-Smirnov, Anderson-Darling, and Shapiro-Wilk Normality Tests in Excel

- Nonparametric Testing in Excel
- Mann-Whitney U Test in 12 Steps in Excel
- Wilcoxon Signed-Rank Test in 8 Steps in Excel
- Sign Test in Excel
- Friedman Test in 3 Steps in Excel
- Scheirer-Ray-Hope Test in Excel
- Welch's ANOVA Test in 8 Steps Test in Excel
- Brown-Forsythe F Test in 4 Steps Test in Excel
- Levene's Test and Brown-Forsythe Variance Tests in Excel
- Chi-Square Independence Test in 7 Steps in Excel
- Chi-Square Goodness-of-Fit Tests in Excel
- Chi-Square Population Variance Test in Excel

- Post Hoc Testing in Excel
- Creating Interactive Graphs of Statistical Distributions in Excel
- Interactive Statistical Distribution Graph in Excel 2010 and Excel 2013
- Interactive Graph of the Normal Distribution in Excel 2010 and Excel 2013
- Interactive Graph of the Chi-Square Distribution in Excel 2010 and Excel 2013
- Interactive Graph of the t-Distribution in Excel 2010 and Excel 2013
- Interactive Graph of the t-Distribution’s PDF in Excel 2010 and Excel 2013
- Interactive Graph of the t-Distribution’s CDF in Excel 2010 and Excel 2013
- Interactive Graph of the Binomial Distribution in Excel 2010 and Excel 2013
- Interactive Graph of the Exponential Distribution in Excel 2010 and Excel 2013
- Interactive Graph of the Beta Distribution in Excel 2010 and Excel 2013
- Interactive Graph of the Gamma Distribution in Excel 2010 and Excel 2013
- Interactive Graph of the Poisson Distribution in Excel 2010 and Excel 2013

- Solving Problems With Other Distributions in Excel
- Solving Uniform Distribution Problems in Excel 2010 and Excel 2013
- Solving Multinomial Distribution Problems in Excel 2010 and Excel 2013
- Solving Exponential Distribution Problems in Excel 2010 and Excel 2013
- Solving Beta Distribution Problems in Excel 2010 and Excel 2013
- Solving Gamma Distribution Problems in Excel 2010 and Excel 2013
- Solving Poisson Distribution Problems in Excel 2010 and Excel 2013

- Optimization With Excel Solver
- Maximizing Lead Generation With Excel Solver
- Minimizing Cutting Stock Waste With Excel Solver
- Optimal Investment Selection With Excel Solver
- Minimizing the Total Cost of Shipping From Multiple Points To Multiple Points With Excel Solver
- Knapsack Loading Problem in Excel Solver – Optimizing the Loading of a Limited Compartment
- Optimizing a Bond Portfolio With Excel Solver
- Travelling Salesman Problem in Excel Solver – Finding the Shortest Path To Reach All Customers

- Chi-Square Population Variance Test in Excel
- Analyzing Data With Pivot Tables
- SEO Functions in Excel
- Time Series Analysis in Excel
- VLOOKUP

Hi, Great work. I have also have an video here explaining the TSP and solution in excel. https://www.youtube.com/watch?v=fQLBn6p6dp4

ReplyDeletehope this helps for all.

gud day!

Here is the video tutorial

ReplyDelete