| 联系我们 |
 |
合作经济与科技杂志社
地址：石家庄市建设南大街21号
邮编：050011
电话：0311-86049879 |
|
|
| 管理/制度 |
| 基于市场需求的共享单车优化调度研究 |
| 第632期 作者：□文/赵 婷 廖成林 时间：2020/5/1 16:24:23 浏览：518次 |
［提要］ 共享单车的出现切实解决了“最后一公里”的难题，因此建立优化调度模型以提升共享单车的服务效率，保证共享单车的最大使用率具有重要意义。本文以用户需求为前提，以共享单车调度产生的费用以及未被调度产生的损失的最小为目标函数建立优化调度模型。运用改进的遗传算法对包含25个共享单车需求站点的算例进行求解，分析计算后得出该区域共享单车的优化调度方案和最小调度成本，表明该模型在共享单车调度问题上具有一定的可行性。
关键词：共享单车；优化调度；遗传算法；市场需求
中图分类号：F252 文献标识码：A
收录日期：2020年2月25日
引言
共享单车作为共享经济时代下最典型的产物，并作为中国新世纪“新四大发明”之一走向世界，它切实解决了“最后一公里”的问题，为人们的出行提供了很大的便利。
相比于传统的公共自行车，无桩停放，即停即用是共享单车最大的特点，因此各个区域共享单车的数量是一个动态平衡的状态，但是受到用车需求的潮汐变化过程，在高校、居民楼以及写字楼等区域的位置共享单车并不能保证自平衡状态，因此根据各个区域的潮汐用车需求对共享单车进行周期化的优化调度，对保证共享单车最大的使用限度，保证最大化利益具有重要的作用。
共享单车的调度可以看作为调度车辆的路径问题（Vehicle Routing Problem，VRP），而共享单车的调度又可以分为动态调度和静态调度。汪慎文等人考虑了共享单车的初始数量和共享单车数量的变化率，建立了共享单车的动态调度模型。赵敬洋等人运用分时段调度思路把自行车系统的调度时间划分成多个连续的调度周期，从而将动态调度问题静态化。Lin J等人研究单车调度时建立了一个非线性的整数规划模型。ContardoC则以调度站点对自行车的需求最小为目标函数建立了优化调度模型，用于对各个调度站点的自行车辆进行调配。ChemlaD在研究自行车调度时将其简化为单配送车辆的调度，并以总调度距离最小为目标函数建立模型，对实现共享单车的复杂调度问题实用性较低。杨珈惠等人研究共享单车的调度时可以允许调度车辆的局部重复路径，当前研究主要以最少运输费用为调度模型的目标函数，Benchimol M等人假设调度恰好满足所有站点的需求，并以最小的调度费用为目标函数建立静态调度模型进行求解。目前对于自行车的优化调度模型已经有相当一部分成果，但是少有同时考虑当调度车辆过多或者过少带来的损失费用。因此，本文提出了一种基于用户需要的共享单车调度模型，该模型以共享单车调度产生的费用以及未被使用产生的损失费用最小值为目标函数建立优化调度模型，能够很好地满足目前共享单车调度方案的需求。
一、共享单车需求模型
为了得到某区域共享单车的投放量，需要根据该区域对共享单车的需求进行分析，本文基于该地区的人口数量及人口结构为基础，通过分析不同层次人口对于车辆的使用频次，从而得到该年龄层的用车率。根据共享单车的需要，对某局部区域的人口结构和职业可以做划分，如表1所示。（表1）
根据表1中年龄和职业划分的五种结构，假定在某个调度区域中第i个年龄段的人数为Ri，该年龄层单日使用共享单车的概率为ui，则可以得到该区域共享单车的需求量为：
X＝■Riui （1）
针对某个包含j个调度区域的地区，则该地区共享单车的需求量可以表示为：
X＝■Xj＝■■Rijui （2）
其中，Cj表示第j个区域中共享单车的需求量；Rij表示第j个调度区域内第i个年龄段人口的数量。
二、共享单车优化调度模型
共享单车的调度受其运营方式的影响，使得其调度过程是一个复杂的动态过程。通常，在对共享单车进行调度分析时，我们把它的调度过程简化成静态过程。本文在建立优化调度模型时，考虑调度的目标函数为如下两个部分：（1）考虑调度过程中由于调度运输产生的费用；（2）某个待调度区域共享单车过少或者过剩时由于未被使用带来相应的损失费用。假设待调度区域只包含一个调度中心（用坐标（0，0）表示调度中心），从该调度中心出发，m辆调度车辆对n个调度区域进行调度时，则调度费用可以表示为式（3）所示：
D1＝f1■■■kidijxijm （3）
其中，f1表示1km的运输成本（单位：元/km）；dij表示从调度点i到调度点j的距离（单位：km）；
xijm＝1，车辆m从i到j0，车辆m未从i到j
ki=1，站点i被服务0，站点i未被服务
同时，需要保证从调度中心出发的调度车辆，经过调度之后最终需要回到调度中心，且进入某调度站点的车辆调度完成后，必须从该调度站点出发进入下一个调度站点或者直接回到调度中心，因此可以表示为：
■x■=1■x■=1■x■=■x■ （4）
为了简化调度问题，设定每个共享单车调度站点的调度任务最多只由一辆车负责，如果被调度只允许被调度一次，则有：
■y■=1y■=1，车辆m未服务站点i0，车辆m服务站点i （5）
其中，yim表示，第i个调度站点是否有第m辆车完成。
此外，当某个区域的共享单车超过其实际需求时，会导致该地区共享单车空置浪费；当某区域数量较少时，则无法满足该区域用户的需求时，又会导致损失。因此，考虑当第i个站点未被调度时，由于未调度所产生的损失费用可以表示为：
D2＝f2■?着i（ki-1） （6）
其中，f2表示一辆单车每天产生的平均收益（单位：元）。
当某个站点被调度之后，但仍未完全达到调度站点的需求，假设调度过程中对第i个站调度单车数量为?准i，则也会产生一部分损失费用，可以表示为：
D3＝f2■?着i-?准iki （7）
其中，?着i表示第i个调度站点自行车的需求量，当?着i>0时表示该站点需要车辆，当?着i>0时表示该站点车辆过多，需要调走；?准i表示第i个站点的实际调度量。
根据上述分析，本文针对共享单车的优化调度模型提出如下假设：
（1）假设该区域共享单车总数保持不变；
（2）假设共享单车的调度为静态调度，每天的调度均在夜间进行；
（3）假设在一个小范围内的共享单车需求量可以通过一个调度站点满足；
（4）调度过程中人力成本与车辆运输成本统一结算为运输成本；
（5）忽略由于共享单车丢失和破损带来的损失。
基于上述假设，本文以共享单车调度产生的成本费用与未被调度时产生的损失费用的和的最小值为目标函数，建立共享单车优化调度模型：
minD=f1■■■kidijx■+f2■?着i（ki-1）+f2■?着i-?准iki
S.t.■x■=1■x■=1■y■=1■x■=■x■0≤■?着iy■≤?准0≤■■■（wijm+?着j）≤?准xijm＝1，车辆m从i到j0，车辆m未从i到jki=1，站点i被服务0，站点i未被服务 （8）
通过建立的上述模型，我们可以得到某地区单个调度中心情况下的共享单车优化调度策略，并保证最优的成本和最低的损失费用。
三、算例分析
（一）初始化调度信息。本文首先在某区域中的二维坐标随机生成共享单车用户的位置信息以及对应的需求数量，并将该区域均衡的分为25个调度区域，根据用户的需求信息以及调度区域的位置信息，并运用重心法求出每个调度区域的调度站点，保证每次调度车辆将共享单车调度在该位置可以满足调度需求。最后，初始化各个调度站点的需求数量如表2所示。（表2）
其中，表2中需求量的正负表示了该调度站点是否需要调度共享单车，正值表示该站点需求为正值，需要由其他站点调配过来，而负值则表示需要由该点向其他地方调配。
（二）调度参数设置
1、调度站点的距离。在已知各个调度站点的坐标的前提下，为了简化问题，本文选取两个调度站点的欧式距离作为两个站点之间的调度距离。
2、共享单车的调度和损失费用。共享单车的调度费用作为本文调度模型的目标函数，共享单车的运输费用和损失费用都将极大影响调度方案和策略，针对现有共享单车的收费标准加上用车情况，本文对调度费用作如下假设：针对该区域，共享单车的调度运输费用为12元/km，而当共享单车不满足用户需求或者是超过用户需求，所带来的损失费用为8元/辆·天。
3、调度车辆信息。本文假定上述划分的25个调度站点（分别命名为1-26号），均由该区域的调度中心负责调度，该调度中心包含三辆调度车，每辆车最大装载量为40辆共享单车。
（三）调度方案计算。目前，运用遗传算法求解物流配送车辆路径问题（VRP）问题的研究具有较多成果，运用遗传算法对该优化的调度模型进行求解，求解步骤如下：
1、参数初始化：初始化样本个数N，最大迭代次数n，交叉概率pi和变异概率pm。
2、种群初始化及编码：本文将调度站点随机连接遍历的路径作为初始化种群，并通过自然编码的方式对该初始化种群进去编码为E（1，2，3，…，m）。
3、适应度函数：计算本次迭代种群的最优适应值。
4、迭代：判断是否到达最大迭代次数n，如果到达则退出循环并输出最优的适应值，否则进入（5）。
5、交叉和变异：选择（4）中个体适应度值小的作为优良的染色体，并按照设置的交叉变异概率进行交叉变异操作，产生新的种群并转入（3）继续计算适应值。
6、迭代终止：到达最大迭代次数，选择最小的适应值作为最优的调度费用，并输出对应的调度路线。
设定遗传算法迭代的参数如下：以模型的目标函数作为迭代的适应度函数，初始化样本为2，000个，交叉概率设为0.9，变异概率设为0.12，终止迭代次数为600代。
本文分别计算派出1、2、3辆车的情况进行调度方案计算，并且保证所派出的调度车辆都需要有调度任务，通过MATLAB编程进行计算，得到三种调度情况的最优调度路线和最小的调度费用如表3所示。（表3）
从表3可以看出，1辆车调度时，站点7、12、19、22、24未被调度，而其他站点被调度且满足站点的车辆需求，最优的调度费用约为551.19元；当我们使用2辆调度时，其费用为477.14元，其中4、7、10、12、19、21、26这7个站点未被调度，当使用3辆车进行调度且保证都有调度任务时，其调度费用反而增加，最优调度费用为600.78元。分析发现，相比于1辆车和3辆车，派出2辆车时其服务的站点较少，但是节省了调度运输费用，保证了综合成本最小。
四、结论
本文结合共享单车无桩停放的特点，深入分析了影响共享单车调度的因素，运用旅行商问题的相关研究结果，根据当前区域对共享单车的需求情况，建立了以调度运输费用和共享单车未被调度所造成的损失最小为目标函数的优化调度模型。通过改进的遗传算法对该模型进行求解，对包含25个调度站点的区域进行计算，得到在不同数量调度车辆的情况下的调度方案和调度费用，得到了最优调度方案。通过模型可以得出，本文提出的考虑共享单车损失费用的调度模型完善了传统调度模型的不足，在很好地解决了共享单车调度的同时，保证了共享单车企业的利益更大化，对共享单车的优化调度方案具有一定的参考价值。
（作者单位：重庆大学经济与工商管理学院）
主要参考文献：
［1］高楹，宋辞，舒华，等.北京市摩拜共享单车源汇时空特征分析及空间调度［J］.地球信息科学学报，2018（8）.
［2］杨珈惠，聂规划，刘畅，等.允许局部路径重复的共享单车调度模型［J］.北京邮电大学学报（社会科学版），2018.20（5）.
［3］王嘉薇，朱家明，祁浩宇，等.基于VRP模型城市共享单车的优化调配研究［J］.沈阳理工大学学报，2018.37（1）.
［4］汪慎文，杨锋，徐亮，等.离散差分进化算法求解共享单车调度问题［J］.郑州大学学报（工学版），2019（4）.
［5］赵敬洋.公共慢行系统的动态调度建模与滚动时域调度算法研究［D］.杭州：浙江工业大学，2010.
［6］Lin J R，Yang T H.Strategic design of public bicycle sharing systems with service level constraints［J］.Transportation Research Part E Logistics & Transportation Review，2011.47（2）.
［7］Contardo C，Morency C，Rousseau L.Balancing a dynamic public bike-sharing system［J］.2012.
［8］Chemla D，Meunier F，Calvo R W.Bike sharing systems：Solving the static rebalancing problem［J］.Discrete Optimization，2013.10（2）.
［9］Benchimol，Mike，Benchimol，et al.Balancing the stations of a self service“bike hire” system［J］.RAIRO-Operations Research，2011.45（1）.
［10］李锦霞.公共自行车调度优化研究［D］.长沙理工大学，2013.
［11］孔继利，顾苧，孙欣，等.系统聚类和重心法在多节点配送中心选址中的研究［J］.物流技术，2010（5）.
［12］周生伟，蒋同海，张荣辉.改进遗传算法求解VRP问题［J］.计算机仿真，2013（12）.
［13］刘兆仁，徐冠宇，尹航.基于遗传算法的公共自行车调度优化［J］.物流技术，2017（2）.
|
|
|
|
