基于整数规划的共享汽车调度研究

发表时间:2021/7/5   来源:《中国建设信息化》2021年5期   作者:于盼月1,张辰2,杨泽众3
[导读] 本文旨在对城市共享汽车使用分布状况及调度供需问题进行分析
        于盼月1,张辰2,杨泽众3
        1、华北理工大学,理学院,唐山063000 ;2、华北理工大学,理学院,唐山063000 ;
3、华北理工大学,人工智能学院,唐山063000
        摘       要
        本文旨在对城市共享汽车使用分布状况及调度供需问题进行分析,利用matlab软件对共享汽车行业现状进行多维分析,并建立图与网络模型,从而对共享汽车站点的位置范围、停靠车辆数量、停留时间以及供需是否平衡的问题进行有效的描述、定位和评价。针对共享汽车站点出现的成本控制环节困难及供需不平衡问题,提出人工调度策略,以实现汽车使用最大化。
关键词   整数规划;共享汽车;聚类分析;马尔科夫链
Abstract
        The purpose of this paper is to analyze the distribution of urban shared car usage and dispatch supply and demand issues, use drawing software to conduct multi-dimensional analysis of the current situation of the shared car industry, and establish a map and network model to determine the location range, number of parked vehicles, stay time and time of shared car sites. Effectively evaluate, describe and locate the issue of whether supply and demand are balanced. Aiming at the difficulty in cost control links and imbalance between supply and demand in car-sharing sites, a manual scheduling strategy is proposed to maximize the use of cars.

一、引言
        共享车辆为社会带来便利的同时也为管理者带来了极大的挑战,车辆如何在空间上避免分布不平衡以及因此带来的车辆调运成为管理者面临的挑战之一。由于用户取车、还车地点的灵活性,区域之间用车需求的不平衡性,以及用户出行活动本身所具有的定向性和周期性,难免出现某一区域停放的共享车辆过多(甚至因车辆过多造成新的社会问题),而另一区域共享车辆不足以满足用户需求的现象。因此,需要尽可能避免车辆在空间上分布不平衡的现象,在必要时对车辆进行调运,而且这种过程具有动态性和不确定性。
        
二、符号说明
        本文所述P代表车辆移动的转移概率;X表示事件;N代表共享汽车站点集合;代表任意站点间距;k为加权因子;N+为共享汽车调出点集合;N—为共享汽车调入点集合;为站点i所需共享汽车数量下限;为站点i所需共享汽车数量下限;为从站点i到j每辆共享汽车的调度成本;为调度之前汽车数量。
三、模型的建立与求解
3.1模型思路分析
        根据已有的研究成果,本文针对某城市在2018-2019年度的已知数据,有关车辆调度问题,主要针对以下几点展开讨论:用户需求分析、车辆流通率的计算、车辆的调度成本,并通过运筹学的优化思想,得到最优车辆停放点,并进行实际的城市中车辆流通分析。
3.2划分停车站点所在区域
        利用MATLAB在以纬度为横坐标、经度为纵坐标的坐标系中描绘出车辆数目的散点图,观察图表,发现有个别站点距离较远较分散,为方便模型的建立,摒弃个别坐标点,截取所需要的部分。
        该城市汽车站点数目比较多,其位置分布呈现出明显的差异性,有些位置停车站点较多,有些位置停车站点则十分少;另外车辆分布也呈现出明显的差异,有少部分停车站点在同一时间内停放了八九辆车,也有部分站点在某些时间出现了无停放车辆的情况。
        为方便分析,我们将站点车辆数目分别为2、3、4的站点位置筛选出使用绘图软件以散点图的形式表示。
        
       
        以汽车数量分别为2、3、4的站点为例,可根据图中站点集中的区域设置停车站点。
        为更直观的观测到该城市共享汽车站点疏密程度,对各个站点所需车辆的多少进行明确的分类,采用聚类分析算法,所研究的站点之间存在程度不同的相似性。于是根据已有的多个车辆定位观测指标,具体找出一些能够度量车辆数目或指标之间相似程度的统计量,以这些统计量作为划分类型的依据,把一些调入车辆和调出车辆相近相似的站点品聚合为一类,把另外一些彼此之间相似程度较大的站点聚合为另一类......关系密切的聚合到一个小的分类单位,关系疏远的聚合到一个大的分类单位,直到把所有的共享汽车站点都聚合完毕,把不同的类型一一划分出来,形成一个由小到大的关于汽车站点投放车辆数目多少的系统。最后再把整个分类系统使用MATLAB绘图工具画成一张分群图,用它将20个停车站点之间的亲疏关系表示出来。
        由此,将停车站点区域按等面积原则划分可分为20个面积相同的、囊括不同停车站点数的、范围较大的区域,称之为汽车站点,分别用P1,P2,…,P20表示。具体划分区间如下:
        
        
        
        
        
        
        
        
        
        
        
      
