笔记：调度算法（三）

《带时间窗的网络动态共乘问题研究》

绪论

现有动态共乘研究存在的问题

一、偏重宏观研究，缺乏对个体出行决策的讨论，特别是如何实现时间窗约束下的多需求、多供给匹配，如何提高共乘意愿，哪种匹配方式最有效等；

二、多数研究仍然沿用合乘的传统理论，模型相对简单，信息科技的作用不突出；

三、数据集比较单一，缺乏来自调度系统、社区网络和意向性调查的社会全数据支持；

动态共乘需要解决的基本问题

一、激励和保障：如何解决使用动态共乘的后顾之忧，增加对参与使用意愿的保障；

二、动态匹配：如何在满足时间和共乘偏好的前提下，解决大范围的动态共乘供给与需求之间的快速匹配；

三、信息科技融合：如何发挥信息科技优势，使网络动态共乘更加容易被人们使用；

动态共乘模型

问题描述

个体表示
- 司机，位置信息，时间信息，订单信息
- 乘客，位置信息，时间信息
个体时间信息
- 期望出发时间
- 期望到达时间
- 弹性时间（期望到达时间 - 期望出发时间 - 实际用时）；
资源
- 资源：车辆的空闲位置；
- 收益：提高车辆的平均占用人数；
约束
- 参与者：满足所有动态共乘参与者的时间窗限制，不会改变原有乘客的出行计划，在弹性时间内为供需双方找到合适的匹配；
- 系统：满足资源限制，同时提高资源的利用率；

单司机单乘客动态共乘模型

模型假设与运行规则：

系统运行在一个边长为 L 的正方形区域，所有个体位于正方形区域内，共乘在区域中进行；
个体以一定的时间间隔进入系统，其到达数量满足参数为 λ 的泊松分布；
个体在进入系统前角色不确定；
个体进入系统是的位置信息包括出发地和目的地，以系统运行区域内的直角坐标表示，x,y满足均匀分布；
个体进入系统时均位于自己的起始位置，乘客在起点等待匹配，司机在原点等候首单；
个体进入系统的时间信息包括最早出发时间，时间窗长度，以及最晚到达时间；
个体的时间信息满足如下关系：最早出发时间 + 时间窗长度 + 必要行驶时间 = 最晚到达时间；
不考虑两点间的距离差异，两点距离取欧氏距离；

动态共乘模型中的节点匹配算法：

实现从现有的乘客和司机节点中找到到相互之间可行的配对集合。
在可行节点中，找到当前条件下满足系统收益最大化目标的最优解；
固定时间间隔进行共乘：新的节点进入系统时并不马上进行匹配，而是进入等待池，当到达匹配时间节点时，系统会对所有扔处于等待状态的个体进行一次全局匹配；

单司机多乘客动态共乘模型

共乘路线的多样性：多个乘客时，路线中起点和终点的排序问题；
行驶途中的动态匹配：途中有新的乘客加入可能会改变原有的行驶路线；

动态变化的匹配条件

对于每个要接的乘客，要在其时间窗范围内到达他的起点位置；
对于路线中每个乘客都能够在最晚时间之前被送达目的地；
每当有新的匹配后对共乘路线进行调整，调整后的新路线对于其中的每个个体仍然要满足以上两个条件；
在所有满足可行条件的路线中选择能够节省更多路程的线路；

仿真模型概述

仿真平台

基于Netlogo仿真平台进行系统仿真。

系统环境设定及循环处理机制

时间窗检查
系统运行指标的设定
- 系统平均匹配成功率；
- 时间节省比率；
- 平均等待时间；

《城市车辆动态拼车调度机制研究》

动态拼车算法设计

问题定义

拼车的代价和好处可以用行驶路程进行量化表示，并且所获得的收益都是与相对不拼车时节省的行驶路程成正比。

优化目标：在能满足用户乘车需求的情况下，寻找能够最大化节省行驶里程的拼车目标进行匹配。

形式化：

地理位置：\(L<lon, lat>\) lon表示经度，lat表示纬度
车辆状态：\(C_i<L_c, P_c, L_d>\) Lc表示出租车当前位置，Pc为当前乘客人数，Ld为出租车当前目的地
用户请求：\(Q<T_p, L_s, P_r, L_d, t_w, t_s>\) Tp为出发时间，Ls为用户的出发地，Pr为需求的座位数
行驶路程长度：\(d(L_i, L_j)\) 对于两个位置 Li 和 Lj，它们之间在道路上实际需要行驶的距离
路程节省：\(e(Q_i, Q_j)\) 对于请求 Qi 和车辆 Cj 进行拼车时，两人独行总路程和共乘的路程之差

