“第三方代管”参与下的共享单车回收路线优化问题_徐国勋 (1).pdf

第 卷 第 期运筹与 管理，年 月 收稿日期：基金项目：国家自然科学基金资助项目（，）；海南省自然科学基金资助项目（，）；山东省自然科学基金面上项目（）作者简介：徐国勋，男，博士，讲师，研究方向：物流优化，旅游优化；王书伟，通讯作者，男，博士，副教授，研究方向：调度优化，智能优化算法设计；郭强，男，博士，教授，研究方向：物流与供应链管理；赵达，男，博士，教授，研究方向：物流与供应链管理。“第三方代管”参与下的共享单车回收路线优化问题徐国勋，王书伟，郭 强，赵 达（海南大学 旅游学院，海南 海口；山东科技大学 经济管理学院，山东 青岛；海南大学 管理学院，海南 海口）摘 要：以共享单车回收为背景，研究了“第三方代管”参与下的回收路线优化问题。针对代管员和调度卡车的特征，提出激励代管员将零散分布的损坏单车运送至附近的中转点，然后派遣卡车将这些集中起来的损坏单车从中转点运送至维修中心。以总成本最小为目标建立混合整数规划模型，针对问题特性设计改进遗传算法。数值实验论证了问题特性，并论证得出在所提回收策略下及时回收损坏单车，不仅可以减轻公共空间被损坏单车挤占的问题，还可以有效减少回收成本。实验结果还表明所设计算法在短时间内能获得高质量解。关键词：共享单车；损坏单车回收；第三方代管；混合整数规划；遗传算法中图分类号：文章标识码：文章编号：（）：，（，；，；，）：，：；引言在中国，共享单车已成为第三大公共交通系统，仅 年便为人们节约出行时间 亿小时，减少雾霾成本 亿元，提高平均出行效率。然而根据调查研究发现，由于故意损坏、机械故障和零配件老化等原因，过去三年全国各城市损坏共享单车数量快速增加。这些损坏的共享单车带来了严重的资源浪费问题，用户满意度下降问题，用户骑行安全问题等。因此，及时召回损坏单车成为共享单车系统可持续发展的关键因素之一。除法律法规建设之外，利用卡车进行高效回收是目前共享单车回收问题研究的重点。一些研究者 考虑再平衡整个共享单车网络时加入损坏单车回收的操作，即卡车在各个站点既转运可用单车又同时回收损坏单车。徐国勋等认为很难同时实现这两个目标，需要均衡考虑损坏单车的回收数量和可用单车的转运数量，并通过增大回收惩罚系数来提高回收需求的优先级。一些研究者提出在回收过程中应考虑时间因素的制约。例如王涵霄等认为部分损坏单车可以当场维修，将维修时间加入到某些站点的服务时间内，并规定维修成功的单车可即刻转运到别的站点。等以最小化总时间为目标建立了一种基于真实数据的回收模型，并在模型中同时考虑了调度人员的开车时间、行走时间和损坏单车查找时间。还有一些研究者考虑了损坏单车的分布情况。例如张巍等提出站点损坏单车近似服从正态分布，并选择合适的成本阈值来作为站点选取的标准。当共享单车系统规模不是很大时，或可满足完全基于卡车进行回收。而我国大中城市的共享单车系统规模普遍很大，回收任务非常繁重，派遣卡车回收的成本又很高，运营商没有足够的资源及时回收损坏单车，从而导致城市公共空间被损坏单车挤占的问题很突出。因此政府与社会在呼吁共享单车用户参与损坏单车的回收利用，但由于并没有找到有效的激励机制，效果不尽人意。鉴于此，近年来多地开始推出“第三方代管”这一新措施，由城管部门牵头，联合运营商聘请第三方代管员在路面巡查。代管员除了规范车辆停放外，还使用电动三轮车将零散分布的损坏单车运送至指定地点，以协助运营商完成回收操作。第三方代管具有成本低和灵活度高的优点，很快成为共享单车回收的重要补充力量。但同时也存在着效率和可靠性相对较低等问题，因此仅适合短距离小批量操作，而中长距离大批量操作仍需要派遣调度卡车来完成。然而在实际中却经常出现：代管员被委派将损坏单车运送至较远距离的维修地，导致其单个操作周期大大变长，进而丧失性价比；卡车被委派去回收操作困难的地点（例如零散分布的居民小区、拥堵的街道等），回收成本与回收数量不成比例，丧失性价比。以往研究全部基于有足够数量的调度卡车完成回收任务这一前提，仅考虑部署调度卡车进行回收，并没有针对实际中存在的第三方代管参与回收的情况来制定回收策略。鉴于此，本文提出第三方代管参与下的共享单车回收路线优化问题，并聚焦于将问题建模成混合整数规划，以及设计高效智能优化算法，为共享单车的回收管理提供重要的科学理论依据。问题描述和模型建立在本问题中，网络中的站点被划分为回收需求点和中转点。回收需求点是存在若干损坏单车的站点，而中转点是普通的租还车站点，用来临时停放从别处运送过来的损坏单车。运营商调派第三方代管员进行短距离小批量回收操作，同时派遣调度卡车进行中长距离大批量操作。回收任务则分成两部分：首先激励代管员将损坏单车从回收需求点运送至附近的中转点，然后派遣卡车将这些集中起来的损坏单车从中转点运送至维修中心。实际中运营商采用购买服务的方式来雇佣代管员，为衡量其完成一次任务应获得的奖励，需考虑以下因素：（）运送距离。由于工作成本（例如时间花费）与回收需求点至中转点的距离成正比，因此奖励大小与运送距离正相关，以体现代管员的工作成本。（）回收需求点损坏单车数量。回收需求点内共享单车损坏数量越多，公共空间被挤占情况越严重，因此奖励大小与回收需求点损坏单车数量正相关，以激励代管员及时将损坏单车运走，解决这些站点公共空间被损坏单车挤占的问题。（）对中转点租还车服务的影响。运送到中转点的损坏单车过多，会影响其正常租还车服务，因此奖励大小与对中转点正常业务的影响程度负相关，以限制代管员出于各种原因（例如图方便省事）将损坏单车堆积在某些站点。而中转点容量越大，运送过来一辆损坏单车的占比则越小，则对正常业务的影响就相对越小，故可用中转点容量的倒数来表示对租还车服务的影响程度。根据以上分析，代管员从回收需求点 运送一辆损坏单车至中转点 获得的奖励 可由公式（）计算得到。其中 表示单位奖励系数，表示回收需求点至中转点的距离，表示回收需求点 内损坏单车数量，表示奖励下限，表示中转点的可用容量（由于 且为整数，为防止分母为，采用 来表示）。且（）为表示数学模型，用到了以下符号：集合：运营商派遣的调度卡车集合；：代管员集合；：回收需求点集合；：中转点集合；，其中 点表示车场（即维修中心）；。参数：回收需求点 的初始库存，即待回收单车数运 筹 与 管 理 年第 卷量；：中转点 的容量；：点 和 之间的距离；：卡车的单位距离成本；：卡车的容量上限；：代管员运送能力上限；：用于激励代管员的总预算；：一个很大的正数。决策变量：卡车 从点 驶向 则为，否则为；：卡车 在中转点 装载的损坏单车数量；：代管员 从回收需求点 运送至中转点 的损坏单车数量。：用来表示卡车 离开中转点 时装载总量的辅助变量；：用来避免子环的辅助变量。数学模型，（）（）（）（），（）（），（）（）（），（），（）（）（），（）（），（），（），（），（），（）目标函数（）包含两部分，第一部分是卡车将中转点损坏单车回收至维修中心的总成本，第二部分是代管员将损坏单车集中至中转点后给予的总奖励。约束条件（）限定了奖励支出预算。这是由于在实际中，一般是采用购买服务的方式来雇佣代管员，因此受到预算约束。约束条件（）确保代管员将每个回收需求点内的损坏单车全部运出。约束条件（）表明在中转点，代管员运送来的损坏单车总量不超过该中转点容量。约束条件（）是代管员运送能力上限。约束条件（）确保由代管员运送至中转点的这些损坏单车最终全部被回收至维修中心。约束条件（）确保若卡车未服务某中转点，则相应的装载数量为。约束条件（）（）确保每辆卡车在整个回收行程中的装载量不超过容量限制。约束条件（）确保每辆卡车空载状态从维修中心出发。约束条件（）表示卡车在该中转点回收数量等于访问该点前后对应的装载数量之差。约束（）限定了卡车装载量取值范围。约束条件（）（）确保卡车从维修中心出发，并最后返回维修中心。约束条件（）确保卡车服务过某中转点后必须从该点离开。约束条件（）是子环消除条件，防止卡车路线中出现不包括维修中心的回路。约束条件（）（）限定变量取值范围。求解算法由于本问题中包含的卡车路线问题是车辆路径问题这一经典的，这意味着本问题是更难求解的，当规模较小的时候采用求解器（如，等）可有效对问题进行求解。但是 和 指出这些求解器的性能与问题规模呈负相关关系，不适合处理大规模问题，而智能优化算法更适合处理这类问题。鉴于共享单车网络规模很大，本文选择设计智能优化算法求解所提问题。大量的数值实验证明遗传算法可以高效地求解车辆路径问题，取送货问题和共享单车再平衡问题等各类路线优化问题。考虑到本问题亦是路线优化问题，故选择遗传算法作为算法框架。但遗传算法仅能选定中转点和确定卡车路线，不能确定代管员的路线和运送数量以及卡车在每个中转点的装载数量。为了求解这些额外的变量，本文在遗传算法中嵌入了一种启发式算法。在每次的迭代中，遗传算法不断地调用该启发式算法，从而构成 了 一 种 改 进 遗 传 算 法（，）。算法框架中解的表示、选择与交叉和种群管理策略与 等保持一致，本节重点阐述根据问题属性重新设计的解的评估，教育和修复算子以及用来求解决策变量 和 的嵌入算法等。解的评估任意解 都有对应的目标函数值（），。由于 是卡车路线的向量表示（例如），故在 已知的情况下，表示卡车路线的 决策变量 成 为 已 知 参 数，即 （）的 第 一 部 分，可 确 定。而 （）第 二 部 分由 节中嵌入算法确定。第 期 徐国勋，等：“第三方代管”参与下的共享单车回收路线优化问题为提高算法的搜索能力，通过对参数 进行松弛来引入不可行解。相对于 的超出量被定义为（），（）。如果 是一条不可行解，则（）。否则，（）。因此可以用适应度函数值（）（）（）来更新（），其中 是初始值为 的惩罚系数。为维护种群多样性，需将适应度函数值与种群多样性特征进行结合，故引入偏差函数（）（）（）（）。其中，表示保留至下一次迭代的精英个体总数，是对应子种群（可行子种群和不可行子种群）规模大小，（）是解 对应的适应度函数值，（）表示解 同其余解的相似度数值在子种群中的排序值。本算法相似度是 与其它解的相同弧数量。举例如下，假设存解：和：。显然它们的相同弧分别是（，），（，）和（，），因此二者相似度为。教育与修复为提高子代个体的质量，引入了教育算子。在教育算子中，包含随机删除，半径破坏，最小贡献移除，随机插入，最优插入，多点插入，随机交换和随机逆序八种局部搜索方法：（）随机删除。从解中随机选择一个点，然后将该点从解中移除。（）半径破坏。从解中随机选择一个点，然后将该点与距离该点最近点删除。（）最小贡献移除。从解中找出对最小化卡车运输成本贡献最小的点 （，），将其从解中删除。（）随机插入。从未被访问过的站点中随机选择一个点，然后插入到解中。（）最优插入。随机选择未访问过的点，并将 插入解中最小成本位置。例如若 被插入至点 和 之间，若，（）（，），则该插入位置为最小成本位置。（）多点插入。从未访问站点中随机挑选两个点，然后将二者随机插入到解中。（）随机交换。从解随机选择两个点并交换它们在解中的位置。（）随机逆序。随机选择一条子序列并将该子序列逆序。教育算子的具体流程如下：经过教育操作后的解如果变得可行则将其置于可行子种群中，如果仍然不可行则将其置于不可行子种群中，然后进行概率为 的修复操作。每个不可行解最多可以修复两次，第一次将（）中的系数 乘（）倍，第二次将系数 乘（），其中 于区间（，随机取值。如果修复之后，原来的不可行解成为可行解，则将修复后的新可行解置于可行子种群中，与此同时在非可行子种群中保留原不可行解。教育算子：将所有方法的编号放置在集合 中；：随机在 中挑出一种方法；：如果该方法能够改进当前解，则重复使用该方法对当前解进行改进。如果连续进行 次迭代都无法改进当前解，则教育算子需被终止；：从 中将该局部搜索方法剔除；：如果 不为空集，则转步骤，否则结束教育算子。嵌入算法由于解 是卡车路线的向量表示，在 已知的情况下决策变量 可确定。这意味着（）代管员必须将损坏单车运送至卡车经过的中转点；（）当