既然你说你有所有节点之间的距离，一种可能性是线性规划。制定该计划将是相当直接的。您的目标是最小化，其中是从节点 i 发送到节点 j 的卡车数量，而是距离。您将只有两个约束。第一个约束条件是表明从所有来源到节点 j 的卡车数量大于 j 处的需求。您可以为每个节点的供应制定类似的约束。$\sum{c_{ij}t_{ij}}$$t_{ij}$$c_{ij}$$\sum_{\forall i}t_{ij}\ge D_{j}$

线性规划方法也可以保证为您提供全局最优，但上述公式存在一个明显的问题。您的决策变量是每对节点的整数。这会将您的 29,000 个节点变成近 900,000,000 个决策变量，这并不是一个微不足道的计算问题。当然你可以做一些事情，比如删除距离超过某个阈值的对，这可以大大减少问题的大小，但会使实现更加复杂。

另外，对于线性编程，我不知道 ruby​​ 中有哪些接口。我个人学习了使用 glpk（免费求解器）和 pyomo（python 框架）。维基百科页面有一个很好的不同免费库列表。