algorithm

[excel_lover]

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.

 

[Charles Williams]

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

 

[Joel]

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]

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/download.do?get=ff19ff878dcd6739a63271618d77a157

 

[excel_lover]

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

 

[Charles Williams]

The transportation algorithm is called
Kuhn's Hungarian Method

regards
Charles
__________________________________________________
The Excel Calculation Site
http://www.decisionmodels.com