1

在 1000 个地点中，有 250 个地点有资格设立分店。我想从这 250 个地点中选择 5 个地点，以使所选地点的社区的利润总和最大化，并且这些网点相距至少 5 英里。给出了人们从一个地方到另一个地方旅行的意愿（它定义了那个地方的邻域）

我尝试过整数编程，但在定义目标函数时遇到了问题。任何可以解决此问题的聚类/优化技术？

编辑：

鉴于：

  • 1000 个位置和任意两个位置之间的大圆距离
  • 对于所有 1000 个地点，人们从一个地点到另一个地点旅行的意愿
  • 250 个符合条件的地点

客观的：

最大化 5 个集群的利润，其中每个集群包含一个选定位置以及人们愿意前往选定位置的所有位置。

约束：

  • 所选位置总数必须为 5 个，并且必须来自 250 个符合条件的位置
  • 选定的位置必须相距至少 5 英里
  • 每个位置只能属于一个集群
4

2 回答 2

2

a constrained full enumeration shouldl do for this problem size:

  1. enumerate all feasible locations combinations not violating the "at least 5 miles apart" constraint. A simple recursion, easily parallelized.
  2. for each of combinations from #1 calculate the total number of locations "covered" by the layout and pick the max. For each node in these 1000 find which outlet if any people from the node will go and +1 if any outlet is reachable. Easily parallelized, again.
  3. Optional. Out of those equally good prefer the ones with the best "load balancing".

The problem you are working on is: http://en.m.wikipedia.org/wiki/Quadratic_assignment_problem

Classic heuristics of approaching these are branch&bound, genetic, annealing. The full enumeration would be used to validate that heuristic is able to approach the global minimum efficiently on small problem sizes.

于 2013-05-23T19:10:47.760 回答
0

如果我正确理解您的问题，您需要以下内容：

让变量Li表示i是否选择了位置。(i = 1..250)

让Si = {Lj for all j such that distance(Li, Lj) <= 5 miles}

让Ci是一个常数，表示邻域的值Li

约束是：

Sum Si <= 1
Li = 1 or 0
Sum(Li for all i) == 5

目标函数是最大化Sum(Li*Ci for all i)

于 2013-05-23T12:03:40.467 回答