-1
$\begingroup$

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.

https://i.sstatic.net/YeCOd.png

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Can you start wherever you want? Can you end wherever you want? $\endgroup$
    – RobPratt
    Commented Dec 9, 2023 at 4:08
  • $\begingroup$ Hey I was planning on start at A1 but ending doesn't matter $\endgroup$
    – zoomonkey101
    Commented Dec 9, 2023 at 4:15

1 Answer 1

Reset to default
1
$\begingroup$

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:

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – zoomonkey101
    Commented Dec 9, 2023 at 4:58
  • $\begingroup$ 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\}$. $\endgroup$
    – RobPratt
    Commented Dec 9, 2023 at 5:04
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Commented Dec 9, 2023 at 5:28
  • $\begingroup$ 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, $\endgroup$
    – zoomonkey101
    Commented Dec 9, 2023 at 6:33
  • $\begingroup$ To avoid such loops in step 3, you need “subtour elimination” constraints. For a simple formulation, search for Miller-Tucker-Zemlin or MTZ. $\endgroup$
    – RobPratt
    Commented Dec 9, 2023 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.