6
$\begingroup$

Visualization of problem

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ How large are your grids (i.e., number of cells) and how many circles do you typically have? $\endgroup$
    – Juho
    Jun 10, 2018 at 17:26
  • $\begingroup$ Not large enough that performance is a major concern. Numbers of circles will always be fairly small <10. The grids could be a bit larger, but we're not talking more than 10,000 cells, so in terms of computer processing, fairly low numbers. $\endgroup$
    – adam3039
    Jun 10, 2018 at 17:32
  • 1
    $\begingroup$ If I understand your description correctly, the problem is NP-complete even for a single circle. A bit more formally, the "grid" is a grid graph (i.e., an induced subgraph of a grid) and now imagine there is a single circle with an arbitrary starting point. Because each vertex of the grid must be visited, the problem is equivalent to finding a Hamiltonian cycle in the grid. But this problem is NP-complete even in grid graphs of maximum degree 3. $\endgroup$
    – Juho
    Jun 10, 2018 at 17:37

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the insight. When constructing the graph that I will use for any of these algorithms, I'd imagine that my two 'homes' in my example would have edges to every node in the grid, correct? Then each grid node would also have edges to every other grid node. My thinking is that they could start anywhere on the grid, so they'd need edges to each node to determine distance. Looks like I've got my work cut out for me. $\endgroup$
    – adam3039
    Jun 10, 2018 at 20:06
  • $\begingroup$ @adam3039, no, that's not what I have in mind. Create one vertex per grid cell. Draw an edge between two vertices if those two grid cells are adjacent. $\endgroup$
    – D.W. ♦
    Jun 10, 2018 at 20:23
  • $\begingroup$ For sure, I understand that for the grid cells, but for this particular problem I'd imagine the location of the "homes" would be important, because you'd need to know the distance between the circles home and the first grid cell one of the circles starts on. My thinking is that each home would need an edge to each grid cell vertex because the circle could end on any node and would need to know the distance back home. $\endgroup$
    – adam3039
    Jun 10, 2018 at 20:55

Your Answer

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

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