I'm attempting to create an algorithm to address an issue that I can't categorize, therefore I'll reveal the subject:
You have a map divided into parts with a specific area and a specific number of inhabitants.
The challenge is to identify sets of connected sections whose area does not exceed a particular amount while maximizing the number of chosen occupants.
Another strategy:
Furthermore, based on the combinatorics of the specific issue, it is possible in some instances to use genetic algorithms in conjunction with tabu search, but only in situations where finding an optimum answer is impossible.
To be more specific, the goal is to obtain a set of connected sections whose sum of areas does not exceed the total area. The population sum of the chosen sections is the parameter to maximize. The goal is to discover the best option.
What I have tried:
For the time being, I can think of two approaches:
Treat the problem as an all-pairs shortest routes problem in an undirected network with positive natural values, and discard solutions that do not match the constraint of the largest chosen area. You might use the
Floyd-Warshall algorithm, Dijkstra for all pairings, or Thorup method (which can be done in time V * E, where V and E are the graph's vertices and edges).
Consider it a profit-generating open vehicle routing problem in which each vehicle can start and stop anywhere it wishes. (open vehicle routing problem with profits or OVRPP).
Submit an article or tip