生成教师拼车时间表的算法方法

Question

希望 StackOverflow 是提出此类问题的最佳场所，我想向群体智能询问解决以下问题的最佳算法方法的建议。尽管看起来很具体，但我认为解决此类或类似问题的方法是普遍有效的。

问题

它是关于为在一天中不同时间开始和结束工作的员工创建一个拼车时间表，即有个人时间表的老师。 乍一看这可能很简单，但当您考虑以下问题时，问题很快就会变得异常复杂：

• 凡是开车回程的人，也必须在路上开车，否则回程的车就会失踪。
• 平均而言，为了公平起见，所有参与者的驾驶次数应大致相同。
• 总体来说，应该尽量少做驱动器，以节省成本。
• 同时向同一方向行驶的汽车应均匀装载。
• 人们在不同的集合点登机；一些收集点位于其他收集点的人们的路线上（可以开车接载），但反之则不然。
• 如有需要，人们也可以在其他（附近）收集点上车，但当天返回时必须在完全相同的收集点下车，例如以便能够取回停在那里的自行车。
• 每个人的车内有不同数量的空闲座位，并且只能携带相应数量的其他人。
• ...

方法

我能想到四种方法来解决这个问题：

1. 天真的方法。我尝试通过某种方式将个人行程和汽车映射到数据结构中，然后迭代地用满足某些属性的人来填充它们，从而手动和强制地实现上述所有约束。然后，我计算每个人驾驶的行程次数，然后尝试手动替换那些经常被用作司机的人，却发现这个问题最晚对我来说变得太复杂了。
2. 暴力方法。我或多或少随机生成了一些人的星座，并生成了数十万个星座，以便选择最不坏的星座。这既费时又费电，不是最优的，而且肯定不满足任何算法要求。
3. 进化算法。这与暴力方法的工作方式相同，但更有针对性，因为生成的时间表中最成功的部分被组合起来以创建更好的时间表。这里的问题是，这个问题太复杂了，我已经无法想象我应该如何用种群、基因组和基因来表示它。有没有多层进化算法这样的东西？
4. 人工智能。当然，一切问题的解决方案。这里的问题是我没有足够的例子来训练人工智能。我手头只有两三个手动创建的时间表。我几乎无法使用它们来训练神经网络从给定的数据集生成新的时间表。

我是一名专业的计算机科学家，但我在这里真的很茫然：是否有一种“经典”的方法来解决这样的问题，你会“自然地”使用 - 或者是否有一个或另一个的具体方法我对如何进行的想法？谢谢你分享我的头痛！

Answer 1

这是“将代理分配给具有指定约束的时隙中的任务”的特殊情况

该方法取决于您的目的。目的有两类：

1. 计算机科学家希望开发一种最佳算法，保证为所有情况提供最佳答案，无论多么不切实际。

2. 软件工程师想要开发一种算法，能够在大多数正常情况下提供不错的答案，而不会太复杂。

你是哪一个？

如果你是#1，那么你就来错地方了。

如果您是#2，那么我们可以讨论您的特定限制，我可以根据您的情况调整我的代码。