朴素动态拼车算法

思想：

首先获取所有车辆的当前状态，对每一辆车计算拼车后节省距离；
计算 Qi 与所有目标车辆的路程节省之后，选取能够节省最多路程的拼车目标，完成匹配；

缺点：计算量太大，无法满足需求

改进的基于聚类的动态拼车算法

思想：

每个用户都有一定的可等待时间 \(t_w\)，系统在收到用户的请求后并不立即处理;
在某一时刻对所有有效的用户请求进行聚类，每个子类就是一个拼车方案；
由于用户请求是动态变化的，聚类操作按照一定频率反复进行，从而满足要求；

缺点：该算法只针对动态更新的用户请求进行处理，但是忽略了道路上正在行驶的汽车，某一时刻的最优，由于新的请求的加入不再最优，需要考虑修正。

改进：

系统在收到请求时，并不立即对其进行匹配；
达到一定时间间隔时，获取所有当前有效的用户请求集合，分为两块，即将超时的用户请求集合和剩余的用户请求集合；
获取当前道路上的车辆状态（满载除外），根据车辆的当前位置以及目的地，构造一个用户请求，从而参与到对请求的聚类中去，构造所有请求，形成另一集合；
贪婪的近似算法进行聚类；
- 处理：
  - 将所有请求分为两类，即将过时的请求和其他请求；
  - 对于即将过时集合中的每个请求，计算其与剩余集合中每个请求的节省距离，按距离节省量排序；
  - 计算每个请求的总的节省距离；
- 过程：
  - 选取总效用最大的请求Qi，从Qi对应的行选取出前n个效用最大的目标拼车，n为一辆车所能容纳的最大请求数；
  - 如果这n个请求进行拼车的节省路程大于预设的一个最小节省值 Min Saving，匹配成功；
  - 将对应请求移除，病假效用矩阵总对应请求的效用改为0；
  - 循环以上步骤，不断生成拼车方案，知道不存在满足要求得解；
  - 剩余请求标记为拼车失败，建议单独出行；

缺点：很多请求会在即将超时时才会得到响应，不满足实时性；

基于位置近似的动态拼车算法

位置网格化：

为了方便计算和表示，将出租车所在城市区域分割成近似正方形的网格，每个网格大小相同；
网格区域确定后，为每个网格点选定一个代表点，用来表示整个网格区域，代表点为区域内打车热门点；
根据网格之间道路的实际情况，实现计算好网格之间的实际行驶距离以及需要的行驶时间，结果存储在 n*n 的矩阵中；

车辆状态表示：

为每个网格都维护一张车辆状态表，该表按照时间信后顺序进行排序，记录预计将要进入此网格的车辆的相关信息，包括：车辆编号，预计到达网格时间，当前乘客人数；

路径规划和表示：车辆的行驶路径用它所要经过的网格来表示；

匹配算法：借助与网格相关的缓存表，快速筛选出时间上符合用户要求的车辆，在这些车辆中选出能够最大程度减少车辆运行总行驶里程的拼车对象；

出发地匹配：保证车辆可以在指定时间，指定地点接到乘客，并且空位数满足用户要求；
- 对于用户请求，根据出发地和目的地，规划路径；
- 找到出发地对应网格，根据维护的最近网格表，寻找最近网格；
- 对于最近网格表中的每个网格，按顺序访问它的网格状态表，选出能够在用户要求时间内接到用户的车辆；
目的地匹配：保证车辆可以在指定时间，指定地点送乘客到达目的地；
- 匹配成功的两种情况：
  1. 拼车乘客所要去的目的地离车辆当前行驶路径上的某一点距离不远；
  2. 车辆当前的目的地离拼车乘客所要行驶的路径上的某一点不远；
- 两种情况分别对应：
  1. 车辆先将拼车乘客送达目的地，再将原始乘客送往目的地；
  2. 车辆先将原始乘客送到目的地，再将拼车乘客送达目的地；
- 针对第一种情况：
  - 先得到拼车乘客的目的地所在网格，并获取该网格的临近网格表；
  - 按行驶时间增序依次选取临近网格表中的网格，检查它是否出现在车辆的当前路径中；
  - 同时，保证当前乘客要容忍搭载新乘客到目的地所产生的时延；
  - 将符合以上条件的车辆和其所要行驶的偏移路径和偏移距离记录下来，加入集合；
