Finding the most efficient paths to cover an area from multiple starting locations

Question

I'm looking to design an algorithm for a problem I have, and was hoping there may be someone that could provide some insight on where to start.

In my picture above, the grid is the area they needs to be explored by the circles. Each cell is a unit of work, so currently I've got lat/lng coordinates for the exact center of each of the grid cells. The goal is to visit every cell in the grid. Circles must start in their home locations, and must end in their home locations.

In my current algorithm (SUPER simple, but it works), I'm simply taking the center coordinates of each of those grid cells, splitting them up into lists (number of lists = number of circles), then adding the home location to the beginning and end of each of those lists. As you can imagine, this leads to some very inefficient routes.

The grid areas can vary wildly, as well as the location of the "Homes", so an algorithm that simply determines the best possible route, by minimizing the total distance travelled for each circle to complete the entire task, is what I'm looking for.

I'm thinking this may be some sort of variant of Dijkstra's algorithm, where the distances between all the different center points as well as the home locations are all calculated before determining the lowest possible solution. Where my understanding kind of falls apart is Dijkstra's algorithm is shortest path from A to B, whereas this algorithm is more of a "shortest path from A to A, given that an individual circle can complete X many units of work, with the end goal of the entire grid area being completed".

With this algorithm, I'm picturing that it would take into account the return trip, since its part of the calculated distance I'm trying to minimize, so it would try to complete units of work that are on the way back home.

Any insight or guidance is greatly appreciated. Thank you.

Answer 1

If I understand your description correctly, there is no polynomial-time algorithm that solves each instance optimally. Intuitively, if you had an efficient algorithm for your problem, we could use it to find a Hamiltonian cycle (i.e., a cycle that visits each vertex exactly once) in a grid graph which is known to be NP-complete [1]. (The paper also contains hardness results for various "grids"; see whether some of the definitions actually capture your concept of a "grid").

In other words, we can reduce the problem of determining whether a grid graph has a Hamiltonian cycle to your problem where we have single circle.

You should not be discouraged too much by such a result though. It is perfectly possible you can do considerably better than your current algorithm, i.e., perhaps maybe even most of your instances are actually quite simple to solve. For instance, you could look at various metaheuristics and consider using (say) a genetic algorithm to find a good solution.

---

[1] Arkin, Esther M., Sándor P. Fekete, Kamrul Islam, Henk Meijer, Joseph SB Mitchell, Yurai Núñez-Rodríguez, Valentin Polishchuk, David Rappaport, and Henry Xiao. "Not being (super) thin or solid is hard: A study of grid Hamiltonicity." Computational Geometry 42, no. 6-7 (2009): 582-605.

Answer 2

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.