5
$\begingroup$

Here is my question where I am propagating distance through the graph, I was wondering if it is possible to do when the graph has cycles, i.e., traveling the same node multiple time then is it possible to assign current distance traveled at each instance of that node?

$\endgroup$
6
$\begingroup$

You can make copies of each node (as many copies as times you can visit the node). Then use your constraints as before on this larger graph. This is e.g., done in some papers for the green vehicle problem (see for instance A Green Vehicle Routing Problem by S. Erdoğan and E. Miller-Hooks).

$\endgroup$
2
  • $\begingroup$ Since I can't pre-compute the number of times I need to visit a node, how to estimate the number of copies of a node. $\endgroup$ – ooo Mar 16 '20 at 7:33
  • $\begingroup$ In the linked paper they write "The number of dummy vertices associated with each AFS (alternative fuel station), $n_f$, is set to the number of times the associated $v_f$ can be visited. $n_f$ should be set as small as possible so as to reduce the network size, but large enough to not restrict multiple beneficial visits." $\endgroup$ – Sune Mar 16 '20 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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