共享单车调度模型和方法综述

2022-09-06何紫齐,肖磊,李世隆等

中国自行车 2022年5期

0 引言

近年来，共享经济模式深入人心，共享单车也应运而生，低碳绿色出行逐渐成为一种趋势。共享单车解决了“最后一公里”的问题，缓解了交通堵塞压力，因而，逐渐成为人们短途出行的主要交通工具之一。但是，在共享单车迅猛发展的同时，也出现了一系列问题：租车难、还车难、单车分配不均衡，一些站点资源过剩，而另外一些资源不足，满足不了用户需求。这些问题不仅造成资源浪费，也会降低用户的满意度。高效的共享单车调度是解决上述问题的最有效途径。

所谓共享单车调度问题，即，调度车辆从车场出发，途经若干租赁点，调度人员需要对各租赁点的共享单车进行分配或者收集，然后调度车辆再返回车场；调度车辆在此过程中需要合理规划路径并对租赁点共享单车进行调整，以满足特定的指标。共享单车调度的具体过程可以参见图1，其中，箭头表示调度车辆行驶的方向，双向箭头表示一个来回过程，图1（a）为单个调度车辆完成任务的过程，图1（b）为多个车辆的调度过程。

图1 共享单车调度具体过程

该问题本质上是一个车辆路径规划问题，但是也有别于车辆路径规划问题，其复杂性要高于传统的车辆路径规划问题，但本质上都是组合优化问题。调度车辆时，当单车以及租赁点个数较少时，我们可以采用数学方法进行精确求解；当问题规模较大时，我们需要寻求高效的方法来获取较优的调度策略。

1 共享单车调度模型

为了求解共享单车调度问题，我们需要构建上述问题的数学模型，也即问题所要满足的特定的指标，比如调度成本最低、车辆利用率最高等。

一般来说，共享单车调度问题的数学模型多为调度成本。徐国勋等考虑共享单车出现的供需不平衡现象，考虑采用“红包车”机制来缓解运营商调度压力，以整体运营成本最低为目标函数，构建问题的混合整数规划模型；杨珈惠等考虑实际使用中的动态规划情况，允许出现局部路径重复的情况，引入动态规划模型，考虑调度车辆和运输距离最小的情况，以获得总的调度成本最低；张陌尘等考虑共享单车不同时期的状态，根据静态和动态两种不同情况，在静态调度过程中，考虑行驶距离最小，而在动态过程中，考虑调度成本最低，以此来构建问题的数学模型；关宏志等根据用户信息建立用户选择模型，并综合考虑用户奖励成本和运营调度成本，建立了用户参与的成本最低化的混合调度模型。

此外，还有一些工作考虑了其他的指标。比如，于德新等分析了影响共享单车成本的参数，在考虑成本最低的同时，将投放率最高为目标，构建了共享单车调度模型；李珍萍等考虑单车利用率和用户满意度，将这两个指标建立成问题的数学模型，同时，融合调度总成本，建立共享单车调度问题的整数规划模型；文蝶斐等考虑单车系统资源的充分利用，收集某市某区域一天的共享单车骑行数据，并对数据进行处理，提取特征，结合需求分析，考虑单车使用率、闲置率，单车平均使用次数，以初始配置的车辆总数为目标函数，来构建问题的数学模型；吕晓萌等收集共享单车数据，统计各个区域的人流量和用户需求量，构建单车调度的非线性规划调度模型，并据此来分配每个租赁点的共享单车数量。

共享单车主要的调度指标如表1所示。

表1 主要调度指标总结

2 共享单车调度方法

共享单车调度问题本质上是一个组合优化问题，为了获得更高效的调度方案，许多学者对共享单车调度方法进行了研究。目前，共享单车调度的方法主要有如下两类：精确算法和启发式算法求解。精确算法主要包括分支定界法、割平面法、动态规划法等；启发式算法可以分为传统启发式算法和元启发式算法，传统启发式算法主要包括局部搜索算法、松弛方法、构造型方法等，元启发式算法包括遗传算法、粒子群优化算法、人工神经网络算法、模拟退火算法、禁忌搜索算法等。常用共享单车调度方法的分类如图2所示。

图2 常用共享单车调度方法

对于精确算法，Zhou Yuyan等针对北京病人前往医院就诊前后使用共享单车行为进行建模，基于效用最大化准则，采用多项式评定模型（Logit模型）进行模型求解；戴敏等针对带有时间窗的局内开放式车辆调度问题，进行竞争分析，设计了用于求解该问题的竞争算法，提出了重新规划策略；文献针对构建的共享单车调度模型，采用LINGO软件来求解，以得到问题的最优调度方案；王浩等采用单纯形法来求解共享单车优化调度问题，所得结果达到了最小的成本和最高效的调度方式。

对于启发式算法，于德新等采用改进的遗传算法对问题进行求解，引入了精英选择策略以及优劣解距离法（TOPSIS法）来评价解的优劣，以降低企业的调度成本；Duan Yubin等考虑在车辆违反交通限制而不能沿着汉密尔顿路径行驶时，采用贪婪算法来调整路径，以获得一个更快速且灵活的策略；贾立双等提出一种改进的多车调度方法，采用最近邻和遗传算法相结合，获取的配送路线较之其他算法更合理；王玲玲等针对传统调度方法的不足，提出了一种多点循环甩挂运输模式，并采用禁忌搜索方法对问题进行求解；此外，周骞等也将禁忌搜索算法用于单车调度优化中，不同的是，所提方法结合了遗传算法；文献均考虑采用基于BP神经网络来优化共享单车调度问题，依靠BP神经网络来进行需求等的预测，来为共享单车调度提供策略。

此外，随着人工智能的兴起，许多学者将深度学习融入调度策略的求解。如, Mao Dianhui等基于时空图，根据自行车的骑行数据估计出每个区域的自行车数量，给出了单车的移动模式和规则，以更好地进行共享单车调度；王嘉薇等基于VRP模型，采用模糊综合评价的方法来构建模型，给出共享单车调度方案；Vazquez-Abad J. Felisa等考虑共享单车系统获取的大量数据，考虑采用数据驱动的方法来对问题进行求解；Xu Miao等基于上海地区GPS数据时空特征的可视化分析结果，提出了一个新的分级和分区方法，并采用深度学习来对共享单车供需多块混合模型进行预测；张建同等针对共享单车分布动态变化的情况，提出采用深度强化学习来对共享单车进行重置，该方法根据单车分布的数据，构建环境交互模拟器，通过大规模数据实验，得到性能优越的解。

3 挑战与展望

上述成果丰富了共享单车调度理论，为共享单车商家提供了众多解决方案。但是随着科技的发展，技术迭代越来越快，我们有必要对调度方法和模型提出更高的要求，以便满足用户进一步的需求。

3.1 模型构建创新

在模型构建方面，我们可以根据前期搜索的数据，采用机器学习等方法来进行特征选择构建问题的模型；如有必要，可以让用户参与进来，采用人机交互的方法来选择或评价模型的优劣；此外，还可以同时考虑多目标，比如调度时间、调度人工成本、用户满意度、用户徒步到租赁点的距离等，构建多目标模型；进一步，考虑实际问题中存在的动态或不确定问题，比如车辆突然损坏、换车租赁点车满等情况，据此构建动态不确定模型。