使用进化算法为教师拼车生成时间表[关闭]

Question

编辑：我必须指定这个问题。最初我想讨论不同的算法方法。但现在我想具体问一下如何设计进化算法来解决这个问题。

问题

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

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

方法

不同的解决方案乍一看听起来很有希望，但都有中度到严重的缺点。例如，我可以立即想到四种方法来解决这个问题：

1. 天真的方法。通过以某种方式将个人行程和汽车映射到数据结构中，然后迭代地用满足某些属性的人来填充它们，手动和强制地实现上述所有约束。
2. 暴力方法。我或多或少地生成了随机的星座，并生成了数十万个星座，以便选择最不坏的星座。
3. 人工智能。当然，一切问题的解决方案。这里的问题是我没有足够的例子来训练人工智能。
4. 进化算法。 这是我的选择。

据我所知，进化算法的工作方式与蛮力方法相同，但更有针对性，因为将生成的时间表中最成功的部分组合起来以创建更好的时间表。

这里的问题是，问题是如此复杂（找到一个最佳的司机，一个最佳的车辆工作人员，创建一周中的最佳一天，一个最佳的一周并确保所有人都以相似的频率驾驶，...）我无法想象我应该如何仅用人口，基因组和基因来表示它。有没有像多层进化算法这样的东西？希望得到您的帮助。

问题

如何借助进化算法解决这个问题？更准确地说：如何将人、车辆、一周中的日子映射到基因、基因组和种群？

Answer 1

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

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

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

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

你是哪一个？

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

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

你提到的收集点实际上造成了这两个问题。 首先，您需要将代理分配到收集点，这将是一个图论问题。 一旦实现了这一点，您就可以查看分配问题，其中收集点是通过约束来建模的，即某些人只能被分配到任务的子集（即为代理分配到的接送点提供服务的游乐设施）。 )

一些定义

• Shift：一对时间，例如上午 8 点和下午 4 点，或上午 9 点和下午 5 点
• 代理：一对，一班，一个收集点。
• 任务：接送所有同班同集合点的坐席

现在的问题是在分配给任务的代理之间轮换驾驶分配。

我认为您没有提供足够的信息来就分配代理到收集点提供任何建议。 作为第一步，也许您可以手动执行此操作？