- 针对第二种情况：
  - 先得到拼车乘客的目的地所在网格，并获取该网格的临近网格表；
  - 按行驶时间增序依次选取临近网格表中的网格，检查它是否出现在车辆的当前路径中；
  - 同时，保证新乘客要容忍送原有乘客到目的地所产生的时延；
  - 将符合以上条件的车辆和其所要行驶的偏移路径和偏移距离记录下来，加入集合
最优方案选取：选取所有满足的方案中，节省距离最多的拼车方案；
- 对于集合中的所有方案，选取节省距离（两者之间公共距离减去偏移距离）最大的方案。
匹配完成后的操作：匹配成功，更新相应网格的车辆状态表，匹配失败，建议用户单独出行；
- 路径规划方法给出唯一路径，那么匹配车辆确定后，车辆行驶的路线就确定了；
- 对车辆路径上所有网格中的车辆状态表进行更新，修改该车到达这些网格的预计时间和人数；

实时出租车拼车调度研究

技术上需要解决的问题

方便：尽量减少用户所需要的操作，方便计算和分配拼车收益；
快捷：服务速度比较快；
有效：拼车的成功率要比较高；
准确：拼车方案要能真正获得收益，并且最好最大化收益；

数据处理

数据源：上海地区出租车位置数据集，找到的其他数据集。

预处理：

去除噪声数据；
去除不活跃数据，统计每辆出租车所出现过的不同地点的数量，如果小于100，则说明车辆行为不活跃；
利用载客信息

实时出租车拼车系统的设计

问题定义：在一个有许多车辆的城市出租车系统中，当有乘客发出新的请求时，系统根据乘客人数、出发时间、出发地、目的地、用户的容忍度，寻找最佳的拼车方案，以达到最大程度节省出租车的行驶距离。

假设条件：

系统能够知道全局状态；
只要能节省费用，乘客总是愿意拼车；
同一块区域中，两点之间的距离可以忽略不计；
用户对达成的出发时间有严格限制，但是达到时间没有严格限制；
只允许两批乘客共乘；

匹配算法：

基于聚类的拼车算法；
基于位置近似的拼车算法；

收益分配算法：

\(S_1, S_2\)：乘客单独打车时的行驶距离；
\(S_d\)：拼车后的行驶距离；
\(\alpha\)：收入分配系数，表示司机和乘客之间的收益分配，乘客之间按照单人行程分配；

系统模拟实现与仿真测试

需求提取：获取乘客的打车请求，包括：出发地，出发时间，目的地；

预处理：

实验将兴趣范围限制在上海地区内环范围内，经度 121.39858 到 121.58775，纬度 31.18402 到 31.28794；
基于这个范围，将其划分为 50*30 的网格，经度方向50格，纬度方向30格，一个街区一格。
模拟时间，早上九点到晚上九点；

参数选取：

时间的最小单位为分钟，距离最小单位为米；
乘客忍耐等待时间和客户可以容忍拼车增加时间为10分钟；
基于聚类的算法，将聚类算法的迭代间隔设置为1分钟，将离用户容忍的等待时间还剩一分钟之内的请求定义为即将超时的请求；

路径规划：调用 Google Map API ，是由谷歌地图提供的路径规划调用接口，对于一个出发点和目的地确定的请求，将其经纬度发送至Google Map API，获取其规划好的路径及运行时间等结果。对于次路径，根据每个点所在的位置将其转化为网格序列，获取网格化后的路径数据，并且可以知道到达各个网格的时间。为了节省API的使用，提高计算效率，可以针对出发网格和目的地网格信息进行缓存。

乘坐人数模拟：据统计，出租车平均每次载客人数为1.5次每人，包括司机为2.5人每次。根据中值为1.5，标准差为1的正态分布的概率密度函数，给每个乘坐请求随机分配1，2，3的人数，对于每个请求，它的需求人数为1、2、3的概率分别为0.422、0.422、0.156。

出租车的行动规则：模拟开始时，出租车位置为原数据集中该出租车所处的位置，当调度系统匹配到某出租车是，出租车根据调度开始运动，当所有乘客送达目的地后，出租车停留在当前位置，等待系统的调度。

动态共乘中文论文泛读