平衡负载和确定总线路线的算法/逻辑

Question

我想创建一个软件来为残障 child 交通规划公交路线(及其最佳载客量)。

这些总线具有以下规范:

• m 个座位(最多 7 个 - 因为有司机和助理)
• o 轮椅“座位”(最多 4 个)
• 固定的最大负载量(在奥地利:9 或 20 人；例如福特全顺 9 人；例如梅赛德斯奔驰 sprinter 20 人)

路线规范:

• child 到学院的路程必须短于 2 小时(不包括公共(public)汽车)
• 为了优化:混合机构可能是最优的

例子

最佳路线 1 是:

• 6, 1, 7, group (2, 3, 4, 5), insitute A (exit for 1, 2, 3, 4, 5, 6), 8, 9, insitute B (exit for 7, 8 , 9) 或
• 1、7、6，小组 (2、3、4、5)，学院 A(1、2、3、4、5、6 退出)，8、9，学院 B(7、8 退出, 9) 或
• 7, 1, 6, 小组 (2, 3, 4, 5), 学院 A (退出 1, 2, 3, 4, 5, 6), 8, 9, 学院 B (退出 7, 8 , 9) 或
• ...

取决于具体的道路(也就是三角形 1-6-3 和 7-1-6 的道路距离)

这是一个简单的例子。当涉及到运输轮椅时，情况就更复杂了。

编辑:
注意:有超过 2 个学院，因为有超过 9 个 child 。这只是为了举例。在现实世界中，会有 600 个 child 和 20 个机构......

我需要什么数据？
我的猜测是:坐标、点之间的距离(不是航线距离，而是道路距离)、“座位使用”类型(座位或轮椅)、某种道路规范(可能由于距离而过时)

任何人都可以提出一些想法、算法、逻辑、反馈(免费!因为残疾 child 交通不是企业业务)我可以用来获取数据(例如坐标、距离……)的软件.

哦，我必须说。我不是学过软件工程师的，所以阅读有气味的文学作品在某种程度上很难，但我愿意亲自动手!

Answer 1

嗯，这实际上是我谋生的工作。基本上，我们使用带有列生成的 MiP 和路径模型来解决这个问题。看到问题很小，我认为您可以使用更简单的边缘流模型来获得合理的结果。这将节省您进行列生成的工作，这是一项相当大的工作。在考虑自己生成路线之前，我建议先计算给定出发路线上的流量——事实上，我会简单地使用路线计算器和双重成本作为指南“手动”完成。

具体来说，您需要创建一个图形，其中每个取货点和送货点都是一个节点，每条公交路线都是一组相连的注释。酌情连接，这真的是画起来比写起来容易:) 然后，制作一个 LP 系统来模拟流量，将流量限制在公交车的容量上，要么要求所有乘客都送达，要么为不送达而付出沉重的代价所以。

一旦就绪，为每条路线创建 bool 变量并将其乘以容量:这将使您能够打开和关闭公交路线。

详情请咨询，以上只是大概的介绍。

编辑:

好吧，看完回复，我想我不得不说，要按照我建议的方式解决这个问题，你至少需要有一些线性规划和图论的知识。是的，这是一个非常难的问题……如此之难以至于我认为除了使用当前计算机技术的非常小的系统外，它是无法解决的。看到这其实是一个很小的。我认为这是可能的，非常欢迎您联系我们公司寻求帮助(contact@ange.dk)。然而，优化方面的专业协助并不便宜。

但是，一切并没有丢失!有更简单的方法，虽然结果不会那么好。当您无法建模时，请模拟!编写一个模拟，给定公交路线、乘客等，显示乘客如何沿着公交路线移动。做一个分数，你使用的每辆公共(public)汽车都要花一些钱，每公里要花一些钱，而每个没有被运送的乘客都要花很多钱。然后查看结果，更改路线并努力找到您可以提出的最佳(最便宜)解决方案。这可能不是一个糟糕的解决方案。

同样，对于不精通 LP+MiP+图论的人来说，创建一个将从头开始为上述问题生成解决方案的程序不是一个合适的企业。但也许更少能做到这一点？

我将在下周左右休假。