Home |
Search |
Today's Posts |
#1
Posted to microsoft.public.excel.programming
|
|||
|
|||
algorithm
Hi,
Im trying to automate a task and to optimise some road routes. I have a matrix, the matrix is a ready reckoner to help calculate milage between a source and its destination; the top row of the matrix has the destination and the left column has all the source sites. Each destination has an annual input capacity and each source has an annual production quantity aswell, these are kept in another two tables. I need to have excel work out the most efficient routes taking into consideration the source production and the destination site capacities. Ive been trying to find a suitable algorithm and have looked at Floyd-Warshall, Dijkstra's & Johnson's but none seem right. Please can anyone give direction on this or possibly help with the code. Thanks for your help. |
#2
Posted to microsoft.public.excel.programming
|
|||
|
|||
algorithm
Sounds like the Transportation problem, which is soluble using either the
transportation algorithm or (less efficiently) Linear Programming. Try using Solver. regards Charles __________________________________________________ The Excel Calculation Site http://www.decisionmodels.com "excel_lover" wrote in message ... Hi, Im trying to automate a task and to optimise some road routes. I have a matrix, the matrix is a ready reckoner to help calculate milage between a source and its destination; the top row of the matrix has the destination and the left column has all the source sites. Each destination has an annual input capacity and each source has an annual production quantity aswell, these are kept in another two tables. I need to have excel work out the most efficient routes taking into consideration the source production and the destination site capacities. Ive been trying to find a suitable algorithm and have looked at Floyd-Warshall, Dijkstra's & Johnson's but none seem right. Please can anyone give direction on this or possibly help with the code. Thanks for your help. |
#3
Posted to microsoft.public.excel.programming
|
|||
|
|||
algorithm
The alogorithm you choose wil depend on how much time you want to use to get
the results. In your cas time is not a factor. therefore I would try every combination a keep track of the previous shorest distance results. You also want to make sure you don't get into any endless loops. Usally a recursive method is the best algorithm in getting these results. Start at the source location the follow these steps. Create an 3 dimensional array of all the routes. The size of the array would be Routes(Number of cities, maximum number of routes from any one city,2) The 2 at the end is for the distance and the new city name. If you had 3 cities , NY, Chicago, LA 1 = NY 2 = Chicago 3 =LA Start/ Destination Route 1,1,1 2(Chicago) 1,1,2 2000 miles 1,2,1 2(LA) 1,2,2 3000 miles 2,1,1 1(NY) 2,1,2 2000 miles 2,2,1 3(LA) 2,2,2 1500 miles 3,1,1 1(NY) 3,1,2 3000 miles 3,2,1 2(Chicago) 3,2,2 1500 miles making 2nd array of the current route. Recursive algorithm 1) Select each of the routes from currect location one at a time 2) Indicate on the array the route chosen 3) call recursive algorithm again passing the latest copy of the array of routes and the new desintation location. Continue to all the routes are used or you hage exceeded the previous shortest distance. "excel_lover" wrote: Hi, Im trying to automate a task and to optimise some road routes. I have a matrix, the matrix is a ready reckoner to help calculate milage between a source and its destination; the top row of the matrix has the destination and the left column has all the source sites. Each destination has an annual input capacity and each source has an annual production quantity aswell, these are kept in another two tables. I need to have excel work out the most efficient routes taking into consideration the source production and the destination site capacities. Ive been trying to find a suitable algorithm and have looked at Floyd-Warshall, Dijkstra's & Johnson's but none seem right. Please can anyone give direction on this or possibly help with the code. Thanks for your help. |
#4
Posted to microsoft.public.excel.programming
|
|||
|
|||
algorithm
Thanks Joel, Im pleased its going to be possible.
Ive got most of the data not quite sure where to take it next Ive posted my spreadsheet here please can you take a look http://www.quickfilepost.com/downloa...3271618d77a157 "Joel" wrote: The alogorithm you choose wil depend on how much time you want to use to get the results. In your cas time is not a factor. therefore I would try every combination a keep track of the previous shorest distance results. You also want to make sure you don't get into any endless loops. Usally a recursive method is the best algorithm in getting these results. Start at the source location the follow these steps. Create an 3 dimensional array of all the routes. The size of the array would be Routes(Number of cities, maximum number of routes from any one city,2) The 2 at the end is for the distance and the new city name. If you had 3 cities , NY, Chicago, LA 1 = NY 2 = Chicago 3 =LA Start/ Destination Route 1,1,1 2(Chicago) 1,1,2 2000 miles 1,2,1 2(LA) 1,2,2 3000 miles 2,1,1 1(NY) 2,1,2 2000 miles 2,2,1 3(LA) 2,2,2 1500 miles 3,1,1 1(NY) 3,1,2 3000 miles 3,2,1 2(Chicago) 3,2,2 1500 miles making 2nd array of the current route. Recursive algorithm 1) Select each of the routes from currect location one at a time 2) Indicate on the array the route chosen 3) call recursive algorithm again passing the latest copy of the array of routes and the new desintation location. Continue to all the routes are used or you hage exceeded the previous shortest distance. "excel_lover" wrote: Hi, Im trying to automate a task and to optimise some road routes. I have a matrix, the matrix is a ready reckoner to help calculate milage between a source and its destination; the top row of the matrix has the destination and the left column has all the source sites. Each destination has an annual input capacity and each source has an annual production quantity aswell, these are kept in another two tables. I need to have excel work out the most efficient routes taking into consideration the source production and the destination site capacities. Ive been trying to find a suitable algorithm and have looked at Floyd-Warshall, Dijkstra's & Johnson's but none seem right. Please can anyone give direction on this or possibly help with the code. Thanks for your help. |
#5
Posted to microsoft.public.excel.programming
|
|||
|
|||
algorithm
This is the table of data.
exp# is the start point location max at destination is shown in row 1 The number data in the matrix relates to Kilometers between points Hope that explains it better Thanks again for your help max 15789.6 13104.45 volume Destination Site 1 Destination Site 2 14.5 exp1 8.42 0.00 14.5 exp2 12.66 5.67 1368.25 exp3 9.60 5.73 72.5 exp4 3.92 6.10 58 exp5 11.09 7.22 333.5 exp6 0.00 8.31 50.75 exp7 3.51 8.52 790.25 exp8 11.51 8.77 997.35 exp9 13.04 9.17 14.5 exp10 3.05 10.18 8926 exp11 5.06 10.27 3153.75 exp12 17.26 10.27 837.35 exp13 16.77 10.87 913.5 exp14 13.53 12.64 1718.2 exp15 11.11 12.86 358.6 exp16 16.16 12.98 2211.25 exp17 8.48 15.75 3037.75 exp18 15.16 17.24 696 exp19 10.66 17.93 87 exp20 13.81 21.08 145 exp21 15.95 21.50 424.1 exp22 32.60 28.73 522 exp23 34.70 30.83 25 exp24 22.97 31.58 159.9 exp25 37.48 33.61 348 exp26 38.87 35.00 |
#6
Posted to microsoft.public.excel.programming
|
|||
|
|||
algorithm
The transportation algorithm is called
Kuhn's Hungarian Method regards Charles __________________________________________________ The Excel Calculation Site http://www.decisionmodels.com |
Reply |
Thread Tools | Search this Thread |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Forum | |||
Help with an algorithm | Excel Programming | |||
Help with an algorithm | Excel Programming | |||
Algorithm Challenge | Excel Programming | |||
help with algorithm | Excel Programming | |||
Need help with algorithm | Excel Programming |