3.3 确定调入调出点
        由于每个站点在不同时段对汽车需求量不同,要确定某一时段初期对应的汽车调出点和汽车调入点,需要根据该时段各个站点的需求量分布以及站点的车辆停放情况进行综合分析.对于某一个站点假设根据历史资料得到其需求量分布区间为某一时段初期,该站点的汽车停放数量为s,则可以按照下列规则,确定该站点的类型。以MATLAB中k-means聚类算法为基础,做出聚类分析图,得到共有20个经纬度确定的停车点(同时作为共享汽车输出点),同时针对于某一个站点,设其需求量分布区间为,在某一时间段初期,该站点的汽车停放数量为,我们此时可以得到:

        以某站点为例,计算出2018-12-17日中八点半到十点半13站点汽车需求量为9(单位:辆);以同样的方法计算出从2018-12-11到2019-1-10中八点半到十点半13站点汽车需求量。从而首先将各站点12个月的汽车使用量数据进行统计,分析其服从的概率分布规律,进一步计算出置信度为0.9的置信区间,作为该站点的汽车需求区间.以13站点为例,进一步根据各个站点每个时段初期的汽车存放量,确定汽车调出点和汽车调入点集合,利用进行数据预处理,以2018-12-11到2019-1-10中八点半到十点半的数据为例,得到20个汽车站点中供需不平衡的站点,其中“+”表示调出点,“-”表示调入点,“0”表示平衡点。
     
        根据求解结果,汽车公司应该在6个供需不平衡的站点之间通过人工方式调度汽车数辆,调度之后所有站点将达到供需平衡。图2描述了最优调度方案对应的调度线路和每条线路上的调度量;
        从图2可以看出,最优方案对应的调度线路均为就近站点之间的连线 。
四、模型评价与展望
        本论文将共享汽车的调度问题转换成为整数规划求最优解问题,利用图论中的运筹学知识,附加matlab对散点图进行处理——K-means聚类分析得出最优调度点,从而解决了调度难、车辆散、分布广的难题,并利用隐马尔科夫进行预测,预测结果说明本文解决方案较好,具有使用价值。
参考文献
[1]李珍萍,刘璐, 王晨.共享单车调度优化问题研究[J].数学的实践与认识,2021,51(06):13-20.
[2]前瞻产业研究院.2014-2018年中国共享经济融资与事件数量[ C/OL]https://f.qianzhan.com.html.2019-08-12 (14)[2021-04-10].
[3]Alvina G H Kek, Ruey Long Cheu, Qiang Meng, et al.A decision support system for vehic le reloc ation operations in carsharing system[J]. Transportation Research Part E 45, 2009:149-158
[4]宋婷颖,盛建平.基于马尔科夫链模型与遗传算法的共享汽车调度方法研究[J].工业控制计算机,2019,32(05):127-128+131.
投稿 打印文章 转寄朋友 留言编辑 收藏文章
  期刊推荐
1/1
转寄给朋友
朋友的昵称:
朋友的邮件地址:
您的昵称:
您的邮件地址:
邮件主题:
推荐理由:

写信给编辑
标题:
内容:
您的昵称:
您的邮件地址: