考虑接驳费用的车辆共享调度算法研究
发布时间：2021-03-25 07:04
针对现有的车辆共享调度算法未充分考虑车辆共享调度时造成的接驳费用问题,研究最小车辆规模最少接驳费用调度优化模型,并改进二分图匹配算法进行求解。根据车辆共享过程中调度方案的优化问题描述,以满足给定出行需求的车辆规模最小以及车辆调度接驳费用最少为目标,构建双目标优化模型。基于有向无环图对车辆出行需求进行建模,将模型求解转化为二分图最大匹配且权重最优匹配问题,提出Kuhn-Munkres算法求解最大匹配最小权重匹配的权重设置条件并进行证明,进而设计Hopcroft-Karp与Kuhn-Munkres算法融合框架进行求解。以安徽省宣城市部分出行为例进行模型和算法合理性分析,479辆自动驾驶共享车辆可以满足13 575个出行需求;与未考虑接驳费用目标的调度算法相比,调度总费用减少40.8%左右。算法可求解最小车辆规模并降低调度成本。
【文章来源】：交通信息与安全. 2020,38(02)北大核心CSCD
【文章页数】：10 页
【部分图文】：
车辆共享接驳示意Fig.1Vehiclesharingdiagram
ǖ挠邢蛭藁吠冀?Ａ瞬煌?某盗镜鞫?的分配方案。例如，图2（a）所示的车辆分配方案包括：T1T3，T1T2T3，T1T4T3，T5T4T6，T5T6。图1的最小车队规模问题则转化为求解有向无环图的最少不相交路径覆盖问题。如图2（b）所示，T1T2T3，T5T4T6为图2（a）有向无环图的最小不相交路径覆盖，路径数量为2，表示满足图1车辆出行需求的车辆共享最小规模为2。（a）车辆共享有向无环图（b）最小不相交路径覆盖图2车辆有向无环图Fig.2Directedacyclicgraphofvehiclesharing2.2二分图的最大匹配与带权最大匹配2.2.1二分图匹配对于上述构建的车辆共享有向无环图，其最小路径覆盖问题可以应用二分图的最大匹配算法进行求解。二分图是一种经典的图论模型，最早用于婚恋匹配的问题中，目前已形成比较成熟的理论。二分图一般用G=(X?Y?E)表示，X?Y表示顶点集分割的不相交的2个子集，E为连接2个集合的边集，其连接的2个顶点分别在X?Y这2个子集中。在本研究当中，把图2有向无环图描述的车辆出行需求T={T1?T2??Tk}中的每个点Tk拆分成Tkx和Tky这2个点，见图3（a）。对于V=(N?E)，如果2个出行需求Tx和Ty能够连接，则加1条边从X集合中的Tx指向Y集合中的Ty，即可得到V所对应的二分图。二分图有以下3个核心概念。1）最大匹配。在二分图G=(X?Y?E)中，若存在1个子图MíG，且M中的任意的边集均不同时连接到同一顶点，则称M为G的1个匹配，见图3（b）实线
算法流程获得KM算法改进条件后，提出求解最大匹配情况下最小权重匹配的HK-KM算法流程。算法在给定出行需求后，将出行需求转化为有向无环图，进一步转化为二分图，根据出行的时空信息构建二分图的衔接矩阵和费用权重矩阵。最小车辆规模目标模型输入二分图衔接矩阵，通过HK算法求解二分图最大匹配k，同时，最少费用目标模型输入原始接驳费用权重和最大匹配数k，补充边的权重调整为L>klmax，通过调整后的KM算法求解最小权重匹配，即可求得最大匹配情况下最小权重匹配方案。具体算法流程见图6。图6最小车辆规模最少费用求解算法流程图Fig.6Algorithmflowchart3案例研究3.1出行数据获取案例分析选取安徽省宣城市中心城区某年某月卡口系统的车牌识别数据进行先验信息库的构建与案例分析，数据内容见表1。宣城市位于安徽省东南76
【参考文献】：
期刊论文
[1]无人驾驶汽车共享调度方法研究[J]. 崔洪军,李雨生,朱敏清,李霞,宋长柏. 公路交通科技. 2019(12)
[2]未来城市自动驾驶共享汽车规模研究：以上海为例[J]. 姚晓锐,王冠,杨超. 交通运输系统工程与信息. 2019(06)
[3]基于调度池的共享单车调度研究[J]. 蒋塬锐,贾顺平,李军. 交通信息与安全. 2019(05)
[4]基于遗传算法的定制公交多停车场多车线路优化[J]. 王超,马昌喜. 交通信息与安全. 2019(03)
[5]自动驾驶条件下共享车辆车队规模[J]. 王冠,杨超,张英杰,陈海林. 综合运输. 2019(02)
[6]无人驾驶汽车路径跟踪控制方法拟人程度研究[J]. 郭应时,蒋拯民,白艳,唐杰帧. 中国公路学报. 2018(08)
硕士论文
[1]基于车联网环境的共享自动驾驶汽车调度研究[D]. 王睿.大连理工大学 2019
[2]基于匹配理论的共享车辆网络稳定最优车辆调度策略[D]. 钟宜轩.哈尔滨工业大学 2019
本文编号：3099263
【文章来源】：交通信息与安全. 2020,38(02)北大核心CSCD
【文章页数】：10 页
【部分图文】：
车辆共享接驳示意Fig.1Vehiclesharingdiagram
ǖ挠邢蛭藁吠冀?Ａ瞬煌?某盗镜鞫?的分配方案。例如，图2（a）所示的车辆分配方案包括：T1T3，T1T2T3，T1T4T3，T5T4T6，T5T6。图1的最小车队规模问题则转化为求解有向无环图的最少不相交路径覆盖问题。如图2（b）所示，T1T2T3，T5T4T6为图2（a）有向无环图的最小不相交路径覆盖，路径数量为2，表示满足图1车辆出行需求的车辆共享最小规模为2。（a）车辆共享有向无环图（b）最小不相交路径覆盖图2车辆有向无环图Fig.2Directedacyclicgraphofvehiclesharing2.2二分图的最大匹配与带权最大匹配2.2.1二分图匹配对于上述构建的车辆共享有向无环图，其最小路径覆盖问题可以应用二分图的最大匹配算法进行求解。二分图是一种经典的图论模型，最早用于婚恋匹配的问题中，目前已形成比较成熟的理论。二分图一般用G=(X?Y?E)表示，X?Y表示顶点集分割的不相交的2个子集，E为连接2个集合的边集，其连接的2个顶点分别在X?Y这2个子集中。在本研究当中，把图2有向无环图描述的车辆出行需求T={T1?T2??Tk}中的每个点Tk拆分成Tkx和Tky这2个点，见图3（a）。对于V=(N?E)，如果2个出行需求Tx和Ty能够连接，则加1条边从X集合中的Tx指向Y集合中的Ty，即可得到V所对应的二分图。二分图有以下3个核心概念。1）最大匹配。在二分图G=(X?Y?E)中，若存在1个子图MíG，且M中的任意的边集均不同时连接到同一顶点，则称M为G的1个匹配，见图3（b）实线
算法流程获得KM算法改进条件后，提出求解最大匹配情况下最小权重匹配的HK-KM算法流程。算法在给定出行需求后，将出行需求转化为有向无环图，进一步转化为二分图，根据出行的时空信息构建二分图的衔接矩阵和费用权重矩阵。最小车辆规模目标模型输入二分图衔接矩阵，通过HK算法求解二分图最大匹配k，同时，最少费用目标模型输入原始接驳费用权重和最大匹配数k，补充边的权重调整为L>klmax，通过调整后的KM算法求解最小权重匹配，即可求得最大匹配情况下最小权重匹配方案。具体算法流程见图6。图6最小车辆规模最少费用求解算法流程图Fig.6Algorithmflowchart3案例研究3.1出行数据获取案例分析选取安徽省宣城市中心城区某年某月卡口系统的车牌识别数据进行先验信息库的构建与案例分析，数据内容见表1。宣城市位于安徽省东南76
【参考文献】：
期刊论文
[1]无人驾驶汽车共享调度方法研究[J]. 崔洪军,李雨生,朱敏清,李霞,宋长柏. 公路交通科技. 2019(12)
[2]未来城市自动驾驶共享汽车规模研究：以上海为例[J]. 姚晓锐,王冠,杨超. 交通运输系统工程与信息. 2019(06)
[3]基于调度池的共享单车调度研究[J]. 蒋塬锐,贾顺平,李军. 交通信息与安全. 2019(05)
[4]基于遗传算法的定制公交多停车场多车线路优化[J]. 王超,马昌喜. 交通信息与安全. 2019(03)
[5]自动驾驶条件下共享车辆车队规模[J]. 王冠,杨超,张英杰,陈海林. 综合运输. 2019(02)
[6]无人驾驶汽车路径跟踪控制方法拟人程度研究[J]. 郭应时,蒋拯民,白艳,唐杰帧. 中国公路学报. 2018(08)
硕士论文
[1]基于车联网环境的共享自动驾驶汽车调度研究[D]. 王睿.大连理工大学 2019
[2]基于匹配理论的共享车辆网络稳定最优车辆调度策略[D]. 钟宜轩.哈尔滨工业大学 2019
本文编号：3099263
本文链接：https://www.wllwen.com/kejilunwen/jiaotonggongchenglunwen/3099263.html
