老实说,我不确定将其发布在哪里/发布什么内容,但我将非常感谢任何人提供的任何建议。
我正在寻求创建一种算法,该算法将为出租车(长途私有(private)租车)公司计算最佳时间表,该公司有多个司机和多个预订。
在任何一天,最多可能有 5 到 10 个工作,每个工作需要不同的时间和不同的里程数。
我可以通过 Google Distance API 获取所有位置之间的坐标和距离。
我想计算最佳时间表,从而最大限度地减少司机的里程/时间,以便尽可能有效地完成所有工作。工作时间和地点是固定的,但是司机可以是最多 10 人中的任何一个。每个司机不一定每天都要完成一份工作。有些司机可能会在一天内完成多项工作,只要它们不重叠即可。
例如:
司机 A 从 A 点到 B 点。
当天晚些时候B点还有另一个工作,所以司机A自然应该被分配到这个工作,因为司机A可以在B点等到下一个工作开始时间,而不是浪费燃料让另一个司机去空车到 B 点。
我尽量做到简明扼要,对篇幅表示歉意。我不希望得到完整的答案,但如果有人尝试过类似的答案,我将不胜感激!
最佳答案
我将尝试通过一些调度伪代码来帮助您。让我们试试吧!
首先,你需要一个调度结构,有N个队列,每个队列有M个slots。您必须有每天的时间表、每个可能的司机的队列和可变数量的插槽。
在我看来,我会将一天分成 15 分钟。考虑到这种结构,调度算法将是一个交互过程,每个新的交互都会尝试分配一个新的路由。
第一步是对所有未决路线进行排序,为 route 的每个终点找到最近的起点。有了这个庞大的有序路线流,下一步就是将这些路线按顺序移动到第一个可用的司机,直到他当天的所有空位都被填满。您继续为下一个司机做同样的拆分,直到没有更多的交付被安排。
在没有所有“时隙”概念的情况下处理此类问题是可能的,但我认为这是避免制定不可能的超紧计划的安全措施。这个提议的算法也不处理往返起点(卡车装载的地方)所需的时间。我认为您可以通过第二次遍历所有时间表并添加往返加载点的所需路线来获得公平但未优化的解决方案。通过这样做,您需要将一些司机的最后一条路线移动到另一位司机,以便适合“回家”路线。
祝你工作顺利。希望它有所帮助!
关于php - 算法查询 - 多个驱动程序,多个位置,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36242622/