3 added 23 characters in body edited Jun 10 '18 at 20:22 D.W.♦ 106k1414 gold badges135135 silver badges315315 bronze badges You are looking for a vertex cycle cover for the grid graph, with some added constraints: we are given $$k$$ vertices $$v_1,\dots,v_k$$ (the "home locations"), and the $$i$$th cycle must include the vertex $$v_i$$; and we want to minimize the length of the longest cycle (or maybe the total lengths of all the cycles, I'm not clear). Unfortunately, as Juho explains, your specific problem is NP-hard, so you shouldn't expect any algorithm that is efficient on the worst case, scales to large graphs, and always gives the optimal solution. So, you're left with looking for heuristics or approximation algorithms, or accepting that your algorithm might take exponential time in the worst case. You might consider a local search algorithm, e.g., simulated annealing or something similar. One could imagine that a particular state assigns each vertex in the graph to the "circle" that will visit it. To make a small change, you might pick one vertex $$v$$ that are assigned to assigned to some circle (say circle A) and is adjacent to a vertex assigned to another circle (say circle B), and change $$v$$ so it is assigned to circle B; then recalculate the Hamiltonian cycles for A and B, and use that to score how good this modified solution is. (How to calculate Hamiltonian cycles? You might in turn use local search for that, or any other standard heuristic for finding Hamiltonian cycles.) Then apply standard local search algorithms to this neighbor relation; e.g., hill climbing or simulated annealing. That's just an idea -- I have no idea whether it will work well or not. Your best bet is probably to try several different approaches like this and see how well they work in practice. You are looking for a vertex cycle cover for the grid graph, with some added constraints: we are given $$k$$ vertices $$v_1,\dots,v_k$$, and the $$i$$th cycle must include the vertex $$v_i$$; and we want to minimize the length of the longest cycle (or maybe the total lengths of all the cycles, I'm not clear). Unfortunately, as Juho explains, your specific problem is NP-hard, so you shouldn't expect any algorithm that is efficient on the worst case, scales to large graphs, and always gives the optimal solution. So, you're left with looking for heuristics or approximation algorithms, or accepting that your algorithm might take exponential time in the worst case. You might consider a local search algorithm, e.g., simulated annealing or something similar. One could imagine that a particular state assigns each vertex in the graph to the "circle" that will visit it. To make a small change, you might pick one vertex $$v$$ that are assigned to assigned to some circle (say circle A) and is adjacent to a vertex assigned to another circle (say circle B), and change $$v$$ so it is assigned to circle B; then recalculate the Hamiltonian cycles for A and B, and use that to score how good this modified solution is. (How to calculate Hamiltonian cycles? You might in turn use local search for that, or any other standard heuristic for finding Hamiltonian cycles.) Then apply standard local search algorithms to this neighbor relation; e.g., hill climbing or simulated annealing. That's just an idea -- I have no idea whether it will work well or not. Your best bet is probably to try several different approaches like this and see how well they work in practice. You are looking for a vertex cycle cover for the grid graph, with some added constraints: we are given $$k$$ vertices $$v_1,\dots,v_k$$ (the "home locations"), and the $$i$$th cycle must include the vertex $$v_i$$; and we want to minimize the length of the longest cycle (or maybe the total lengths of all the cycles, I'm not clear). Unfortunately, as Juho explains, your specific problem is NP-hard, so you shouldn't expect any algorithm that is efficient on the worst case, scales to large graphs, and always gives the optimal solution. So, you're left with looking for heuristics or approximation algorithms, or accepting that your algorithm might take exponential time in the worst case. You might consider a local search algorithm, e.g., simulated annealing or something similar. One could imagine that a particular state assigns each vertex in the graph to the "circle" that will visit it. To make a small change, you might pick one vertex $$v$$ that are assigned to assigned to some circle (say circle A) and is adjacent to a vertex assigned to another circle (say circle B), and change $$v$$ so it is assigned to circle B; then recalculate the Hamiltonian cycles for A and B, and use that to score how good this modified solution is. (How to calculate Hamiltonian cycles? You might in turn use local search for that, or any other standard heuristic for finding Hamiltonian cycles.) Then apply standard local search algorithms to this neighbor relation; e.g., hill climbing or simulated annealing. That's just an idea -- I have no idea whether it will work well or not. Your best bet is probably to try several different approaches like this and see how well they work in practice. 2 added 1068 characters in body edited Jun 10 '18 at 19:24 D.W.♦ 106k1414 gold badges135135 silver badges315315 bronze badges You are looking for a vertex cycle cover for the grid graph, with some added constraints: we are given $$k$$ vertices $$v_1,\dots,v_k$$, and the $$i$$th cycle must include the vertex $$v_i$$; and we want to minimize the length of the longest cycle (or maybe the total lengths of all the cycles, I'm not clear). Unfortunately, as Juho explainsas Juho explains, your specific problem is NP-hard, so you shouldn't expect any algorithm that is efficient on the worst case, scales to large graphs, and always gives the optimal solution. So, you're left with looking for heuristics or approximation algorithms, or accepting that your algorithm might take exponential time in the worst case. You might consider a local search algorithm, e.g., simulated annealing or something similar. One could imagine that a particular state assigns each vertex in the graph to the "circle" that will visit it. To make a small change, you might pick one vertex $$v$$ that are assigned to assigned to some circle (say circle A) and is adjacent to a vertex assigned to another circle (say circle B), and change $$v$$ so it is assigned to circle B; then recalculate the Hamiltonian cycles for A and B, and use that to score how good this modified solution is. (How to calculate Hamiltonian cycles? You might in turn use local search for that, or any other standard heuristic for finding Hamiltonian cycles.) Then apply standard local search algorithms to this neighbor relation; e.g., hill climbing or simulated annealing. That's just an idea -- I have no idea whether it will work well or not. Your best bet is probably to try several different approaches like this and see how well they work in practice. You are looking for a vertex cycle cover for the grid graph, with some added constraints: we are given $$k$$ vertices $$v_1,\dots,v_k$$, and the $$i$$th cycle must include the vertex $$v_i$$; and we want to minimize the length of the longest cycle (or maybe the total lengths of all the cycles, I'm not clear). Unfortunately, as Juho explains, your specific problem is NP-hard, so you shouldn't expect any algorithm that is efficient on the worst case, scales to large graphs, and always gives the optimal solution. So, you're left with looking for heuristics or approximation algorithms, or accepting that your algorithm might take exponential time in the worst case. You are looking for a vertex cycle cover for the grid graph, with some added constraints: we are given $$k$$ vertices $$v_1,\dots,v_k$$, and the $$i$$th cycle must include the vertex $$v_i$$; and we want to minimize the length of the longest cycle (or maybe the total lengths of all the cycles, I'm not clear). Unfortunately, as Juho explains, your specific problem is NP-hard, so you shouldn't expect any algorithm that is efficient on the worst case, scales to large graphs, and always gives the optimal solution. So, you're left with looking for heuristics or approximation algorithms, or accepting that your algorithm might take exponential time in the worst case. You might consider a local search algorithm, e.g., simulated annealing or something similar. One could imagine that a particular state assigns each vertex in the graph to the "circle" that will visit it. To make a small change, you might pick one vertex $$v$$ that are assigned to assigned to some circle (say circle A) and is adjacent to a vertex assigned to another circle (say circle B), and change $$v$$ so it is assigned to circle B; then recalculate the Hamiltonian cycles for A and B, and use that to score how good this modified solution is. (How to calculate Hamiltonian cycles? You might in turn use local search for that, or any other standard heuristic for finding Hamiltonian cycles.) Then apply standard local search algorithms to this neighbor relation; e.g., hill climbing or simulated annealing. That's just an idea -- I have no idea whether it will work well or not. Your best bet is probably to try several different approaches like this and see how well they work in practice. 1 answered Jun 10 '18 at 18:00 D.W.♦ 106k1414 gold badges135135 silver badges315315 bronze badges You are looking for a vertex cycle cover for the grid graph, with some added constraints: we are given $$k$$ vertices $$v_1,\dots,v_k$$, and the $$i$$th cycle must include the vertex $$v_i$$; and we want to minimize the length of the longest cycle (or maybe the total lengths of all the cycles, I'm not clear). Unfortunately, as Juho explains, your specific problem is NP-hard, so you shouldn't expect any algorithm that is efficient on the worst case, scales to large graphs, and always gives the optimal solution. So, you're left with looking for heuristics or approximation algorithms, or accepting that your algorithm might take exponential time in the worst case.