基于VRP问题的大学校园共享单车的优化调度

孙启隆 李文荣 庞晓军

【摘要】如今，共享经济以及移动互联网飞速发展，共享单车已成为我国各大院校学生出行的重要工具。因此，收集、分析学生的骑车需求以及时空特征，对校园共享单车进行优化调度具有重要意义。由于校园内单车骑行的特殊规律性，本文提出结合‘吧三stic模型对骑行高峰期需求量进行合理预测，并利用VRF问题确定调度路线，选择遗传算法进行求解，最后以山东师范大学为实例，给出优化调度路线。

【关键词】共享单车 优化调度 Logistic模型 VRP问题 遗传算法

1、引言

从2016年起，共享单车迅速普及，我国各大院校中也出现了共享单车的身影，为广大学生提供了便利。但是，校园内共享单车的供需关系及调度问题还存在一定的不合理性。因此，分析学生的骑车需求以及时空特征，对校园共享单车进行优化调度具有重要意义。本文利用VRP（Vehicle Routing Problem）问题研究大学校园共享单车的优化i思度，主要分为数据收集与处理、调度需求预测方法、优化调度模型的建立及求解3个阶，段。其中，数据收集以问卷调查和实地调查为主;高峰期的调度需求预测通过结合Logistic模型和实际情况实现;在调度优化模型建立及求解部分，首先进行区域划分，利用VRP问题确定调度路线，并选择遗传算法进行求解。

2、数据收集与处理

数据收集主要通过问卷调查和实地调查的方法。问卷调查的主要目的是得到学生对校园内部单车数量、投放情况的满意程度，以及骑行的时空特征。实地调查的目的是获取包括不同时间停放量在;内的校园内各投放点的实际情况。

由于实地调查受到时间限制，所获取数据并不完整，为了得到较为准确的完整数据，本文选择将得到的数据通过Matlab利用最小二乘法并结合实际进行非线性拟合，将缺失数据完整化。

3、调度需求预测方法

由于校园内单车的骑行时间受到课程安排的影响，在工作日会表现出明显的规律性，而在周末，学生自由支配时间，出行相对分散，并没有呈现出明显的规律。故在本文中，主要对校园内共享单车在工作日的调度需求进行研究。

3.1 各投放点的单车数量变化

将一天24h分为σ个时间段，每个时间段中单车数量变化服从相同的函数关系，则投放点单车数量随时间变化的函数关系为周期切换函数：

其中，to为初始時刻，D=5为周期，函数f_i（t）表示在i时段的周转车辆数满足的函数关系，且f_i（t）不完全相同。

以某高校上课时间前后的教学楼区投放点为例，该时段以单车骑入为主，骑出量可忽略不计，单车数量变化符台Logistic模型。

假设单车的增长率函数为：

3.2 调度需求模型的建立

在校园中，学生通常会按照出行时间、距离以及特殊天气状况等因素对出行方式进行选择。因此，首先考虑建立出行方式效用函

4、优化调度模型的建立及求解

4.1 区域划分

同一时间点，各投放点的需求量及调度量受到空间位置的影响，虽然学校内的投放点较多，但工作日尤其是高峰期时段，投放点之间存在明显的规律性。故可将投放点所在区域根据关联关系进行分组，对区域进行划分，从而简化问题。

4.2 优化调度模型的建立

4.2.1 模型假设及符号说明

假设1：区域i到区域j之间的距离取区域i中心到区域j中心的欧氏距离;

假设2：每辆调运车容量相同，最多装载G辆共享单车;

假设3：运送每台单车单位距离所需成本相同;

假设4：调度任务在高峰期之前的规定时间内完成。

4.2.2 基于VRP问题的单车优化调度模型的建立

假设有K个投放点需要进行调酉己，从调度中心K₀派出M辆调度车，在规定时间内去往各投放点，完成调度任务，最后返回调度中心K₀。

设y_ijm为调度车m从投放点i到投放点j运送的单车数量，则M辆调度车的单车调度成本之和C为：

其中，距离取欧氏距离d_ij，U_c表示运送每台单车单位距离所需

5、实际算例

以山东师范大学内青桔单车为例，基于上述模型对学生的骑车需求进行收集分析，对校园共享单车进行优化调度。

5.1 数据收集及处理。对2019年12月3日—2019年12月7日校园中各投放点的实地调查数据进行‘整理，以2019年12月5日的实地调查结果为例进行数据缺失处理。

通过Matlab利用最小二乘法并结合实际进行非线性拟合得到最终数据如表3所示：

5.2 调度需求模型的检验。根据上述7：00-9：00的B区投放点单车数，利用Logistic模型求得该高峰期时段单车数随时间的变化，并将该数据与实际数据进行比较，得到下图：

其中，红色曲线为Logistic模型下单车数量变化曲线，蓝色折线由实际数据连接而成，容易看到模型与实际变化趋势大致相同，且误差在5辆内波动，故可用来预测高峰期的单车数量。

5.3 优化调度模型的建立与求解

由于在高峰期时段，学生的路线主要是从宿舍楼所在投放点至文渊教学楼区。对此，调度任务是将闲置的车辆提前运送到各宿舍楼投放点。

由于学校宿舍楼总区域占地面积及所跨坡度较大，不妨按照宿舍区域的命名，将宿舍楼投放点区域进行划分。假设校园中有10个投放点需要调度，根据上述区域划分方法，将10个投放点分为3个调度区域，分别由3辆最大载车辆为30的调度车进行调度。

利用4.2中的优化调度模型，取100为该算法的迭代次数，初始种群个数为8，交叉概率为0.9，变异概率为0.2，通过Matlab完成遗传算法。从图中可以看出，该遗传算法在迭代50次后开始收敛，在迭代100次后收敛。

求解结果为启用3辆调度车，调度路径分别为：1→2→1，1→8→7→6→5→1，1→3→4→1，总长度为1567.9m。其中，1、2、3、4、5、6、7、8分别为以下投放点的编号：文渊教学楼B区、梅苑中心投放点（4#）、图书馆、8#投放点、10#投放点、英华楼投放点、18#投放点、20#投放点。

参考文献：

[1]王嘉薇，朱家明，祁浩宇，李瑞新.沈阳理工大学学报[J].第37卷第1期2018.81-86.

[2]于梦，苏春芝，于桂芳，刘思雨，赵宇玲，兰慧，万曼曼[J].河北中医药学报。第35卷第1期2020.12-15.

[3]史越.共享单车需求预测及调度方法研究[D].北京：北京交通大学.2019.

特别感谢：山东师范大学数学与统计学院的李海涛教授对该论文的修改所提供的建议，以及大学生创新创业项目2019130211的资助。

作者简介：孙启隆（1999-），女，山东曲阜人，大学本科在读，研究方向为信息与计算科学。李文荣（2000-），女，山东肥城人，大学本科在读，研究方向为数学与应用数学。庞晓军（1999-），女，山东聊城人，大学本科在读，研究方向为数学与应用数学。