Question

Truck Delivery Route

The distance between 11 cities are listed below:

		Boston	Chicago	Dallas	Denver	LA	Miami	NY	Phoenix	Pittsburgh	SF	Seattle
1	Boston	0	983	1815	1991	3036	1539	213	2664	792	2385	2612
2	Chicago	983	0	1205	1050	2112	1390	840	1729	457	2212	2052
3	Dallas	1815	1205	0	801	1425	1332	1604	1027	1237	1765	2404
4	Denver	1991	1050	801	0	1174	1332	1780	836	1411	1765	1373
5	LA	3036	2112	1425	1174	0	2757	2825	398	2456	403	1909
6	Miami	1539	1390	1332	1332	2757	0	1258	2359	1250	3097	3389
7	NY	213	840	1604	1780	2825	1258	0	2442	386	3036	2900
8	Phoenix	2664	1729	1027	836	398	2359	2442	0	2073	800	1482
9	Pittsburgh	792	457	1237	1411	2456	1250	386	2073	0	2653	2517
10	SF	2385	2212	1765	1765	403	3097	3036	800	2653	0	817
11	Seattle	2612	2052	2404	1373	1909	3389	2900	1482	2517	817	0

Suppose a delivery truck company locates in Boston. The truck needs to start from Boston, visit each city once and only once, and finally return Boston. How should you design the traveling route for the truck so that the total traveled distance is shortest?

Notice that due to some specific requirement from the customers, the truck must go to New York immediately after visiting Denver.

Use the excel template to build your model and find the best route for the truck.

Answer 1

We have a Distance matrix. We created 2 more matrices, one is the allocation matrix, the other is the Total Distance matrix . In case of Allocation Matrix, we have used 1 for allocation & 0 for non allocation. Total Distance Matrix was obtained by multiplying Distance matrix with allocation matrix. The image gives a better detailing..

BG BH BI BL BM BN BO BP BQ BE B5 B1 BV BW BY CA CE CC Bl 24 Pittshurgh SE Distance Mlami Phoont Spattle Denver Pttsburgh SF Denver Dalas Mam Boston Chicago Dalas Boston Chicago LA Phoentx Spattle ce Boston Boston 1015 3030 50 213 cc 792 230. 2612 Chicago 840 Chicago 0 983 120 105 21 13 172 45 21 2053 0 1050 1429 2 nequre FO- 147 1780 TE 142 2825 245 10r LA spal LA Mami NY 21: 112 75 AL 125t 1251 Miami 53 13: 275 35 330 35. 2442 21 2825 1258 NY 84 160 78 386 03 86 1027 24- 20r8 - petshu al n7 8T 176 04 238 176 3036 2653 81 940 20 Seattle Seattle 2612 20s 37 1000 190 2512 813 7 Sum Phoento Sum Pittsburgh S 14092 Boston hicago Dalas Soatth erver Chcago Dalas Denver 44 Mami 46 Phoenix 47 Pttsburah 4B SF -

In case of Allocation Matrix, we have created 2 more columns, one represents row sum and the column sum. Also, we have created a sum of all the diagonal allocations & this is represented in BQ50. Now this sum has to be Zero as there wont be any allocations from Boston to Boston or Dallas to Dallas.

The Total Distance matrix contains the total Distances & their sum is represented in CC38.

Now,

Objective Function : To minimize the Sum of Total Distance, which is in CC38.

Variables : The Allocation matrix has to be changed to achieve this.

subject to constraints:

1. Allocation matrix is binary, i.e either 1 or 0.

2. The column sum which is represented from BF50 to BP50 should be 1.. as the allocation can happen only once to a city.

3. Now, we have to go NY immediately after Denver. Therefore, Allocation is done from Denver to NY in the cell BL42.

4. The row sum which is represented from BQ39 to BQ49 should be 1.. as the allocation can happen only once to a city.

5. The sum of the diagonal allocations , which is represented in BQ50 should be 0, as we cant allocate Denver from Denver.

The below picture gives a better detailing..

X Solver Parameters Set Objective: $CC$38 Min To: C Value Of: Max By Changing Variable Cells: $BF$39:$BP$49 Subject to the Constraints: $BF$39:$BP$49 = binary $BF$50:$BP$50 1 $BL$42 1 Add Change $BQ$39:$BQ$49 = 1 $BQ$50 0 Delete Reset All Load/Save Make Unconstrained Variables Non-Negative Select a Solving GRG Nonlinear Options Method: Solving Method Select the GRG Nonlinear engine for Solver Problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems that are non-smooth. Close Help Solve