Shortest Path Optimization

**excelcombinations** · 09-15-2017, 07:23 AM

Hi,

I have a routing sequence for a set of machines on an assembly line. Each route has to go through the entire line (i.e. if you only run the first and second machine, you still account for the distance from the second to the end of the line).

I have six different machines (720 possible combinations of machines) with fixed distances between each location on the line. The distance between the first and second machine is 100', the distance between second and third is 75', third and fourth is 75', fourth and fifth is 25', and fifth and sixth is 25'.

I have 4 different products that have to run down the line, and each of them have a fixed routing.

My problem is, how do I set up a vba code or solver that will allow me to run through all possible combinations of the line setup and determine the optimal setup for this line? Any machine can be placed at any location, as long as it optimizes the result! What are your thoughts?

The four product routes are :
A - B - C - D - F
A - C - B - D – E - F
A - F - E - D - C - B - A - F
A - C - E - B - D – F

**shg** · 09-15-2017, 08:18 AM

Welcome to the board.

Homework?

Presumably there is a desired location for finished goods to end up along that path (maybe closest to the shipping department). But since they all start with A and end with F, it seems likely that those are the bookend machines, and you only need to optimize the four middle ones (24 permutations).

Also, you would need to consider the quantities of each route, no? It it were {1000, 1, 1, 1}, you'd just optimize for the first route.

**MrShorty** · 09-15-2017, 08:58 AM

I put "excel shortest path" into my favorite internet search engine and got several hits. This was the first one: http://www.excel-easy.com/examples/s...h-problem.html I would suggest you start by studying this and other examples of the shortest path problems. Then work on adapting those examples to your specific scenario here. If you have trouble with a specific part of the algorithm, let us know and we'll see what we can do to help.