# Grocery Store Problem

I have an issue with my Excel function for a grocery store problem and I am not sure where I messed up the constraints. I have the value of the solution it should be (cost = 8,283).

I need to make a stop in aisles 16, 18, 24, 8, 10, 14, 23, 17, 30, 1, 25, 2, 19, 22, 21, 20, and 29 to pick things up. There are 30 aisles.

Here is my Excel spreadsheet: grocery store problem excel.

Here is the network.

• Can you start wherever you want? Can you end wherever you want? Dec 9, 2023 at 4:08
• Hey I was planning on start at A1 but ending doesn't matter Dec 9, 2023 at 4:15

You can solve the problem as follows.

1. Find all-pairs shortest path distances between the $$17$$ "must-visit" nodes in the original directed network.

2. Introduce a dummy node $$0$$, with $$0$$-cost arcs to node $$1$$ and from all other must-visit nodes.

3. Solve an asymmetric traveling salesman problem in a (complete, except for the dummy node) directed network on the must-visit nodes and the dummy node, where the arc costs are the shortest-path distances obtained in step 1.

The resulting optimal tour has the following costs, which sum to $$8283$$, as you claimed: $$\begin{matrix} i&j&\text{cost}\\ \hline 0&1&0\\ 1&2&1170\\ 2&8&1020\\ 8&10&300\\ 10&14&1153\\ 14&16&273\\ 16&18&320\\ 18&17&113\\ 17&21&614\\ 21&20&272\\ 20&19&163\\ 19&22&864\\ 22&30&271\\ 30&23&312\\ 23&24&400\\ 24&25&101\\ 25&29&937\\ 29&0&0\\ \end{matrix}$$

By the way, if you are allowed to start anywhere and end anywhere, the optimal cost is instead $$7174$$, achieved by a path that starts at $$29$$ and ends at $$1$$ but is not quite the reverse of the path above.

Related questions:

• Thank you so much, so I just add the dummy variable as if it was just another edge? Can you explain 3. a little bit more, sorry I'm inexperienced with OR Dec 9, 2023 at 4:58
• You will add a dummy node $0$, an edge $(0,1)$ to force starting at $1$, and edges $(i,0)$ for $i\in\{16,18,24,8,10,14,23,17,30,25,2,19,22,21,20,29\}$. Dec 9, 2023 at 5:04
• If you prefer, omit the dummy node and just replace the shortest-path distances to node $1$ with cost $0$. Then for step 3 you have a complete directed network on the $17$ must-visit nodes. Dec 9, 2023 at 5:28
• I added them and set them all to zero, how do I include these in the constraints/objective function, I tried adding them as normal but some of them are looping like A1A2 A2A1, Dec 9, 2023 at 6:33
• To avoid such loops in step 3, you need “subtour elimination” constraints. For a simple formulation, search for Miller-Tucker-Zemlin or MTZ. Dec 9, 2023 at 14:31