5

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?

ooo
  • 1,589
  • 4
  • 12

1 Answers1

7

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).

Sune
  • 6,457
  • 2
  • 17
  • 31
  • 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. – ooo Mar 16 '20 at 07:33
  • 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." – Sune Mar 16 '20 at 08:56