【《某大学共享单车调度方案的优化设计实现案例》7000字】

目录TOC\o"1-3"\h\u2483 1324321.1全共享单车停车点遍历路径计算 1244901.1.1算法介绍 1263291.1.2参数介绍 2218041.1.3实现过程 2143401.2共享单车现有车存量预测和调度量计算 765841.3具体调度数量方案计算 10232541.3.1模型介绍 1056291.3.2最小元素法确定初始调度方案 1154931.3.3闭回路法优化调度方案 13161131.4方案比选 131.1全共享单车停车点遍历路径计算1.1.1算法介绍经对比最终采用蚁群算法来进行遍历路径计算。蚁群算法（ACO,AntColonyOptimization）最早是1991年由MarcoDorigo等人在研究新的算法的过程中，发现寻找食品的蚂蚁会留下一种生物信息素来交换路径信息，通过种群个体间的信息迭代产生正向循环，使种群的觅食行为可以高效完成。蚁群算法起源于大自然中蚁群寻觅食品的寻找路径原理。由昆虫学家的调查，发现自然环境下的视觉极度退化的蚂蚁可以在不存在所有导航的现状中，找出从出发点到找到食品的最短路程，除此之外可以在逐渐改变环境中的要素的条件下，更新这些路程，完成新的探索。蚁群在搜索食品的过程中，可以在其经过的道路上释放一种信息素，同时使蚁群中的所有个体都可以共享这一信息。当部分道路上经过的个体逐渐变多时，信息素集中就会逐渐明显，选择某个道路的个体数量也就越高，这回使得这条道路上的信息素更加集中，选择这条路径的个体会进一步占据族群中的更大份额，周而复始。蚁群的这种探索方法被称作自催化行为。对于种群中的每一个个体，它不需要独立探索寻找最佳路径，只是根据种群的意志进行选择；就整个蚂蚁种群的层面角度来看，它们确实完成了客观上探索最佳方案的任务，这就是种群智慧。蚁群算法是参考蚁群搜寻食品的自发自优化过程而衍生出的的仿生算法，由其在自然界中的实用效果，蚁群算法可以用来解决最佳路径优化的问题，并真的在旅行商问题（TSP，寻找周游所有目的地的最佳方案的问题）上应用广泛并且效果良好。当前，这种算法也已逐步应用到许多不同的领域的同类型问题上。而对校园内所有停车点进行遍历恰好可以看作一个车辆调度方案领域的TSP类问题。1.1.2参数介绍编制蚁群算法需要的参数包括：种群数量、信息素因子、启发函数因子、信息素挥发因子、信息素常数、最大迭代次数。（1）种群数量设M表示停车点数量，m表示蚂蚁数量。m的数量是一个需要考量的方面，当m过大时，同时经过所有道路的个体数量偏高，而信息素的增加则会失去特征，不利于辨别各条道路上的残留信息素；m过小时，有可能出现部分道路一直没有个体经过的情况，会导致考量道路网残缺，最终得到的遍历路径可能只是部分道路上的最佳方案。（2）信息素因子信息素因子的意义是个体参考其他个体在道路上经过时释放的信息素选择道路时认定的重要性。其值过大，个体把已经走过的道路作为选择对象的概率大，对完整路网的探索率低；取值过小，将会趋近于贪婪算法，仅会在局部路网产生最优方案。经实验研究发现[19]，信息素因子在[1,2]区间的场合，运行效果较好。（3）启发函数因子启发函数因子反映的是路径探索过程中个体主观意愿的重要性。取较大值时，达到最优方案的迭代次数会显著降低，但获得的方案很大可能不是在完整路网上的最佳方案；取较小值时，会加大探索行为的随机性，达到最优方案的收敛次数将会超出最大迭代次数。实验研究发现[19]，当启发函数因子为[4,6]时，算法运行效果较好。（4）信息素挥发因子信息素挥发因子代表了当前道路上存在的信息素随着迭代进行衰减的速度，这一因子的取值对算法的总体效果会产生影响。多次尝试发现，当其取值为0.1时，算法运行效率较好。（5）信息素常数这一参数代表了信息素强度，表示个体完成一次迭代时在道路上的信息素释放量，其作用是为了积极利用全局信息反馈量，使算法以合适的演变速度在正反馈影响机制下探索整个道路系统上的最佳方案。实验发现[19]，越小取值会使算法具有越低的收敛性,但同时由于反馈减弱使搜索空间增大，算法获得仅在部分道路上的最优方案的可能性变低。（6）最大迭代次数最大迭代次数值过小，会使算法输出的最终的方案不符合完整道路网上最佳方案的预期；取值过大则会产生大量无用计算，加大计算时间消耗。可以先取一定最大迭代次数，再根据运行效果调整这一参数。1.1.3实现过程（1）参数确定校园内停车点数量为26，因此为保证收敛效果，可以先取种群数量为停车点数的1.5倍，即取39。参考文献[19]确定信息素因子α可取1，启发函数因子β可取5；多次场数尝试后，信息素挥发因子ρ取0.1；信息素常数Q可取100，最大迭代次数取200。如表4-1所示。表4SEQ表\*ARABIC\s11蚁群算法参数参数名及符号值信息素因子，α1启发函数因子，β5信息素挥发因子，ρ0.1信息素常数Q100种群数量m39最大迭代次数200（2）变量初始化由于研究区域仅限S大学（威海）校园内部，各停车点坐标用相对表示展示出各停车点相对位置即可。从使用TransCAD得到的道路网信息表中可以得到当前校园内所有停车点在所选坐标系下的坐标（xi，yi）如表4-2所示。表42校园内各停车点坐标编号名称xiyi1图书馆106426135147875472N楼西106424023147869033海洋学院106424676147820084研究院后106426937147770075研究院北106424768147778916研究院南106424653147772787十公寓与十一公寓106422963147853158十二公寓106428001147839669二公寓1064242261478272710四公寓1064247171478353211三公寓1064244401478297312G楼1064241251478093713M楼1064235561478116314学苑餐厅1064253221478280615六公寓1064251501478391816一公寓1064246111478251017五公寓1064246761478200818大学生服务中心1064238911478199819学子餐厅1064249521478522720九公寓1064241391478482021八公寓1064237251478423422七公寓1064232791478363623H楼1064250201478054624留学生餐厅1064269901477974825体育场1064222111478041726N楼东10642544414786267此外，现在使用的蚁群算法普遍采用如下公式计算各个目标点之间的距离： (41)式中Dij——停车点i,j之间距离；xi，xj——停车点i,j横坐标；yi，yj——停车点i,j纵坐标。连接各个停车点的道路存在绕路现象，若以上面公式计算各停车点之间的距离会出现较大误差，因此本研究采用连接各停车点之间的道路实际距离代替该公式来表示各停车点之间的距离，依旧可以直接使用TransCAD直接获取，如图4-1所示。图4-1距离矩阵（3）构造禁忌表对每个个体的搜索过程中，不允许个体多次到达同一个停车点，因为这会导致遍历时间的浪费并且不符合实际需求。记待访问的停车点集合为J。为每一个个体设置一个禁忌表，将其经过的停车点加入表中。禁忌表中第一个值代表个体在访问开始的时候所处的停车点，当禁忌表中包含了所有的停车点时，认为该次搜索结束。（4）轮盘赌选择下一个停车点个体选择下一个目标停车点的方式不一，本研究选择下一个目标的方法是经典的轮盘赌方法。定义启发因子表示路径(i,j)上的启发信息，表示蚂蚁从停车点i转移到停车点j的期望程度。计算方式为： (42)式中——启发信息因子；——停车点i至停车点j之间的距离。个体选择每个停车点的概率采用当前路径上信息素浓度与两个停车点之间的启发信息因子通过启发因子赋权后的积来计算： (43)式中——路径几率;——信息素因子;——启发函数因子;——信息素浓度;——停车点i到停车点j之间的启发信息因子;J——在停车点i处所有可访问的城市集合。通过上式可知，个体选择某一条路径的概率与道路(i,j)信息素含量成正比，而道路(i,j)之间的距离越大，启发信息因子就越小，则个体把该路径标记为下一步方向的概率就越小，个体选择路径(i,j)的概率与上述两个因素都有关系。由上式得到选择各个停车点为下一步目标的概率，再将这些概率除以所有概率之和，得到选择下一步停车点的实际概率。一般的蚁群算法会按照概率排序，认为个体会选择概率最大的线路前进。但由于蚁群算法是基于仿生学产生的算法，需要保证下一步的所有可能停车点都占有一定被选择的可能。如若不然，单纯依靠概率排序决定下一步行动，就是普通的贪心算法。因此用轮盘赌选择的方法来决定下一步行动。首先按照顺序把各个停车点实际概率相加，直到这一相加值大于一个随机生成的概率，这时输出最后一个用于相加的概率对应点停车点编号，设置为下一个需要访问的停车点。用这种方式依次完成遍历路线的选择，采用图4-2代码完成轮盘赌选择：图4-2轮盘赌选择代码信息素更新信息素的更新是蚁群算法的一个重要的特征步骤。每一次种群的路径选择完成后，环境中的信息素都会发生改变。信息素的含量将会随着搜索进行而逐渐增加。信息素浓度更新主要会因为以下因素而改变：蚁群的路径选择导致网络中的信息素增量；系统中信息素的挥发，即实际的道路上信息素浓度会随着探索任务的进行而有减少一定的比例。假设在(t,t+n)时刻所有个体完成一次路径选择，则在t+n时刻停车点i,j之间的信息素更新过程可以表示为： (44) (45) (46)式中(t+n)——在t+n时刻停车点i,j之间的信息素含量；——信息素挥发因子；(n)——在n时刻停车点i,j之间的信息素含量；——信息素浓度的增加量；——第k个个体在本次遍历中释放在道路i,j之间的信息素；Q——信息素常数；Lk——蚂蚁k在周游中经过的路径长度。使用代码如图4-3：图4-3信息素浓度更新代码通过更新系统上的信息素浓度，较优的路径解会在达到一定的迭代次数时出现。当最大迭代次数完成的时候，停止迭代，可以认为此时的最佳路径即为全局最优路径。（6）计算距离本研究以总路程最短为最佳路径的判断标准，记录每次迭代过程中出现的最佳路线。当迭代次数达到最大迭代次数时，将每次调度路线的经过路程依次相加求和，计算每次迭代中的最佳遍历路线的总路程，再把所有的遍历路线进行比较取最小值，并调取该次路线的访问表，在坐标系中将这26个停车点根据其坐标（xi，yi）中画出相对应的位置，再根据访问表依次连接停车点，即可得到最佳遍历路径，如图4-4所示。图4-4遍历路径遍历路径为：研究院北→研究院南→研究院后→体育场→H楼→学苑餐厅→六公寓→四公寓→三公寓→一公寓→二公寓→五公寓→大学生服务中心→G楼→M楼→七公寓→八公寓→九公寓→十公寓与十一公寓→学子餐厅→N楼东→N楼西→图书馆→十二公寓→留学生餐厅→海洋学院→研究院北，路径长度7246m。该算法在70次左右达到最小值收敛，收敛速度较快。1.2共享单车现有车存量预测和调度量计算1.2.1算法介绍现在已经获取数据为连续的一周内校园内各停车点的存车量。利用这些数据预测将来某一需要进行调度的时刻各停车点的车存量。本研究中采用BP神经网路学习现有数据，并利用其建立网络模型，对某一个拟进行调度的时刻的各停车点的车存量进行预测。BP神经网络在业界被专家们称为反向传播神经网络，具有非常不错的市场发展前景和较强的实用性跟普适性[20]。BP神经网络模型预测分析可分两步来进行，第一步首先输入样本训练集，将调查数据调入到模拟环境中，通过样本数据集训练神经网络，使样本中的输入数据与输出数据通过隐含层建立非线性对应关系。第二步就可以使用训练后的网络来进行预测，训练后的网络基于训练集产生记忆，会根据这一万能模型进行预测，并分析预测值的合理性来判断网络是否训练成功。本研究采用MATLABR2018a软件进行BP神经网络的实现。1.2.2参数确定在MATLAB系列软件中自带完整的BP神经网络的工具包。通过其说明文档，可知进行BP神经网络进行预测需要包括以下流程：输入，参数确定，训练函数，建立神经网络并学习现有数据，输出预测值。在已经确定输入的情况下我们需要确定网络中的参数。一般BP神经网络的参数包括最大训练次数、训练要求精度、学习率、最大失败次数、最小梯度要求、最大训练时间、动量因子。常见的训练函数包括：梯度下降法，带有动量项的梯度下降法，自适应lr梯度下降法，自适应lr动量梯度下降法，弹性梯度下降法，Fletcher-Reeves共轭梯度法，Ploak-Ribiere共轭梯度法，Powell-Beale共轭梯度法，量化共轭梯度法，拟牛顿算法，一步正割算法等。本研究使用的训练参数如表4-3所示。表43BP神经网络参数参数名及符号值最大训练次数，epochs10000学习率，lr0.05动量因子，mc0.9训练要求精度，goal0.01训练函数带有动量项的梯度下降法1.2.3实现过程在MATLABR2018a中使用图4-5代码构建BP神经网络：图4-5BP神经网络代码运行该程序，获得调度车辆到达时各停车点现存单车数如表4-4所示。表44校园内停车点存放量目标时刻预测值编号预测值编号预测值图书馆9学苑餐厅12N楼西2六公寓4海洋学院42一公寓6研究院后19五公寓1研究院北54大学生服务中心11研究院南81学子餐厅18十公寓与十一公寓5九公寓0十二公寓0八公寓4二公寓6七公寓5四公寓3H楼115三公寓5留学生餐厅22G楼38体育场20M楼45N楼东12表中预测值合计为539辆，与校园内总投放量基本相符，且各停车点预测值均在调查实际数据的范围内，故可认为该预测数据可能在实际调度中出现，即可作为预测值使用。1.2.4调度量计算根据上文获得了即将进行调度时各停车点车存量的预测值和最佳车存量的预测值，对各个停车点的两值作差即可得到各个停车点的调度量如表4-5、4-6所示。表45校园内各调入点调度量编号调入值编号调入值图书馆11六公寓14N楼西8一公寓12研究院后1五公寓17十公寓与十一公寓13大学生服务中心4十二公寓12学子餐厅2二公寓12九公寓10四公寓15八公寓14三公寓13七公寓13学苑餐厅8N楼东8表46校园内各调出点调度量编号调出值编号调出值海洋学院12M楼15研究院北24H楼75研究院南46留学生餐厅7G楼8根据方案一，含有调度量的调度方案如下（其中-为调出，+为调入）：研究院北（-24）→研究院南（-46）→研究院后（+1）→体育场（0）→H楼（-75）→学苑餐厅（+8）→六公寓（+14）→四公寓（+15）→三公寓（+13）→一公寓（+12）→二公寓（+12）→五公寓（+17）→大学生服务中心（+4）→G楼（-8）→M楼（-15）→七公寓（+13）→八公寓（+14）→九公寓（+10）→十公寓与十一公寓（+13）→学子餐厅（+2）→N楼东（+8）→N楼西（+8）→图书馆（+11）→十二公寓（+12）→留学生餐厅（-7）→海洋学院（-12）→研究院北。若以总运距： (47)式中——遍历路径上下一步的距离；——调度车辆运载量增量。来评价调度方案，计算得到总运距为322470。1.3具体调度数量方案计算以上本研究已经获取了拟进行调度时各停车点的需求调度量，接下来本研究将具体计算共享单车调度方案。1.3.1模型介绍本研究认为，单车调度可以看作是一个运输问题。对于运输问题的经典描述是[21]：设有产量分别是，，……，的m个工厂，，……，；又有销量分别是，，……，的n个经销地，，……，。假设从工厂向经销地运输单位产品的运输价格是，寻找最优的方案使产品从生产地点运输到销售地点的运输成本最小，运输量为。为了描述本研究中的单车调度问题，本研究采用以下描述上的调整。将有车辆调出的停车点视为产品工厂，有车辆调入的停车点视为经销地，调入站点和调出站点之间的路网上的实际距离作为单位运输成本，寻找可以使调度车辆过程中的运输总运价最小的调度方案。假设调出单车数量总是等于调入单车数量，则有评价函数： (48)式中m——调出站点数；n——调入站点数；——由调出站点Si至调入站点Tj的距离；——由调出站点Si运至调入站点Tj的调度量。因此，校园内单车的调度问题可以用如下的数学模型描述： (49)式中m——调出站点数；n——调入站点数；——由调出站点Si运至调入站点Tj的距离；——由调出站点Si运至调入站点Tj的调度量。参考求解运输问题的算法，本研究采用两阶段调度求解算法。由最小元素法获取初始可行解；然后应用闭回路法改良初始解达到最优方案。1.3.2最小元素法确定初始调度方案最小元素法是运筹学中求解运输问题中寻找初始运输方案的常用方法。最小元素法以近距离调度为原则，即调度由成本表中成本最低的位置开始进行，逐个解决调度起讫点，直到满足所有调入调出需求，获得一组初始可行解。算法步骤如下：搜索阻抗矩阵中的最小值，确定调度关系，满足其调度量。去除已经完成调度的行列，本算法中以非常大的成本代替原有成本来表示该调度已经完成。重复以上步骤，直到所有调度需求被满足，得到初始调度方案。在MATLABR2018a中使用图4-6、图4-7代码实现最小元素法：图4-6最小元素法代码图4-7最小元素法代码（续）运行代码得到初始可行解如图4-8所示：图4-8最小