python-3.x - 通过基于距离对位置进行聚类，以计算成本低廉的方式替代 VRP

Question

我有一个位置列表和一个车辆容量列表。我想对位置进行聚类，使聚类中的点数等于车辆的容量。此外，在形成集群时，我不希望集群中位置之间的距离超过阈值。

例如，我拥有的位置是：

points = array([[33.    , 41.    ],
       [33.9693, 41.3923],
       [33.6074, 41.277 ],
       [34.4823, 41.919 ],
       [34.3702, 41.1424],
       [34.3931, 41.078 ],
       [34.2377, 41.0576],
       [34.2395, 41.0211],
       [34.4443, 41.3499],
       [34.3812, 40.9793]])

车辆容量如下：

capacities = [3, 4, 2]

集群中两个连续位置之间的最大距离应该小于 say 3 kms。

即，如果位置 1->2->3->4 在集群中，则此距离限制适用于订单 1,2 和 2,3 和 3,4。

这个问题有什么解决办法吗？我不想使用vrpyor ortools。

标签： python-3.xgraphcluster-analysis