基于匹配理论的共享车辆网络稳定最优车辆调度策略

发布时间：2020-08-07 20:41

【摘要】：出租车是城市地区最受欢迎的交通工具之一,因为它给乘客提供了很大的出行便利。但是出租车服务的不同获取方式都有较为严重的缺点,例如等待时间不确定、容易增添交通阻塞、只能在固定地点提供服务、预定方式需要较高的价格等。如今通过通过网络预约的共享车辆服务克服了传统出租车服务的诸多弊端,给乘客提供了更加便捷的出行服务,是一种很有前景并已经受到大众欢迎的交通服务模式。相比传统的出租车服务,该新型的出行服务模式以更便宜的价格和更好的便捷性受到人们的青睐。此外,这种出行服务模式可以减少能源消耗、环境污染和交通拥堵等问题。当前在共享车辆服务领域应用的各种车辆调度算法存在着很大的不足,这阻碍了该新型出行服务模式的进一步发展。当前各种车辆调度算法的不足主要包括:调度方案不稳定;计算量过大,无法及时响应乘客的请求;需要部署大量设备,部署和维护成本太大等。本文主要研究适用于共享车辆网络的无共乘和有共乘两种场景下的车辆调度算法。本文提出使用订单费来求得最优调度方案并保证方案稳定。为了求得合适的订单费,本文针对无共乘的车辆调度问题提出了一种类似于拍卖机制的新型分布式算法。分布式算法通过所有乘客不断地提高车辆接送他们的成本,每辆车随后选择收益最大的乘客发出服务请求,重复上诉步骤直到没有乘客被多于1辆车请求服务,最终得到最优的车辆调度方案。本文证明了该分布式算法的稳定性和最优性。仿真结果表明该分布式算法以较快的速度地收敛到稳定状态,并且只要参数设置合理,就能以极大的概率求得最大社会效益,或者得到社会效益和最优解相差很少。此外,本文对分布式算法进行拓展,并结合穷举法,设计出一种分布式共乘算法运用到有共乘的车辆调度问题。通过仿真,本文发现分布式共乘算法虽然不能求得最优车辆调度方案,但是相比于求最优解,分布式共乘算法可以大大加快求解速度,并且该算法求得的社会效益处于一个可以被接受的范围。对于无共乘和有共乘两种场景的车辆调度问题,本文设计的算法都易于实现,并且可以大大减轻中心服务器的工作量,从而提高了系统对乘客的请求的响应速度。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：O224;U492.22
【图文】：

哈尔滨工业大学工学硕士学位论文 重的边的集合，W 的元素w权重。边集合的一个子集，并且这说，二分图的一个匹配方案多被其中的一条边所连接，配方案。整二分图的一个例子。图 2集合的点用边连接起来，每-1 中粗边的集合是该二分图共顶点，并且它的边的权重1 3 41481 21 52

并且路径规划已经有比较好的解放在车辆调度问题上。一名乘客提供服务，这辆车将从回报与乘客的出发点到其目的地回报用mnr表示。类似地，所有组成一个 M ×N 的收入矩阵，该矩 =1... , =1...mnm M n NR，对于 R 的元素mnr有以下定义：=mn mnr β h， β 是与市场经济相关的收入因一样的。为了符合现实情况，本车和 3 名乘客的车辆调度场景的辆 2 接送乘客 1，车辆 3 接送乘客去他们的目的地。车辆和乘客之13h3

rs1 23车辆调度建模为有权完整二模一辆车在行驶过程中可以这种车辆调度场景中，车一送到他们对应的目的地的乘客。有共乘的车辆调车容量等）的前提下，安驶路线，使最终的调度方调度不仅要将乘客接上车车接送多名乘客的先后顺等限制。度问题建模时需要考虑以能有一个或者零个输出路

【相似文献】

相关期刊论文 前10条

1 闫智,郑锋;基于FPGA的动态分布式算法的研究与应用[J];天津商学院学报;2005年03期

2 张邦成;戴群亮;王占礼;刘晨;;基于FPGA动态分布式算法的研究与应用[J];长春工业大学学报(自然科学版);2005年04期

3 鲁汉榕;;分布式算法的性质和复杂性[J];计算机科学;1985年05期

4 袁永康;分布式算法机器人变形关键[J];国外科技动态;2004年10期

5 国静;李良荣;;串并分布式算法的研究及其实现[J];科技信息;2009年02期

6 向珏良;一个有效的图匹配并行分布式算法[J];上海工程技术大学学报;1995年04期

7 任维政,陈凌霄,梁菁;基于FPGA的动态分布式算法的研究与应用[J];电子器件;2005年01期

8 王彩芬，武继刚;有限资源最佳分配的分布式算法[J];西北师范大学学报(自然科学版);1994年01期

9 鲁汉榕;一个最优任务调度的分布式算法[J];重庆大学学报(自然科学版);1985年03期

10 张德富;孙钟秀;盛蓝;杨培根;徐希豪;;一组计算FFT的分布式算法[J];计算机应用与软件;1986年02期

相关会议论文 前2条

1 张薇;;新型分布式算法的自动化检测流水线的研究[A];2017智能电网信息化建设研讨会论文集[C];2017年

2 何永泰;;基于FPGA实现DFT的DA算法研究与改进[A];2007'中国仪器仪表与测控技术交流大会论文集（二）[C];2007年

相关博士学位论文 前10条

1 杨照辉;密集蜂窝网全局无线资源分配分布式算法研究[D];东南大学;2018年

2 邢浩;面向智能电网中能量管理的分布式算法研究[D];浙江大学;2017年

3 刘浩;无线自组织网络一致算法安全与隐私研究[D];浙江大学;2017年

4 朱迪;星载降水雷达超低副瓣脉冲压缩算法的研究与实现[D];中国科学院研究生院（空间科学与应用研究中心）;2008年

5 石立国;分布式卫星系统星间链路关键技术研究[D];中国科学院国家空间科学中心;2016年

6 潘存华;互干扰信道系统中的能效优化问题研究[D];东南大学;2015年

7 张敏;基于无线智能传感器Imote2的桥梁健康监测的分布式算法研究[D];汕头大学;2010年

8 刘莹;计算机网络中的多播路由算法[D];西安电子科技大学;2000年

9 徐昀;有向网络约束下的分布式资源优化分配研究[D];浙江大学;2017年

10 韩彦琰;移动容延/容断网络的路由机制和高效传输方法研究[D];武汉大学;2015年

相关硕士学位论文 前10条

1 钟宜轩;基于匹配理论的共享车辆网络稳定最优车辆调度策略[D];哈尔滨工业大学;2019年

2 韩冰;密度中心聚类的优化及分布式算法研究[D];东北大学;2015年

3 袁坤;多智能体网络一致性问题的分布式算法研究[D];中国科学技术大学;2014年

4 刘来;基于概率模型检测的分布式算法验证和分析[D];华侨大学;2014年

5 姜泽;基于移动云计算的协同数据分流联合信道诜择研究[D];南京邮电大学;2017年

6 王逸恺;空间信道博弈的分布式算法[D];南京大学;2014年

7 桂秀平;[D];南京师范大学;2017年

8 谢于飞;基于智能的分布式算法的设计与实现[D];南京邮电大学;2012年

9 胡存龙;数据管理平台—内容识别模块的设计与实现[D];北京交通大学;2015年

10 程钰涵;基于分布式算法的离散余弦变换的硬件架构[D];天津师范大学;2008年

本文编号：2784502