算法查询-多个驱动程序，多个位置

Question

老实说，我不知道该把这个贴在哪里，但是我会非常感谢任何人，你能提供的任何建议我都很感激。

我希望创建一个算法，它将计算出出租车(长途私人租赁)公司最优的时间表，有多个司机和多个预订。

在任何一天，都可能有5到10份工作，每一份都需要不同的时间和不同的里程。

我可以获得坐标，以及所有地点之间的距离通过谷歌距离API。

我想要计算的最佳时间表，其中司机里程/时间是最小的，以便尽可能有效地完成所有工作。作业时间和地点是固定的，但是司机可以是任何一个池多达10个。每个司机不一定要完成每天的工作。一些驱动程序可以在一天内完成多个任务，只要它们不重叠。

例如：

司机A从A点到B点。

一天晚些时候，B点还有另一份工作，所以司机A自然应该被分配到这项工作，因为司机A可以在B点等待下一项工作的开始时间，而不是浪费燃料让另一名司机带着一辆空车去B点。

我试着简明扼要，为自己的长篇道歉。我不期待一个完整的答案，但如果有人试图类似，一些提示将不胜感激！

Answer 1

我会尽力帮你安排一些伪代码。我们试试吧！

首先，您需要一个具有N个队列和每个队列M个时隙的调度结构。您必须有每天的日程安排、每个可能的驱动程序的队列和可变数目的插槽。

在我看来，我会把这一天分成15分钟。考虑到这种结构，调度算法将是一个交互过程，每个新的交互将尝试分配一个新的路由。

第一步是对所有挂起的路由进行排序，为路由中的每个结束点查找最近的起点。有了这个大流量的有序路线，下一步是移动这些路线，以便第一个可用的司机，直到他的所有时段，为一天填补。您继续对下一个司机进行同样的拆分，直到没有更多的交付计划。

在没有“插槽”概念的情况下处理这类问题是可能的，但我认为这是一项安全的措施，以避免安排一个不可能太紧的时间表。所提出的算法也不处理往返于起点(卡车装载的地方)所需的时间。我认为，您可以有一个公平但非优化的解决方案，通过第二遍所有的时间表，并添加所需的路线往返于负载点。这样做，您将需要将一些司机的最后路线转移到另一个司机，以便“回家”的路线可以适合。

祝你工作顺利。希望它能帮上忙！