algorithm - 什么方法适合根据接送地点对客户进行聚类

Question

有些人想要从某个上车地点前往某个下车地点。所有上车地点都在城市 A，所有下车地点都在城市 B。其中 A != B。如何对人员进行聚类，以使汽车到上车和下车的总距离最小化。由于大多数汽车可容纳 4 人，因此希望充分利用每辆汽车的容量。每个集群都将分配给可以选择拒绝行程的汽车司机，在这种情况下，它会被传递给下一个司机。

Answer 1

查看此问题的答案:K-means algorithm variation with equal cluster size用于聚类成大小相等的簇的算法(在您的情况下为 4)。

为了处理“不同城市”的约束，将每个客户定义为由他们在城市 A 的上车点和城市 B 的下车点组成的点元组，并将 2 个客户之间的距离定义为距离之和他们的上车地点和他们的下车地点之间的距离。元组列表的平均值是由上车位置的平均值和下车位置的平均值组成的元组。定义这两个函数应该足以实现 K-means。

如果在一个城市行驶给定距离比另一个城市平均花费更长的时间，您可能希望对两个城市的距离加权不同，因为那里的交通更糟糕，或者您将在高峰时间或其他任何时间在一个城市。