文摘
随着人民生活水平的提高,人们的旅游需求,出租车越来越多,但出租车服务体系还不完善;出租车司机通常依赖于他们的操作经验或巡航随机找到乘客。没有macroguidance,出租车系统的作用不能被充分的利用。许多学者研究了出租车司机的行为找到更好的操作策略,但是他们的研究依赖于局部优化方法提高司机的利润,这将使供应和需求之间的不平衡。为了解决这个问题,我们提出一个可替换主体基于强化学习——(泥灰岩)出租车predispatching模型通过分析13000辆出租车的运行数据。不同于其他方法的出租车调度基于订单的实时位置,首先我们的模型预测在不同地区对出租车的需求在未来的时期,然后提前分派出租车来满足未来的需求;因此,出租车的数量和可用在不同地区平衡。此外,为了减少计算复杂度,我们提出几个方法来减少的状态空间和动作空间的强化学习。最后,我们比较我们的方法与另一个出租车调度方法,结果表明,该方法有显著提高车辆利用率和乘客需求满足率。
1。介绍
智能城市,一个新兴的技术,其目的是为了新一代的信息和通信技术应用于各行各业,能够缓解“大城市病”(1),协调城市发展,提高城市的运行效率和市民的生活质量2]。智能交通(3,4),作为一个智能城市不可或缺的一部分,目的是提高交通系统的运行效率,充分利用交通资源,确保交通安全(5]。它在公民生活起着至关重要的作用,整个城市的操作。如今,交通拥堵、事故频发、能源浪费,空气污染,和其他问题普遍存在于城市和他们可以解决智能交通(6,7]。
无线通信技术的快速发展和物联网(物联网),收集移动对象的轨迹记录变得简单和快速,使智能交通可能(5,8]。各种设备内置GPS在我们的生活中无处不在,比如智能手机(9,10],私家车[11,12),和公共交通13]。位置信息可以更容易获得,每天大量的轨迹数据收集。轨迹数据具有空间属性和时间属性;它变成了时空数据挖掘技术的主要研究对象。轨迹数据的应用程序不仅可以为用户提供基于位置的服务,而且还帮助城市规划和智能交通。收集和分析这些大规模真实的数字痕迹为我们提供了前所未有的机会,把握城市动力学和更好地理解社会和经济模式14- - - - - -16]。
然而,相应的经营战略并没有开发的出租车数量的增加,仍然有许多缺点,比如在高峰时间很难找到出租车,出租车不均匀分布,和司机的拒绝服务(17]。出租车司机的策略寻找乘客大多是经验和大幅改变彼此间18,19),导致服务效率低,收入低。许多研究已经致力于解决这些问题(8,18,20.,21),但基本上从驾驶员的角度看,这些局部优化方法在某些地区可能会导致饥荒。所以它既不能为出租车调度提供指导从全球的角度来看也为乘客提供更好的乘坐体验。也有一些研究致力于将车辆分配给每个订单基于实时位置。然而,基于实时调度订单状态有一些缺陷;例如,如果可用很少有出租车乘客,我们不得不安排一辆出租车根据最短的距离优先级原则服务乘客,但实际距离很远。这不是一个理想的安排的司机和乘客。汽车旅行更远的距离,乘客需要等待更长的时间使整个出租车系统效率低下。
为此,我们提出一个车辆prescheduling模型从整个城市的角度,所以出租车资源可以得到充分利用,并且可以提高服务质量和乘客的工作经验。首先通过历史轨迹数据的分析,我们确定了人口流动模式的特点和出租车运营规则在城市。基于这两点,我们计算车辆的数量可以在当前时间提供服务并预测在未来出租车的数量要求。根据预测的结果,我们可以知道的数量供给和需求在每一个城市的区域。最后,可替换主体强化学习可用于出租车调度,这将最终平衡全球供给和需求,使更多的乘客需要出租车在更短的时间。
我们的主要贡献是总结如下:(1)我们研究在不同地区人群运动模式通过分析历史出租车轨迹数据,从而为车辆调度提供一些辅助信息。(2)我们提出一个出租车predispatching模型基于可替换主体强化学习方法,它可以平衡出租车的数量在每个地区和需求。(3)我们提出一个分治状态空间方法降低音量过大的泥灰,这提高了计算效率。(4)我们评估不同的时间序列预测算法的性能预测未来皮卡请求通过实验,通过实验证明该模型的有效性进行比较。
本文的其余部分组织如下。节2,我们给出租车经营战略研究的简要回顾和网上订单匹配方法。节3,我们提供的定义问题;然后我们介绍文章的处理管道。本文使用的数据,处理数据的方法,介绍了城市分工部分4。节5介绍基于多重代理调度方法强化学习。实验结果部分所示6。最后,我们总结论文部分7。
2。相关工作
挖掘出租车轨迹数据一直是研究热点在智能城市22];许多学者研究过这个问题。通过对相关研究的分析,我们发现文学在出租车的研究主要集中在两个方面。一是分析了出租车司机操作策略和研究策略可以给司机带来更高的收入。另从整体的角度是出租车市场,专注于为出租车调度,并提供指导。在本节中,我们主要介绍其他学者的研究成果从这两个观点。
不同的城市有不同的人群运动模式的特征。但在同一个城市,不同的驱动程序也不同,因为他们的收入可能采用不同的操作策略。许多学者研究过哪一种经营战略出租车司机应该采取更高的利润。荣et al。18]提取有效的运营策略通过大规模历史出租车轨迹数据,然后分析这些策略通过多个指标,得到一些有价值的见解和使用这些策略来增加司机的收入。李等人。14)设计一个仿真模型来测试性能的三种不同的搜索策略从两个角度包括乘客等待时间和空出租车旅行。陈等人。23)使用三个指标包括出租车服务的水平、出租车运营,和出租车发展分析出租车的操作,以提高出租车行业的管理,促进出租车行业的可持续发展。
一些学者建议出租车司机通过分析人群运动模式。基于这些模式,它们为出租车司机提供建议和推荐一些位置。在这些位置,有更大的可能性得到乘客,这可以减少巡航时间,从而增加他们的收入。香港et al。24]提出time-location-relationship (TLR)服务推荐模型相结合来提高司机的利润根据乘客的特点在不同的功能区域。TLR模型分析了乘客上下车每个时期之间的关系,采用高斯过程回归(GPR)预测的乘客和建议司机最近的地区出租车的需求是最多的在同一时间。Phithakkitnukoon et al。25]提出一个预测模型空出租车的数量在一个特定区域基于时间,星期,天气条件。有了这些知识,我们可以更快地为请求分配车辆。枭龙et al。26]调查人类移动模式通过分析大规模出租车跟踪和开发一个改进的ARIMA方法预测传感器数量(PUQ)的城市热点然后出租车司机推荐最优的热点,出租车司机将花费的时间最少拿起下一个乘客。
元等。27)提供一个推荐系统对出租车司机和人们期待坐出租车,使用知识移动模式的乘客和出租车司机接/的当属行为从GPS轨迹。这个推荐系统为出租车司机提供一些地点和路线这些位置,为人们提供一些地方(步行距离之内),他们可以很容易地找到空的出租车。Golpayegani和克拉克28考虑司机和乘客的各自的偏好。他们提出一个可替换主体协同匹配和客运出租车调度模型。乘客和司机被建模为自治代理有多个拥偏好。乘客和司机的注意偏好摘要给我们伟大的灵感。系统应考虑不同用户的偏好,而不是平等地对待他们。Dimitriou et al。16]研究纽约的出租车轨迹数据。通过分析出租车的旅行时间和距离,上下车的情况在机场等重点领域,他们推荐的最佳位置出租车乘客。
上述研究都从车手角度;我们的目标是让司机更多的利润。这些研究是局部优化,不利于出租车服务质量的角度来看整个城市。一些其他的研究集中在如何匹配可用车辆请求更合理。他们使用不同的算法来实现这一目标;例如,Kuemmel et al。29日)利用一个稳定的婚姻分配算法和应用调度出租车乘客。稳定的婚姻匹配算法是最初开发的男性和女性在多项式时间内根据他们的偏好。郑和杰30.)也使用稳定的婚姻的方法。他们研究在线离线出租车调度问题。对于nonsharing出租车调度,它使用稳定的婚姻方法和使用三种规则来查找所有可能的稳定匹配。?萧和et al。31日)提出一个可替换主体架构与出租车和请求试图提高乘客满意度全球更多。这座城市被划分为不同的区域;每个地区维护自己的出租车队列和请求队列。该系统将匹配请求和车辆定期在每个区域。魏et al。17]研究的影响服务拒绝在出租车市场供需平衡。
也有一些研究人员使用强化学习来实现自己的目标。Gueriau和Dusparic32]提出一种基于强化学习车辆转移分散方法以及骑请求分配在共享系统按你的要求。每辆车自主学习行为,包括调整和选择哪些请求服务,基于其局部电流,观察历史需求。再平衡战略提出了非常有建设性的,为我们提供一个好的参考。李等人。33,34)都使用泥灰来解决匹配问题的车辆和订单,但前者遵循对等的分布式特性的拥有权问题,采用平均场近似简化当地社区之间的交互通过平均行动。后者使用强化学习的扩展版本:分层强化学习(HRL)。它作为一个大规模并行模型ride-hailing排名问题,结合顺序与车队管理调度,和分层的方式进行决策的过程。
现有研究调度车辆实时根据订单的位置。由于不同地区的供给和需求的失衡,一些出租车需要长途旅行服务乘客,这将延长乘客的等待时间,减少操作效率。如果我们能提前知道每个地区的潜在需求,我们可以采取一些措施来解决这个问题。幸运的是,我们现在有各种各样的非常成熟的预测模型,包括机器学习模型、深度学习模型,和各种时间序列模型,可实现高精度。因此,prescheduling模型提出了第一个预测未来皮卡请求到时间序列预测模型,然后分派出租车实现每个地区的供需平衡。这样做之后,只需要一个小规模的调度。仿真结果表明,该方法可以有效地避免出租车会众所引起的局部优化方法和提高出租车的运营效率。
3所示。概述
在本节中,我们将介绍问题定义和处理管道有一个更好的理解什么是本文所述。
3.1。问题定义
无论大小的城市,出租车的数量,可用出租车和出租车的数量要求对不同区域的城市是不平衡的,尤其是在上下班高峰时间。因此,我们提出一个出租车predispatching模型来平衡出租车在不同地区的供给和需求,最终提高出租车的利用率,满足更多的需求,减少乘客等待时间。
本文作为研究区域地图上的一个二维平面上,然后将它划分为大小相同的网格。根据实时GPS数据上传的出租车,我们可以得到每个出租车,出租车的数量的位置在每个网格(供应数量),构成供应矩阵(t代表了时间)。预测的需求之后,每个网格的需求矩阵可以通过结合所有网格的值根据其空间位置。减去两个矩阵,我们可以得到目标矩阵,通过它我们可以知道整个地区的供需形势。这个问题然后转向如何安排出租车,这样更多的目标矩阵中的值大于或等于零。本文可替换主体强化学习是用来让机器自动探索最好的调整计划,以实现这一目标。
3.2。处理管道
我们的主要处理管道方法见图1。它主要由四部分组成:数据预处理、地图分区,需求预测,出租车调度。数据预处理是用来消除不必要的GPS数据和错误信息,方便以后的应用程序。地图相同大小的分区将城市划分为网格,然后分析人群旅游模式在不同的网格为出租车调度后提供援助。需求预测部分使用多个时间序列预测方法来预测未来的出租车数量要求在每个网格,所以每个地区的未来需求情况可以提前掌握。之后,出租车调度可以根据当前出租车分布和未来需求情况。
4所示。数据处理
上海是中国最繁荣的城市之一。对出租车的需求非常大。出租车在城市交通中扮演着重要的角色。具有重要意义优化出租车服务的效率。本文使用13700辆出租车的GPS定位数据从4月1日在上海,2015年4月30日,2015年,研究在上海出租车的需求。出租车的位置是每10秒采样,生成数据时乘客或关闭。在30天内,大约30亿块生成的数据。数据中的字段及其含义如表所示1。
4.1。数据进行预处理
由于设备故障、传输干扰,或存储错误,数据可能不正确。例如,当出租车司机下班后,他可能会把计价器上虽然没有乘客在出租车上了。出租车状态和出租车的位置是非常重要的后续实验,所以不合理数据应当予以纠正或删除为了得到更准确的结果。澄清真正的空缺并占领了轨迹(分别与没有乘客,轨迹),执行如下的数据处理步骤。步骤1。数据按时间排序。根据时间排序的数据每一个出租车,出租车应该定期的状态之间的转换和占领的。对应数据,出租车状态字段应该改变在0和1之间。例如,0011年…1100年或1100年…0011年,从1到0,就意味着接收旅客,从0到1意味着乘客下车。结合经度和纬度,我们可以知道乘客。步骤2。消除错误状态转换。车辆的状态可能经常变换,例如00100110001或111011011101。显然,这些情况是不合理的。它将导致错误的记录得到了很多次,这将对结果产生影响。处理此类错误的方法是限制最短时间与机上乘客和空的汽车。如果低于阈值时,它将被认为是一个错误的转换。通过数据的统计分析,出租车与乘客的最低时间上和无载设置为5分钟,一分钟,分别。步骤3。纠正错误的位置点。由于GPS设备的错误,弱卫星信号,或传输错误,一些点轨迹的位置可能是异常;也就是说,两个点之间的距离超过了最大距离汽车可以在一段时间内旅行。为了处理这种情况,我们采取的中点的位置两个记录(错误记录之前和之后)的实际位置点。因为分析的对象是网格,不需要得到一个非常精确的位置。
4.2。映射描述和流程
我们主要研究领域在经度121.4100°-121.5045°,纬度30.1940°之间在上海-31.2750°。这一领域包括商业中心、火车站、居民区,许多旅游景点。它是高度代表整个城市出租车的情况的分析。一般来说,有两种方法来划分一个区域。第一个是把该地区的主要道路,另一个是将区域划分为大小相同的网格(35]。除以主要道路的方法是不容易的在选择正确的道路由于各种环形路高架桥和不均匀网格的大小;因此它将带来额外的未来预测和调度困难。所以我们选择第二种方法。研究区域分为从1到81网格和标签;每个网格的大小 。图2显示了分区的结果。
4.3。关系的,下车
每个网格的纬度和经度范围可以确定啮合后完成。数据上传的出租车包含纬度和经度。所以我们可以匹配每一块数据到相应的网格。然后,根据时间信息的上传记录,我们可以得到可用出租车的数量在每个网格和出租车的需求。
排序后的数据按照时间,每个出租车应该经常改变的状态之间的入住率和懒惰在连续时间序列。例如,或 。一个过渡的意味着国家的出租车从空的状态已经改变到占领状态;也就是说,需求满足。我们可以计算转换的数量在一段时间内的需求在每一个网格。同样,如果国家象征变化从0到1,这意味着乘客下车后,上述处理后,我们可以得到,下车的数量在每个网格在所有时间。
如图3之间的定量关系,我们显示乘客上下车工作日和周末期间在三个网格。居民区的人早上出去工作,晚上回家,所以得到的人数在一辆出租车在早上下车的人数多一辆出租车,晚上的情况恰恰相反。如数据所示3(一个)和3 (d)工作日的早上高峰时间是8点,晚上高峰时间是20点,周末早晚高峰是上午10点和22点。,分别。与工作日相比,早晚高峰的周末之后,因为人们在周末出去后,参加各种娱乐活动在晚上也让人回家后。
(一)
(b)
(c)
(d)
(e)
(f)
商业领域,休闲和娱乐,保持相对较高的登机和离船时间相比,住宅区。如图3 (b),很多人在中午之前到达和人相处的数量远远高于那些下车后21点钟,因为人们开始回家。周末显示工作日一样的趋势,但高峰期交通繁忙得多。这是符合我们的期望;肯定会有更多的人去娱乐时不需要去上班。
与居住区相比,工作区域产生相反的旅游模式。人们在早上上班,晚上回家。下车峰是8 - 9点20点钟,登上高峰。但在晚上高峰时间的交通不如早高峰时间,因为没有急于下班回家。有些人可能使用不同的交通方式回家,比如地铁或公交。比较周末和工作日,模式是一样的,但流量和峰值则要弱的多,初期的特定时间后,表明有些人仍然在周末上班,但少的人数,时间是晚。
通过分析不同的功能区域,我们可以了解人群旅游的模式在不同的功能区域。这些信息可以帮助调度过程和使它更合理,比如派遣更多的出租车在晚上高峰时段工作区域。
5。调度模型
通过上面的研究历史数据,我们知道出租车在不同地区的供给和需求情况,可以使用不同的预测方法来预测在未来出租车的数量需求。有了这些知识,我们利用强化学习方法安排出租车,这样所有地区可以实现供需平衡。
5.1。WoLF-PHC算法
有一些常用的泥灰岩算法,如极大极小q学习,纳什q学习,敌我q学习(FFQ),和狼政策爬山(WoLF-PHC)。前三个方法需要维护Q-function所有代理的学习过程;所需的空间三个方法是非常大的。为了解决这个问题,我们希望每个代理维护核反应能量函数只有通过了解自己的行为。WoLF-PHC这样的算法,每个代理只有保存自己的行动来完成学习任务。所以我们在本文中使用WoLF-PHC。
WoLF-PHC结合了“赢或学的很快”的规则和政策爬山算法(PHC)。狼是指慢慢仔细调整参数,当代理比期望值和加速的步伐调整参数当代理比期望值(36]。过去是一个代理在稳定的环境中学习算法。该算法的核心是强化学习的想法,从而增加的概率选择可以得到最大累积期望的行动(37]。
该算法定义了两种策略:目前的策略 和平均策略 。当前的策略是一个概率分布函数的初始值 。这个概率分布函数将被更新以下列方式当代理选择行动。Q-function,如果它是最好的行动,也就是说, ,它的概率将增加,而其他操作将减少的可能性。WoLF-PHC不断更新策略和比较它与当前平均策略:如果当前策略的平均回报价值大于平均的策略,也就是说, ,代理将被视为“赢。“在这个时候,战略将采用平均率慢慢更新策略。否则,当前代理将被视为“输了,”和更大的速度将用于更快的适应学习。
5.2。调度过程
预测后的需求在未来时期,每个网格的需求矩阵D可以通过结合每个小格子的预测结果根据其空间位置。代表行网格的需求我和列j。供应矩阵年代可以通过计算获得出租车的数量在每个网格当前时间。一个新的矩阵X(如图4)可以减去从供应需求矩阵的矩阵,正值表示可用的数量的出租车和负值代表不满足要求。我们的目标是最小化负数与最短的驾驶距离矩阵。
为了实现这一目标,我们使用WoLF-PHC算法,它把每个出租车作为一个代理,使用网格数来表示其空间位置。每个出租车构成了当前状态的空间位置。出租车采取行动后,它的位置会改变,国家将会相应地改变。每个出租车可以带五每一步行动,包括上,下,左,右,和保持,但它只能停留在一个网格需要出租车。如果一个网格不需要它,它保持它在这个网格是没有意义的。当可用的出租车的数量大于总需求,我们应该尽量满足所有的要求。在这种情况下,算法的终止状态意味着所有目标矩阵中的值是积极的;时即终止状态达到所有要求都被满足了。否则,终止状态意味着只有负数和零矩阵,这意味着可以使用任何额外的出租车。如果算法达到平衡状态后,所有代理都采取了行动,所有代理会得到一个奖励100点; otherwise they will get −1 points. All agents take actions according to their Q table until they reach the termination state. For the same matrix, there may be many scheduling methods to achieve balance, but after the algorithm has updated the strategy it will eventually find an optimal way to achieve balance.
所有代理的位置是在给定的时间环境的状态。有81个网格,所以状态空间的大小 , 网格的数量,是代理的数量。每个代理可以采取五个行动,所以是5的行动空间。每个代理的Q表的大小 ; 可能达到数千人,所以状态空间和Q表将会非常大,计算复杂度会很高。在实践中,它将需要很长时间来计算每个出租车的位置。为了降低计算复杂度,我们需要使状态空间小。我们可以通过减少的大小来实现这一点和 。(我)减少的大小 :我们可以将81网格划分为3×3大网格,每个人也是由3×3小网格。通过这种方式,状态空间减少到原来的1/9。大电网后调整和平衡,小网格将安排。(2)减少的大小 :我们可以把矩阵分成相同大小的两个矩阵的出租车数量除以每个网格同样,和同样的效果可以通过平衡各子矩阵。代理的数量矩阵可以减少一半,以及由此产生的子矩阵可以并行计算,进一步提高了计算速度。
|
||||||||||||||||||||||||
|
||||||||||||||||||||||||||||
不同的调度算法有不同的目标,如司机的最大化利润,让司机找下一个乘客更快,或者减少乘客的等待时间。本文的目标是提高出租车的利用率和满足尽可能多的要求可以使用一定数量的出租车。同时,调度算法的效率也认为,这意味着用更少的出租车,以满足更多的需求。因此,调度模型的目标函数定义如下:
在方程(1),代表了需求满足率,计算除以总皮卡请求满足需求见方程(2)。一个好的调度算法应该满足尽可能多的要求,所以需求满意度越高,调度的结果就会越好。表示出租车的利用率。计算方法,如方程所示(2)=出租车的数量,有效利用(这意味着出租车派遣和满足某种需求)之间的较小值除以总皮卡请求和出租车的总数。可能有两种情况;一个显示,出租车的数量小于需求,在这种情况下,所有的出租车都可以有效地利用;另一个是出租车的数量超过了需求,在这种情况下出租车,可以有效地利用等于总需求。有时,完成后安排,有些要求不满意,但仍有一些可用的出租车,这表明调度算法是不好的,所以我们希望的价值比较大。代表出租车调度的效率。如方程所示(2),计算方法等于要求满足发运除以出租车的数量,这意味着有多少需求满足每一个出租车。更大的价值是,调度算法的效率就越高。我们的目标是调整该模型目标函数的价值最大化。
6。实验
在本节中,我们首先比较三个时间序列预测模型在不同的性能指标,然后使用表现最好的模型提供数据支持后续调度。然后我们比较调度方法提出了用另一种方法在许多方面来测试我们的模型的有效性。
6.1。预测实验
为了有一个精确的预测结果在未来不同时期,我们将一天分成米时间片段,每一个都是t小时的长度。为不同类型的城市或同一城市的不同地区,交通条件的变化速度是不同的,所以对于繁荣的地区我们应该使用一个更小的t应对快速变化的需求的情况。偏远地区或小城市,交通条件相对稳定;我们可以设置t更长时间,这可以减少计算的频率,确保预测的准确性。
在本节中,三个算法ARIMA LSTM, FBprophet评估预测的要求。使用两个指标,RMSE和梅,比较三种方法的性能。(1)均方根误差(均方根误差):它是用来测量预测值和真实值之间的偏差。它侧重于项目的预测和实际之间的差异值,值越小,算法就会越好。它可以定义如下: 预测值和实际值用和 ,分别定义为测量的数量n。(2)平均的平均绝对误差(MAE):它代表之间的平均绝对误差预测和观察到的值。它关注的和所有的预测和实际值之间的差异。它可以定义如下:
如图5两下,FBprophet最佳性能指标测试条件下的工作日还是周末。这种方法不需要调整参数。具有良好的通用性和预测数据速度非常快。是不敏感的数据的大小;即使预测在周末用更少的数据精度依然很高。LSTM预计工作日FBprophet相似的结果。它执行比FBprophet周末,但比ARIMA更好。它的缺点是,它取决于网络结构设计和质量的各种参数的设置,和网络的训练过程会消耗很长时间了。ARIMA、传统模型、不执行在这个预测问题,可能是因为有很多日常交通状况、影响因素和模型并不能很好的预测这些波动。此外,这种模式需要调整不同的自回归系数p和移动平均问对不同的数据集,这是时间成本高,所以不适合多个时间序列的预测。总之,我们决定使用FBprophet模型预测,因为更快和更高的准确预测可以使调度结果更好。
(一)
(b)
(c)
(d)
6.2。调度实验
通过使用FBprophet模型,我们可以让出租车在未来在每个网格的要求。然后我们可以使用模型提出了安排所有可用的范围的出租车。为了验证我们的模型的性能,在不同时期的工作日和周末我们进行了实验,并与time-location-relationship (TLR)结合出租车服务推荐模型提出了(24]。TLR模型的主要思想是,当出租车司机需要找到乘客,八个网格的模型比较要求出租车然后建议电网最大的出租车要求出租车作为目的地。该调度方法可以很容易地导致出租车聚集在一个区域。在本文中,一个小的改进是在实现的过程中。出租车这个模型将推荐一个网格,由一定的选择可能从两个网格最出租车的需求。实验结果如下。
在图6,在这个网格是深红色的,可用的车辆越多,在这个网格是蓝色越深,越会有需求,和网格中的数字代表了特定的值。在图中所示的场景6(一),要求是44超过可用出租车的数量,和不满足的要求是527开头。我们的模型调度后,有44不满足要求,需求满足率是91.65%,出租车利用率是100%。TLR模型调度后,160年不满足需求,满意度为69.64%,出租车利用率是75.9%。在图中所示的场景6 (d),需求是114不到可用车辆的数量,和未满足的需求是450开头。我们的模型调度后,所有的需求都被满足,满足率是100%。TLR模型调度后,仍有106人不满足需求和满意度为76.44%。
(一)
(b)
(c)
(d)
(e)
(f)
根据图6,我们可以看到,本文提出的模型在所有时期表现更好。在高峰时期,周一到周五的早上9点,如图6(一),供需失衡严重,可用出租车的数量小于需求。在这种情况下,我们的模型调度后,如图6 (b)利用所有可用的车辆;换句话说,没有更多的出租车可以安排来满足需求;TLR模型,如图6 (c),大部分的需求得到满足,但是仍有许多可用的出租车离开未使用。在周末晚上9点,如图6 (d),失衡的程度相对较轻,可用出租车的数量大于需求。在这种情况下,我们的模型调度后,如图6 (e),所有的要求都满足了,剩下的出租车是均匀分布的。然而,TLR模型,如图6 (f),无法满足所有的要求,即使出租车的数量超过了需求。此外,从数据可以看出6 (c)和6 (f)热区和冷区分开TLR模型的调度后,这表明,如果冷区和热区远,出租车在炎热的区域不能使用。这表明对比模型是一个当地的优化模型,我们的模型是一个全局优化模型,可以实现供给和需求的平衡在全球范围。
图7显示两个调度模型目标函数下的比较结果1在工作日和周末。实验比较两个模型的调度结果从早上8点到晚上10点使用一个月的数据。很明显从图,该模型比比较模型作为一个整体。,该模型比比较模型更稳定;比较的结果模型在早晚高峰时期比其他时期;原因在于,相邻网格调度的策略使用的比较模型不能充分利用出租车资源,尤其是当许多网格需要出租车。与平时相比,两种方法的目标函数值变得更高,和周末两种方法之间的差距变得越来越小。原因是需求的时空分布更加均匀周末和高峰时间在早上和晚上是较弱的。根据上述模型提出了可以更高效的利用出租车资源和满足乘客的需求更好。
(一)
(b)
实验进行一个8核机8 g RAM。的次数,一个目标矩阵分裂随数量的代理。但分裂操作非常快;总分裂时间不超过0.01秒。因此,运行时间主要是由强化学习算法的速度。强化学习算法需要一些时间去探索最优策略。我们重复试验100次,平均程序的运行时间是13.88秒。
7所示。结论
在本文中,我们提出了一个MARL-based出租车predispatching模型来平衡供需的出租车在城市的不同区域。通过历史数据的分析,我们发现不同的功能区域有不同的人群移动模式,和他们都有规律。然后,为了提前对出租车的需求情况,我们用三个时间序列预测方法来预测每个网格的出租车皮卡请求在未来和比较他们的结果。最后,根据分布的出租车在当前时间,调度模型的基础上,可替换主体强化学习用于调度网格之间的出租车。降低算法的计算复杂度,我们采取各个击破的策略,将总体任务划分为子任务,这些子任务可以由单个机器,加工,每个小任务可以并行的。最后总结获得的调度方法是所有子任务的结果,从而大大提高了计算速度和出租车调度的实时性能。
在实验部分,我们首先比较三种预测模型的预测结果。结果表明,FBprophet模型下表现最好的两个评价指标,所以我们最后使用的预测结果FBprophet近似实际需求情况。然后我们比较该调度算法与TLR服务推荐方法相结合。从结果我们可以看出,该调度算法具有更好的性能在不同的场景,不同流量条件下,性能稳定。
在未来,我们将进一步进行更细粒度的调度;具体我们将研究出租车应该派遣在每个网格中,每个出租车如何选择路线,和在哪里可以找到乘客在达到指定的网格。我们将努力解决这些问题,进一步提高出租车服务的效率。
数据可用性
原始数据用来支持这项研究没有提供,因为隐私问题。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是由中国国家自然科学基金会批准号。61772230和61772230下,中国的自然科学基金对于年轻学者(没有。61702215),中国博士后科学基金会(2017 m611322和2018 t110247号),和长春科技开发项目(没有。18 dy005)。