Macro to find the best combination of routes

[tfuhr]

Hi All,

Thank you in advance for taking the time to read this and for any solutions and ideas you can provide me with.

I am looking to establish the best combination of routes to deliver 80 stores from one warehouse. Stores can be delivered in single (Warehouse ==> Store 1 ==> Warehouse), doubles (Warehouse ==> Store 1 ==> Store 2 ==> Warehouse), triple (warehouse ==> Store 1 ==> Store 2 ==> Store 3 ==> warehouse). I have established all the possible scenarios (82160 triple, 3160 doubles, 80 singles) and the cost associated to each of these scenerios (affected by the distance and time). My excel sheet is organised as follows. Column A is Warehouse, Column B is the distance between warehouse and first store that is in column C, Column D is the distance between first store (Column C) and second store which is in column E, Column F is the distance between second and third store (coulmn G) and column h is the distance between the third store and the warehouse (column A). Column I contains the total distance, J the time (total distance devided by 60) and the final column is K, which contains the cost associated to each route. Each store as a unique ID (number 1 to 80).

I would love a macro or a system that would go through all the data and establish what is the best combination of routes to use (with the lowest final cost) knowing that I have 33 trucks to deliver and that some trucks can do two routes if they are both under 3 hours (column J). All 80 store must be delivered.

Once again, thank you in advance for your help, let me know if I wasn't clear, I would be delighted to try and be more explicit,

Kind regards,

Tfuhr

[Richard Buttrey]

Ahh, The old 'Travelling Salemen' question arises again!

Check out the following first and see if the techniques therein fit in with your data.

http://www.economicsnetwork.ac.uk/ir.../rasmussen.pdf

The usual problem with this sort of thing is that during the calculation process you can easily build up a serious number of permutations and cause Excel to slow down considerably. You may need to include some pragmatic restrictive rules to cut the permutations in order to facilitate a sensible calculation time/best result balance.

After checking the above and if you still need ideas/help, upload your workbook with any additional thoughts or parameters that you are prepared to accept.

[tfuhr]

Richard,

Thank you so much for your answer. The pdf is fascinating. However, that it is studying one route and how to organize all the stops in between while I am trying to assess which route to select each associated with a cost to deliver my 80 stores with my 33 trucks.

Please find attached below the xls which I am working with that includes 7000 of the combinations possible as described in my previous post. It is not the full 85400 as it doesn't comply with the constraint of uploading in excelforum.com but it should give you a good idea of what I am working with!

Let me know what you think,

Thanks again,

Tfuhr

[tfuhr]

Hi Richard,

Once again thank you.

First of all let me correct some mistakes I made. First of all I don't have 80,000 combinations possible but almost 500,000 permutations (80*79*78+80*79+80).

I have been able to reduce that number tremendously by eliminating permutations where load is too small or too big for a truck, or where one of the store is not delivered that day.

I have now around 10,000 permutations available per day.

I have looked, in these to days, at the paper you attached with great interest. Although it is very intersting, it doesn't quite fit my problem as I am trying to establish the best combination of 33 travelling salesman and not the route of only one.

Ideally, I would like a tool that scan all the possibilities and pulls out the cheapest one that delivers all 80 stores only once . However, if this is not possible or maybe too much data for excel, perhaps it would be possible to just extract all the combinations possible that deliver all 80 stores only once and I would be able to do the cost calculation myself quite easily.

Thanks again for your help,

Any idea is welcome,

Best,

Tfuhr

[Richard Buttrey]

Hi,

Yes I've been pondering this myself over the last few days looking for some balance between pragmatism and the serious number of potential combinations which would otherwise make a pure 'analyse every permutation' too time consuming for Excel.

Leave it with me.