基于sufferage的动态出租车拼车调度算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于sufferage的动态出租车拼车调度算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：目前对于拼出租车调度问题的研究多集中于静态的或者“一个起点到多个终点”和“多个起点到一个终点”的动态拼车。针对“多个起点到多个终点”的动态拼出租车问题，首先对拼车和任务调度两个问题进行了分析比较，建立了拼车问题的任务调度模型；然后给出了计算拼车任务完成时间的算法；最后根据任务完成时间计算任务的sufferage值，并基于任务调度中的sufferage算法的原理，给出了一种动态拼出租车调度算法。实验结果表明，提出的动态拼出租车调度算法可以有效提高整个拼车系统的成功率，缩短乘客的平均拼车完成时间。
关键词：动态拼车；拼出租车；任务调度；sufferage
中图分类号：TP399文献标识码：A文章编号：1009-3044(2011)28-7019-05
Dynamic Taxipooling Scheduling Algorithm Based on Sufferage
FENG Tian
(Key Laboratory of Embedded System and Service Computing of Ministry of Education, Tongji University, Shanghai 201804, China)
Abstract: The study of taxipooling problem is mainly focus on static case or the dynamic case of "one origin to many destinations" and "many origins to one destination". For the case of "many origins to many destinations", this paper first analyzed and compared taxipooling problem and task scheduling problem, and established the schedule model for taxipooling problem. Then, an algorithm to calculate the completion time of taxipool was presented. Finally, the sufferage value of taxipool was calculated by the completion time, and a dynamic taxipooling scheduling algorithm was proposed based on the principle of suffrage algorithm in task scheduling. The experimental results showed that the proposed algorithm can improve the success rate of taxipooling and reduce the average completion time as well.
Key words: dynamic carpool; taxipool; task scheduling; sufferage
1 概述
现代都市中，随着车辆的增多，停车占地、道路拥堵、交通污染等问题日益严重。一人一车不仅会增加道路上的车辆数量，导致交通堵塞，而且毁车费油，加大空气污染。拼出租车是一种类型的拼车，也即具有相同方向的乘客同乘一辆出租车[1]。出租车具有私家车相当的移动性和易用性，因而具有很多优点。首先，拼出租车时乘客一般只需付比平常少的费用，可以降低乘客的出行成本，而司机可收取多人的付费而得到比平时较多的收入。其次，车费的降低有利于提高出租车的乘坐率，降低出租车的空驶率，相应减少了车辆对环境的污染。此外，出租车作为一种商业运营行为，相对于拼私家车，乘坐出租车时乘客的权益会得到法律的保障，有专业的司机提供服务，具有较低的安全风险，并且乘客到达目的地之后不用担心停车问题。最后，虽然各个城市都有大量的出租车，基本能够满足社会需求，但在上下班和雨雪天气等情况下，仍存在“打的”难的问题。拼出租车的推广，必将在一定程度上解决这一问题，缓解交通压力。
拼车中的关键问题就是车辆和乘客的匹配以及车辆行驶路径问题。静态拼车问题通常被建模为VRPPDTW问题 [2-3]（vehicle routing problem with pickup and deliveries and time windows，集取货送货一体的车辆路径问题），用启发式方法进行求解。由于缺乏有效的信息技术和通讯技术支持，拼车请求匹配列表的自动生成问题被研究了很多年。一些学者将拼车问题作为电话叫车问题（dial-a-ride problem）的一种特例，并根据问题的规模和特性提出了他们的解决方法[4-6]。动态拼车问题和一般的拼车问题不同，动态拼车是针对个别的出行，而不是基于有规律的出行。近年来，智能交通系统ITS、地理信息系统GIS、定位技术、手持设备的发展，为出租车服务带来新的机遇。通过ITS技术，出租车调度中心可以监控整个车队的位置和运动，并实时获得手机等移动用户的位置和拼车需求[7]。动态拼车请求可以在需要拼车时及时提出[8]。国内外对拼出租车问题已做过一些研究。文献[9]基于“贪婪”方法和时空网络提出了两种启发式算法来解决动态拼出租车问题 ，文献[10]使用模拟退火算法对文献[9]中的算法进行了改进。但是这些方法仅考虑了从一个起点到很多终点（“one-to-many”）和从很多起点到一个终点（“many-to-one”）的情况，不适用于复杂的多个起点到多个终点的情况。
本文针对多个起点到多个终点的动态拼出租车问题，建立拼车问题的任务调度模型，并基于任务调度中的sufferage算法原理，给出一种基于sufferage的动态出租车拼车调度算法。
2 任务调度相关概念
任务调度问题中对于系统中的M个资源和不断到来的任务，每个任务需要在一定的资源上执行，任务有提交时间，任务在资源上有相应的执行时间，资源只有在执行完分配在其上的所有任务之后才能执行新的任务。任务调度问题就是要找出一个任务到资源的映射，使得系统能够最快的完成所有的任务。
现有的启发式任务调度算法分为两类：在线模式和批模式[11]。在线模式是指任务只要到达调度器就立刻分配给资源。常见的两种在线模式调度算法是 MET(Minimum Execution Time最小执行时间)和 MCT (Minimum Completion Time最小完成时间)。批模式是指映射事件发生时开始将成批的任务按照一定的策略分配给资源。常见的批模式调度算法有Min-Min 算法、Max-Min 算法、Suffrage 算法。其中，Min-Min算法优先选取最早完成时间最小的任务进行调度。Max-Min算法优先选择最早完成时间最大的任务进行调度。Sufferage算法的原理是，一个任务将被分配给这样一个资源，如果该任务不分配给该资源，将会在完成时间上蒙受最大的损失。该算法为每个任务指定一个Sufferage值该值定义为任务的次小完成时间与最小完成时间之差，差值大的任务具有高的调度优先级。
3 基于sufferage的动态拼出租车调度算法
3.1 拼车问题的任务调度模型
本文拟解决的问题是对于乘客的实时拼车请求，调度中心通过调度算法，将合适的车辆指派给乘客。如果将有空位的车辆看做资源，乘客的拼车请求看做任务，那么，拼车调度问题就变为将拼车任务分配到车辆资源上执行。
拼车问题和任务调度问题的不同之处在于：
1）任务调度问题中，资源j在执行完已分配在其上的所有任务之后，才能执行新的任务，资源j可以执行任务i的时间，即资源j的就绪时间与分配在其上的任务的执行时间有关，与待分配的任务i无关。在拼车问题中，车辆j在执行任务的过程中（车内有乘客），只要车内有空位，就可以接受新的拼车任务（新的拼车请求），车辆j开始执行乘客i的拼车请求的时间，不仅与车内乘客的路径有关，还与待分配乘客i的位置有关。
2）任务调度问题中，任务i在资源j上的预测执行时间为主机在零负载情况下执行每个任务的时间，是通过一些性能评估机制来预测的。而在拼车问题中，乘客i在车辆j上的执行时间是根据车辆的行驶路径来预测的。
3）任务调度的目标通常是使时间跨度（makespan）较小，时间跨度是指整个系统完成所有任务的时间。而拼车问题的目标是使更多乘客的拼车请求得到满足，并且每个乘客都能尽早到达目的地。
通过对拼车问题和任务调度问题进行分析，建立拼车问题与任务调度问题的对应关系如下：
1）任务i，对应于乘客i的拼车请求（下文中也称作乘客i或者拼车任务i。
2）资源j，对应于车辆j。
3）任务i在资源j上的执行时间eij，对应于乘客i乘坐车辆j从其起点至目的地的时间。
4）资源j关于任务i的就绪时间wij，对应于乘客i从提出拼车请求到坐上车辆j的时间。
5）任务i在资源j上的完成时间cij，对应于乘客i从提出拼车请求至乘坐车辆j到达目的地的时间。由以上定义可知cij =wij + eij。
6）任务i的完成时间ci，ci={ cij | 如果乘客i被分配到车辆j中}。
可见，我们可以将拼车问题转换成一类特殊的任务调度问题，并选用任务调度算法进行处理。
对于拼车问题，如果采用在线模式的算法进行处理，就是每当有乘客提出拼车请求，就为他进行最优的分配，对应于任务调度中的MCT算法，虽然实现方式简单，但是应用在拼车中存在以下的问题：
1）问题1：以车外乘客的最小完成时间为标准来调度车辆并规划车辆路径，只考虑了车外请求拼车的乘客的利益，没有考虑车内乘客的时间损失。在车外请求拼车的乘客的完成时间达到最小的同时，车内乘客的绕路时间可能相对较大，从而使得车内乘客到达目的地的时间较晚。
2）问题2：当时间上相隔很近的若干个拼车请求竞争同一辆车上的座位，也就是说待分配的乘客分别有一辆或者几辆可以乘坐的车辆，但是使他们获得最短完成时间的车辆都是同一辆。这时，如果按照在线模式算法进行处理，则该座位将分配给最早提出拼车请求的乘客a。这样做，对于乘客a是最优的，但是对于系统来说，可能会由于将该车辆分配给前者后，导致后者没有可以乘坐的车辆或者需要等待很长的时间，影响系统的拼车成功率和平均完成时间。
针对以上两个问题，本文采用如下策略：
1）对于问题1，由于乘客i乘坐车辆j的完成时间cij对应于乘客i从提出拼车请求至乘坐车辆j到达目的地的时间，与车辆j的行驶路径密切相关。而车辆j的行驶路径又与车内乘客的起点和终点相关。所以，本文在将乘客i的起点和终点插入原车辆路径时，同时考虑车外乘客和车内乘客的起点和终点，引入绕路系数α和绕路系数β分别表示车内乘客能忍受的最大绕路系数和车外乘客i能忍受的最大绕路系数，找出满足绕路系数α和β的最短车辆路径，从而得到相应的完成时间。这部分内容将在3.2.1节中详细介绍。
2） 对于问题2，以批处理模式代替在线模式，每隔时间T做一次决策（T的设置应该较短，是一个乘客可以接受的时间），处理时间T内所有的拼车请求，找到最优的方案，并通知乘客和司机。由拼车问题的目标和批处理算法的特点，本文基于sufferage算法原理进行处理。这部分内容将在3.2.2节中详细介绍。
3.2 基于sufferage的拼车调度算法
拼车任务的Sufferage值定义为拼车任务的次小完成时间与最小完成时间之差，差值大的任务具有高的调度优先级。算法首先要计算每一个拼车任务相对于每一辆车的完成时间，然后再计算每个拼车任务对应的sufferage值，从而根据Sufferage算法的原理对拼车任务和车辆资源进行映射。
3.2.1 拼车任务完成时间的计算
对于每一个乘客的拼车任务和每一辆车，首先按照最小插入代价将乘客的起点和终点插入原车辆路径中，得到新的车辆路径，从而计算相应的时间。
对于乘客起点origin和终点dest的插入，有三种情况，分别如图1 中(a),(b),(c)所示。
情况1：起点与终点都插入原路径中间。
情况2：起点插入原路径中间，终点插入原路径末端。
情况3：起点插入原路径末端，终点插在起点之后。
图1中，向量c={c1,c2,…,cend}表示车辆行驶路径中的关键位置，包括已经分配到车上的乘客的起始点和目的地。nextstop表示车辆行驶路径中下一个停靠点的编号，nextpath表示车辆当前位置与下一个停靠点的距离。车辆从当前位置current到乘客目的地dest的距离记做completepath，代表乘客的拼车完成距离。用 D[a][b]表示站点a与站点b之间的最短距离，P、Q分别表示乘客起点和终点的插入位置。
引入绕路系数α和β作为过滤值，分别表示车内乘客能忍受的最大绕路系数和车外乘客能忍受的最大绕路系数。其中，车外乘客的绕路系数表示将乘客的起点和终点插入车辆路径之后，乘客的实际路径与最优路径相比其增量的比例，显然该值越大表示车外乘客的绕路越多。车内乘客的绕路系数表示在原路径的两个关键位置之间插入乘客的起点或终点后，这两个关键位置之间增加的距离与原距离的比例，显然该值越大表示车内乘客的绕路越多。若将乘客的起点或终点插入到最后一个关键位置之后，则对车内乘客无影响，此时无需计算车内乘客的绕路系数。
算法1 给出在路径（A，B）之间插入X时，计算绕路系数不超过α的最小插入代价mincost和对应的最优插入位置p的算法。
算法1：
1. for 路径（A，B）之间的每一个插入位置k
2. 插入前后的路径之差
costk=D[ck][X]+D[X][ck+1]-D[ck][ck+1]
3. 计算绕路系数rk=costk/D[ck][ck+1]
4. if (rk＞α)
将costk置为最大值MAX。
5. if (costk＜mincost)
mincost=costk，插入位置p = k
6. endfor
计算拼车任务i在车辆j上的完成时间cij的流程如算法2所示。
算法2：
1. 初始化车辆i的剩余关键位置向量c={c1,c2,…,cend}
2. 根据算法1计算乘客起点在路径(c1,cend)中的最小插入代价cost_omid，以及插入位置p
3. 根据算法1计算乘客终点在路径(P,cend)中的最小插入代价cost_Dmid，以及插入位置q
4. 计算情况1的插入代价 cost1=cost_omid+cost_Dmid，P=p，Q=q
[4] Zhi-hai Xiang,Cheng-bin Chu,etc.A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints[J].European Journal of Operational Research,2006,174:1117-1139.
[5] Cordeau J F,Laporte G.A Tabu Search Heuristic for the Static Multi-vehicle Dial-a-ride Problem[J].Transportation Research Part B,2001,37:579-594.
[6] Attanasio A,Cordeau J F,etc.Parallel Tabu Search Heuristics for the Dynamic Multi-vehicle Dial-a-ride Problem[J].Parallel Computing,2004,30:377-387.
[7] Calvo R W,Luigi F L,etc.A Distributed Geographic Information System for the Daily Carpooling Problem[J].Computers & Operations Research,2004,31:2263-2278.
[8] Daily D J,Loseff D,etc.Seattle Smart Traveler: Dynamic Ride matching on the WWW. Transportation Research Part C[J].1999(7):17-32.
[9] Chi-Chung Tao,Chun-Ying Chen.Heuristic Algorithms for the dynamic taxipooling problem based on Intelligent transportation system technologies[J].Transportation Research Part B,2001,137:579-594.
[10] 张瑾,何瑞春.解决动态出租车“拼车”问题的模拟退火算法[J].兰州交通大学学报,2008(3).
[11] Maheswaran M, S Ali,etc.Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems[J].Journal of Parallel and Distributed Computing,1999,59:107-131.
[12] 车勇.基于多人合乘模式的出租车智能调度管理系统设计与研究[D].上海:同济大学,2008.
[13] 张瑾.出租车“拼车”问题研究及其服务系统设计实现[D].兰州:兰州交通大学,2009.
[14] Petros Lalos,Andreas Korres,etc.A Framework for dynamic car and taxi pools with the use of Positioning Systems[J].2009 Computation World:Future Computing, Service Computation,Cognitive, Adaptive,Content,Patterns,2009,55:385-391.