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

《“第三方代管”参与下的共享单车回收路线优化问题_徐国勋 (1)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

第３２卷第１期运筹与管理Ｖｏｌ．３２，Ｎｏ．１２０２３年１月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＪａｎ．２０２３“第三方代管”参与下的共享单车回收路线优化问题１２１３徐国勋，王书伟，郭强，赵达（１．海南大学旅游学院，海南海口５７０２２８；２．山东科技大学经济管理学院，山东青岛２６６５９０；３．海南大学管理学院，海南海口５７０２２８）摘要：以共享单车回收为背景，研究了“第三方代管”参与下的回收路线优化问题。针对代管员和调度卡车的特征，提出激励代管员将零散分布的损坏单车运送至附近的中转点，然后派遣卡车将这些集中起来的损坏单车从中转点运送至维修中心。以总成本最小为目标建立混合整数规划模型，针对问题特性设计改进遗传算法。数值实验论证了问题特性，并论证得出在所提回收策略下及时回收损坏单车，不仅可以减轻公共空间被损坏单车挤占的问题，还可以有效减少回收成本。实验结果还表明所设计算法在短时间内能获得高质量解。关键词：共享单车；损坏单车回收；第三方代管；混合整数规划；遗传算法中图分类号：Ｆ２５３．４文章标识码：Ａ文章编号：１００７⁃３２２１（２０２３）０１⁃００４１⁃０６ｄｏｉ：１０．１２００５／ｏｒｍｓ．２０２３．０００７ＡＢｉｋｅＲｅｃｙｃｌｉｎｇＰｒｏｂｌｅｍｗｉｔｈＴｈｉｒｄ⁃ｐａｒｔｙＰａｒｔｉｃｉｐａｔｉｏｎｉｎＢｉｋｅＳｈａｒｉｎｇＳｙｓｔｅｍｓ１２１３ＸＵＧｕｏｘｕｎ，ＷＡＮＧＳｈｕｗｅｉ，ＧＵＯＱｉａｎｇ，ＺＨＡＯＤａ（１．ＳｃｈｏｏｌｏｆＴｏｕｒｉｓｍ，ＨａｉｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｈａｉｋｏｕ５７０２２８，Ｃｈｉｎａ；２．ＳｃｈｏｏｌｏｆＥｃｏｎｏｍｉｃｓａｎｄＭａｎａｇｅｍｅｎｔ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｑｉｎｇｄａｏ２６６５９０，Ｃｈｉｎａ；３．ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＨａｉｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｈａｉｋｏｕ５７０２２８，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｉｎｂｉｋｅｓｈａｒｉｎｇｓｙｓｔｅｍｓ，ｂｒｏｋｅｎｂｉｋｅｓｍａｙｂｅｐｉｌｅｄｕｐａｓｈｉｇｈａｓａｍｏｕｎｔａｉｎｉｎｍａｎｙｓｔａｔｉｏｎｓｄｕｅｔｏｔｈｅｌａｃｋｏｆｒｅｃｙｃｌｉｎｇ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｅｒｅｃｙｃｌｉｎｇｐｒｏｂｌｅｍｏｆｂｒｏｋｅｎｂｉｋｅｓｉｓｓｉｇｎｉｆｉｃａｎｔｔｏｄｅｖｅｌｏｐａｓｕｓｔａｉｎａｂｌｅｂｉｋｅｓｈａｒｉｎｇｓｙｓｔｅｍ．Ｔｏｉｍｐｒｏｖｅｔｈｅｒｅｃｙｃｌｉｎｇｅｆｆｉｃｉｅｎｃｙｏｆｂｒｏｋｅｎｂｉｋｅｓ，ａｂｉｋｅｒｅｃｙｃｌｉｎｇｒｏｕｔｉｎｇｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｗｉｔｈｔｈｉｒｄ⁃ｐａｒｔｙｍａｎａｇｅｍｅｎｔｉｓｐｒｏｐｏｓｅｄ．Ｂａｓｅｄｏｎｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｉｒｄ⁃ｐａｒｔｙｅｍｐｌｏｙｅｅｓａｎｄｔｒｕｃｋｓ，ｔｈｉｒｄ⁃ｐａｒｔｙｅｍｐｌｏｙｅｅｓａｒｅｉｎｃｅｎｔｉｖｉｚｅｄｔｏｒｅｌｏｃａｔｅｂｒｏｋｅｎｂｉｋｅｓｔｏｔｒａｎｓｓｈｉｐｍｅｎｔｓｔａｔｉｏｎｓｔｏｆａｃｉｌｉｔａｔｅｃｅｎｔｒａｌｉｚｅｄｒｅｃｙｃｌｉｎｇ，ｗｈｉｌｅｔｒｕｃｋｓａｒｅｄｅｐｌｏｙｅｄｔｏｔｒａｎｓｐｏｒｔｔｈｅｓｅｂｒｏｋｅｎｂｉｋｅｓｆｒｏｍｔｒａｎｓｓｈｉｐｍｅｎｔｓｔａｔｉｏｎｓｔｏｔｈｅｒｅｐａｉｒｃｅｎｔｅｒ．Ｔｈｅｐｒｏｂｌｅｍｉｓｆｏｒｍｕｌａｔｅｄａｓａｍｉｘｅｄ⁃ｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｔｏｍｉｎｉｍｉｚｅｔｈｅｔｏｔａｌｃｏｓｔ．Ｔｏｓｏｌｖｅｔｈｅｐｒｏｐｏｓｅｄｐｒｏｂｌｅｍ，ａｎｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｓｄｅｖｅｌｏｐｅｄ．Ｎｕｍｅｒｉｃａｌｅｘｐｅｒｉｍｅｎｔｓｄｅｍｏｎｓｔｒａｔｅｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｅｐｒｏｐｏｓｅｄｐｒｏｂｌｅｍ，ａｎｄｒｅｖｅａｌｔｈａｔｔｈｅｐｒｏｐｏｓｅｄｒｅｃｙｃｌｉｎｇｓｔｒａｔｅｇｙｃａｎｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｏｆｐｕｂｌｉｃｓｐａｃｅｏｃｃｕｐｉｅｄｂｙｂｒｏｋｅｎｂｉｋｅｓａｎｄｅｆｆｅｃｔｉｖｅｌｙｒｅｄｕｃｅｔｈｅｏｐｅｒａｔｉｏｎｃｏｓｔ．Ｎｕｍｅｒｉｃａｌｅｘｐｅｒｉｍｅｎｔｓａｌｓｏｉｌｌｕｓｔｒａｔｅｔｈａｔｔｈｅｐｒｏｐｏｓｅｄｓｏｌｕｔｉｏｎｍｅｔｈｏｄｃａｎｏｂｔａｉｎｈｉｇｈ⁃ｑｕａｌｉｔｙｓｏｌｕｔｉｏｎｓｗｉｔｈｉｎａｓｈｏｒｔｃｏｍｐｕｔａｔｉｏｎｔｉｍｅ．Ｋｅｙｗｏｒｄｓ：ｂｉｋｅｓｈａｒｉｎｇ；ｂｒｏｋｅｎｂｉｋｅｒｅｃｙｃｌｉｎｇ；ｔｈｉｒｄ⁃ｐａｒｔｙｐａｒｔｉｃｉｐａｔｉｏｎ；ｍｉｘｅｄ⁃ｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ［１］１５％。然而根据调查研究发现，由于故意损坏、０引言机械故障和零配件老化等原因，过去三年全国各城［２］市损坏共享单车数量快速增加。这些损坏的共在中国，共享单车已成为第三大公共交通系［３］享单车带来了严重的资源浪费问题，用户满意统，仅２０１７年便为人们节约出行时间０．７６亿小度下降问题［４］，用户骑行安全问题等［１］。因此，及时，减少雾霾成本１３亿元，提高平均出行效率时召回损坏单车成为共享单车系统可持续发展的收稿日期：２０２０⁃１２⁃２９基金项目：国家自然科学基金资助项目（７２１６１００８，７１８６１００９）；海南省自然科学基金资助项目（７２１ＲＣ５２６，２０１９ＣＸＴＤ４０２，７１８ＭＳ０３３）；山东省自然科学基金面上项目（ＺＲ２０２２ＱＧ０４５）作者简介：徐国勋，男，博士，讲师，研究方向：物流优化，旅游优化；王书伟，通讯作者，男，博士，副教授，研究方向：调度优化，智能优化算法设计；郭强，男，博士，教授，研究方向：物流与供应链管理；赵达，男，博士，教授，研究方向：物流与供应链管理。

1４２运筹与管理２０２３年第３２卷关键因素之一。理论依据。［５］除法律法规建设之外，利用卡车进行高效回收是目前共享单车回收问题研究的重点。一些１问题描述和模型建立［６～８］研究者考虑再平衡整个共享单车网络时加入损坏单车回收的操作，即卡车在各个站点既转运可在本问题中，网络中的站点被划分为回收需求［９］用单车又同时回收损坏单车。徐国勋等认为很点和中转点。回收需求点是存在若干损坏单车的站难同时实现这两个目标，需要均衡考虑损坏单车的点，而中转点是普通的租还车站点，用来临时停放从回收数量和可用单车的转运数量，并通过增大回收别处运送过来的损坏单车。运营商调派第三方代管惩罚系数来提高回收需求的优先级。一些研究者员进行短距离小批量回收操作，同时派遣调度卡车提出在回收过程中应考虑时间因素的制约。例如进行中长距离大批量操作。回收任务则分成两部［１０］王涵霄等认为部分损坏单车可以当场维修，将分：首先激励代管员将损坏单车从回收需求点运送维修时间加入到某些站点的服务时间内，并规定维至附近的中转点，然后派遣卡车将这些集中起来的［１１］修成功的单车可即刻转运到别的站点。Ｌｕ等损坏单车从中转点运送至维修中心。实际中运营商以最小化总时间为目标建立了一种基于真实数据采用购买服务的方式来雇佣代管员，为衡量其完成的回收模型，并在模型中同时考虑了调度人员的开一次任务应获得的奖励，需考虑以下因素：车时间、行走时间和损坏单车查找时间。还有一些（１）运送距离。由于工作成本（例如时间花费）［１２］研究者考虑了损坏单车的分布情况。例如张巍与回收需求点至中转点的距离成正比，因此奖励大等提出站点损坏单车近似服从正态分布，并选择合小与运送距离正相关，以体现代管员的工作成本。适的成本阈值来作为站点选取的标准。（２）回收需求点损坏单车数量。回收需求点当共享单车系统规模不是很大时，或可满足完内共享单车损坏数量越多，公共空间被挤占情况越全基于卡车进行回收。而我国大中城市的共享单严重，因此奖励大小与回收需求点损坏单车数量正车系统规模普遍很大，回收任务非常繁重，派遣卡相关，以激励代管员及时将损坏单车运走，解决这车回收的成本又很高，运营商没有足够的资源及时些站点公共空间被损坏单车挤占的问题。回收损坏单车，从而导致城市公共空间被损坏单车（３）对中转点租还车服务的影响。运送到中挤占的问题很突出。因此政府与社会在呼吁共享转点的损坏单车过多，会影响其正常租还车服［４］单车用户参与损坏单车的回收利用，但由于并没有务，因此奖励大小与对中转点正常业务的影响［１３］找到有效的激励机制，效果不尽人意。鉴于此，程度负相关，以限制代管员出于各种原因（例如图近年来多地开始推出“第三方代管”这一新措施，方便省事）将损坏单车堆积在某些站点。而中转由城管部门牵头，联合运营商聘请第三方代管员在点容量越大，运送过来一辆损坏单车的占比则越路面巡查。代管员除了规范车辆停放外，还使用电小，则对正常业务的影响就相对越小，故可用中转动三轮车将零散分布的损坏单车运送至指定地点，点容量的倒数来表示对租还车服务的影响程度。以协助运营商完成回收操作。第三方代管具有成根据以上分析，代管员从回收需求点ｓ运送一本低和灵活度高的优点，很快成为共享单车回收的辆损坏单车至中转点ｉ获得的奖励ｒｓｉ可由公式（１）重要补充力量。但同时也存在着效率和可靠性相计算得到。其中ω表示单位奖励系数，ｃｓｉ表示回收对较低等问题，因此仅适合短距离小批量操作，而中需求点至中转点的距离，Ｉｓ表示回收需求点ｓ内损长距离大批量操作仍需要派遣调度卡车来完成。然坏单车数量，ｒｍｉｎ表示奖励下限，Ｌｉ表示中转点的可而在实际中却经常出现：代管员被委派将损坏单车用容量（由于Ｌｉ⩾０且为整数，为防止分母为０，采运送至较远距离的维修地，导致其单个操作周期大用Ｌｉ＋１来表示）。大变长，进而丧失性价比；卡车被委派去回收操作困Ｉｓｒ＝ω·ｃ·且ｒ⩾ｒ（１）ｓｉｓｉｓｉｍｉｎ难的地点（例如零散分布的居民小区、拥堵的街道Ｌｉ＋１等），回收成本与回收数量不成比例，丧失性价比。为表示数学模型，用到了以下符号：以往研究全部基于有足够数量的调度卡车完集合成回收任务这一前提，仅考虑部署调度卡车进行回Ｋ：运营商派遣的调度卡车集合；Ｕ：代管员集收，并没有针对实际中存在的第三方代管参与回收合；Ｍ：回收需求点集合；Ｎ：中转点集合；Ｎ０＝Ｎ∪的情况来制定回收策略。鉴于此，本文提出第三方｛０｝，其中０点表示车场（即维修中心）；Ｖ＝Ｍ∪Ｎ代管参与下的共享单车回收路线优化问题，并聚焦∪｛０｝。于将问题建模成混合整数规划，以及设计高效智能参数优化算法，为共享单车的回收管理提供重要的科学Ｉｓ：回收需求点ｓ的初始库存，即待回收单车数

2第１期徐国勋，等：“第三方代管”参与下的共享单车回收路线优化问题４３量；Ｌ：中转点ｉ的容量；ｃ：点ｉ和ｊ之间的距离；μ：（１１）确保每辆卡车在整个回收行程中的装载量不ｉｉｊ卡车的单位距离成本；Ｃ：卡车的容量上限；Ｈ：代管超过容量限制。约束条件（９）确保每辆卡车空载员运送能力上限；Ｔ：用于激励代管员的总预算；状态从维修中心出发。约束条件（１０）表示卡车在Ｍ：一个很大的正数。该中转点回收数量等于访问该点前后对应的装载０决策变量数量之差。约束（１１）限定了卡车装载量取值范ｋｋｘ：卡车ｋ从点ｉ驶向ｊ则为１，否则为０；ｙ：卡围。约束条件（１２）～（１３）确保卡车从维修中心出ｉｊｉｖ发，并最后返回维修中心。约束条件（１４）确保卡车ｋ在中转点ｉ装载的损坏单车数量；ｚ：代管员ｖｓｉ从回收需求点ｓ运送至中转点ｉ的损坏单车数量。车服务过某中转点后必须从该点离开。约束条件ｋ（１５）是子环消除条件，防止卡车路线中出现不包Ｑ：用来表示卡车ｋ离开中转点ｉ时装载总量的辅ｉ助变量；Ｂｋ：用来避免子环的辅助变量。括维修中心的回路。约束条件（１６）～（１９）限定变ｉ数学模型量取值范围。ｋｖｍｉｎ∑∑μｃｉｊｘｉｊ＋∑∑∑ｒｓｉｚｓｉ（２）ｋ∈Ｋｉ，ｊ∈Ｎ０ｓ∈Ｍ，ｉ∈Ｎｉ∈Ｎｖ∈Ｕ２求解算法ｖｓ．ｔ．∑∑∑ｒｓｉｚｓｉ⩽Ｔ（３）ｓ∈Ｍｉ∈Ｎｖ∈Ｕｖ由于本问题中包含的卡车路线问题是车辆路∑∑ｚｓｉ＝Ｉｓ∀ｓ∈Ｍ（４）ｉ∈Ｎｖ∈Ｕ径问题这一经典的ＮＰ⁃Ｈａｒｄ，这意味着本问题是更ｖ∑∑ｚｓｉ⩽Ｌｉ∀ｉ∈Ｎ（５）难求解的ＮＰ⁃Ｈａｒｄ，当规模较小的时候采用求解器ｓ∈Ｍｖ∈Ｕｖ（如ＣＰＬＥＸ，Ｇｕｒｏｂｉ，Ｉｐｓｏｌｖｅｒ，ＭＯＳＥＫ等）可有效ｚ⩽Ｈ∀ｓ∈Ｍ，ｉ∈Ｎ（６）ｓｉ［１４］对问题进行求解。但是Ｈｏ和Ｓｚｅｔｏ指出这些求ｋｖ∑ｙｉ＝∑∑ｚｓｉ∀ｉ∈Ｎ（７）解器的性能与问题规模呈负相关关系，不适合处理ｋ∈Ｋｓ∈Ｍｖ∈Ｕｙｋ⩽Ｍｘｋ∀ｋ∈Ｋ，ｉ∈Ｎ（８）大规模问题，而智能优化算法更适合处理这类问ｉ０∑ｉｊｊ∈Ｎ０题。鉴于共享单车网络规模很大，本文选择设计智ｋＱ＝０∀ｋ∈Ｋ（９）０能优化算法求解所提问题。ｋｋｋｋＱ⩾Ｑ＋ｙ－Ｍ（１－ｘ）∀ｋ∈Ｋ，ｉ∈Ｎ，ｊ∈Ｎ（１０）ｊｉｊ０ｉｊ０大量的数值实验证明遗传算法可以高效地求ｋ０⩽Ｑｉ⩽Ｃ∀ｋ∈Ｋ，ｉ∈Ｎ（１１）解车辆路径问题，取送货问题和共享单车再平衡问ｋ［１５～１８］∑ｘ＝１∀ｋ∈Ｋ（１２）题等各类路线优化问题。考虑到本问题亦是０ｉｉ∈Ｎ路线优化问题，故选择遗传算法作为算法框架。但ｋ∑ｘｉ０＝１∀ｋ∈Ｋ（１３）遗传算法仅能选定中转点和确定卡车路线，不能确ｉ∈Ｎ∑ｘｋ＝∑ｘｋ∀ｋ∈Ｋ，∀ｉ∈Ｎ（１４）定代管员的路线和运送数量以及卡车在每个中转ｉｊｊｉｊ∈Ｎ０ｊ∈Ｎ０点的装载数量。为了求解这些额外的变量，本文在ｋｋｋＢ⩾Ｂ＋１－Ｍ（１－ｘ）∀ｋ∈Ｋ，ｉ∈Ｎ，ｊ∈Ｎ（１５）ｊｉ０ｉｊ０遗传算法中嵌入了一种启发式算法。在每次的迭ｋＢ⩾０∀ｋ∈Ｋ，ｉ∈Ｎ（１６）ｉ０代中，遗传算法不断地调用该启发式算法，从而构ｋｘｉｊ＝｛０，１｝∀ｋ∈Ｋ，ｉ∈Ｎ０，ｊ∈Ｎ０（１７）成了一种改进遗传算法（ＩｍｐｒｏｖｅｄＧｅｎｅｔｉｃｋｙｉ⩾０∀ｋ∈Ｋ，ｉ∈Ｎ０（１８）Ａｌｇｏｒｉｔｈｍ，ＩＧＡ）。ＩＧＡ算法框架中解的表示、选择ｖ［１８］ｚ⩾０∀ｓ∈Ｍ，ｉ∈Ｎ，ｖ∈Ｕ（１９）与交叉和种群管理策略与Ｌｉ等保持一致，本节ｓｉ目标函数（２）包含两部分，第一部分是卡车将重点阐述根据问题属性重新设计的解的评估，教育ｋｖ中转点损坏单车回收至维修中心的总成本，第二部和修复算子以及用来求解决策变量ｙｉ和ｚｓｉ的嵌入分是代管员将损坏单车集中至中转点后给予的总算法等。奖励。约束条件（３）限定了奖励支出预算。这是２．１解的评估由于在实际中，一般是采用购买服务的方式来雇佣任意解ｐ都有对应的目标函数值ｆ（ｐ）＝代管员，因此受到预算约束。约束条件（４）确保代∑∑μｃｘｋ＋∑∑∑ｒｚｖ。由于ｐ是卡车ｉｊｉｊｓｉｓｉｋ∈Ｋｉ∈Ｎ０，ｊ∈Ｎ０ｓ∈Ｍｉ∈Ｎｖ∈Ｕ管员将每个回收需求点内的损坏单车全部运出。路线的向量表示（例如０→１→２→０→３→４→０），故约束条件（５）表明在中转点，代管员运送来的损坏在ｐ已知的情况下，表示卡车路线的０－１决策变单车总量不超过该中转点容量。约束条件（６）是ｋ量ｘ成为已知参数，即ｆ（ｐ）的第一部分代管员运送能力上限。约束条件（７）确保由代管ｉｊｋ员运送至中转点的这些损坏单车最终全部被回收∑∑μｃｉｊｘｉｊ可确定。而ｆ（ｐ）第二部分ｋ∈Ｋｉ∈Ｎ０，ｊ∈Ｎ０至维修中心。约束条件（８）确保若卡车未服务某ｖ∑∑∑ｒｓｉｚｓｉ由２．３节中嵌入算法确定。中转点，则相应的装载数量为０。约束条件（９）～ｓ∈Ｍｉ∈Ｎｖ∈Ｕ

3４４运筹与管理２０２３年第３２卷为提高算法的搜索能力，通过对参数Ｔ进行中的系数α乘（１＋γ）倍，第二次将系数α乘１０（１松弛来引入不可行解。ｐ相对于Ｔ的超出量被定＋γ），其中γ于区间（０，１］随机取值。如果修复之义为Ｅ（ｐ）＝ｍａｘ｛０，（∑∑∑ｒｚｖ－Ｔ）｝。如后，原来的不可行解成为可行解，则将修复后的新ｓｉｓｉｓ∈Ｍｉ∈Ｎｖ∈Ｕ可行解置于可行子种群中，与此同时在非可行子种果ｐ是一条不可行解，则Ｅ（ｐ）＞０。否则，Ｅ（ｐ）＝群中保留原不可行解。０。因此可以用适应度函数值Ｆ（ｐ）＝ｆ（ｐ）＋α·教育算子Ｅ（ｐ）来更新ｆ（ｐ），其中α是初始值为１的惩罚系１：将所有方法的编号放置在集合Ω中；数。为维护种群多样性，需将适应度函数值与种群２：随机在Ω中挑出一种方法；多样性特征进行结合，故引入偏差函数ＢＦ（ｐ）＝如果该方法能够改进当前解，则重复使用该方法对当ｆｉｔ（ｐ）＋（１－Ｎｅｌｉｔｅ／Ｎｉｎｄｉｖ）ｄｃ（ｐ）。其中，Ｎｅｌｉｔｅ表示保３：前解进行改进。如果连续进行ＩＴｅｄｕ次迭代都无法改留至下一次迭代的精英个体总数，Ｎ是对应子种进当前解，则教育算子需被终止；ｉｎｄｉｖ４：从Ω中将该局部搜索方法剔除；群（可行子种群和不可行子种群）规模大小，ｆｉｔ（ｐ）５：如果Ω不为空集，则转步骤２，否则结束教育算子。是解ｐ对应的适应度函数值，ｄｃ（ｐ）表示解ｐ同其余解的相似度数值在子种群中的排序值。本算法２．３嵌入算法相似度是ｐ与其它解的相同弧数量。举例如下，假由于解ｐ是卡车路线的向量表示，在ｐ已知的ｋ设存解ｐ１：０→３→１→２→４→０→５→６→８→７和情况下决策变量ｘｉｊ可确定。这意味着（１）代管员ｐ２：０→１→２→５→４→０→６→８→３→７。显然它们的必须将损坏单车运送至卡车经过的中转点；（２）当相同弧分别是（１，２），（４，０）和（６，８），因此二者相中转点选定后，卡车的最优成本便已固定。因此只似度为３。需根据代管员激励成本来安排其路线和需要运送２．２教育与修复的损坏单车数量即可：ｖ为提高子代个体的质量，引入了教育算子。在步骤１确定ｚ。ｓｉ教育算子中，包含随机删除，半径破坏，最小贡献移步骤１．１将剩余库存不为零的回收需求点除，随机插入，最优插入，多点插入，随机交换和随和剩余可用容量不为零中转点对应的ＯＤ对全部机逆序八种局部搜索方法：置于集合Ω；（１）随机删除。从解中随机选择一个点，然后步骤１．２根据ｒ的数值，按照由小到大的顺ｓｉ将该点从解中移除。（２）半径破坏。从解中随机选序对集合Ω中全部ＯＤ对排序；择一个点，然后将该点与距离该点最近点删除。步骤１．３确定Ω中第一个ＯＤ对可运送的（３）最小贡献移除。从解中找出对最小化卡车运损坏单车最大数量Ｚ＝ｍｉｎ｛Ｉ，Ｌ｝；ｓｉｓｉ输成本贡献最小的点ｔ＝ａｒｇｍａｘ（∑∑μｃｘｋ步骤１．４更新回收需求点的剩余库存和中ｉｊｉｊｋ∈Ｋｉ∈Ｎ０，ｊ∈Ｎ０转点的剩余可用容量。Ｉｓ←Ｉｓ－Ｚｓｉ，Ｌｉ←Ｌｉ－Ｚｓｉ。ｋ－∑∑μｃｉｊｘｉｊ），将其从解中删除。如果Ｉ＝０，则从Ω中将包含ｓ点的ＯＤ对全部移ｓｋ∈Ｋｉ∈Ｎ０，ｊ∈Ｎ０，ｉ≠ｔ，ｊ≠ｔ除；如果Ｌ＝０，将包含ｉ点的ＯＤ对全部移除；（４）随机插入。从未被访问过的站点中随机ｉ选择一个点，然后插入到解中。步骤１．５重复执行步骤１．３和步骤１．４，直到Ω中元素全部被清空，于是全部Ｚ便可确定；（５）最优插入。随机选择未访问过的点ｔ，并ｓｉ将ｔ插入解中最小成本位置。例如若ｔ被插入至点步骤１．６把运送任务（Ｚｓｉ辆损坏单车）分给ｉ和ｊ之间，若ｉ，ｊ＝ａｒｃｍｉｎ（μｃｉｔ＋μｃｔｊ－μｃｉｊ）（ｉ，ｊ）∈Ａ，ｖ＝［１＋Ｚｓｉ／Ｈ］个代管员，其中［．］表示取整。ｋｖ则该插入位置为最小成本位置。步骤２确定ｙｉ。ｚｓｉ确定后，各中转点内的损（６）多点插入。从未访问站点中随机挑选两坏单车库存便已知。将中转点内的损坏单车库存个点，然后将二者随机插入到解中。表示为ｑｉ。（７）随机交换。从解随机选择两个点并交换步骤２．１令ｋ＝１；它们在解中的位置。步骤２．２将卡车ｋ的剩余载重空间表示为Ｃｌｅｆｔ；（８）随机逆序。随机选择一条子序列并将该步骤２．３根据卡车ｋ访问中转点顺序依次ｋｋ子序列逆序。获取ｙｉ，其中ｙｉ＝ｍｉｎ｛ｑｉ，Ｃｌｅｆｔ｝；教育算子的具体流程如下：步骤２．４更新卡车ｋ的剩余载重空间，以及ｋｋ经过教育操作后的解如果变得可行则将其置中转点剩余库存，即Ｃｌｅｆｔ←Ｃｌｅｆｔ－ｙｉ，ｑｉ←ｑｉ－ｙｉ。重于可行子种群中，如果仍然不可行则将其置于不可复步骤２．３和步骤２．４，直至Ｃ＝０；ｌｅｆｔ行子种群中，然后进行概率为Ｐ的修复操作。步骤２．５若ｋ≥｜Ｋ｜，转步骤３。否则更新ｋｒｅｐａｉｒ每个不可行解最多可以修复两次，第一次将Ｆ（ｐ）←ｋ＋１，转步骤２．２。

4第１期徐国勋，等：“第三方代管”参与下的共享单车回收路线优化问题４５ｋｖ步骤３根据步骤１和２获取的ｙ和ｚ数值，量上限后，需要把损坏单车存放到其它中转点。相ｉｓｉ可确定目标函数值，算法结束。应地，卡车在回收过程中需要访问的中转点数量增加，进而使得其运输成本增加。由图１还可得，３数值实验“第三方代管”的奖励支出关于损坏单车数量的曲线斜率为正。这表明随着站点内积压的损坏单车３．１回收需求点内损坏单车数量与回收成本之间数量的增加，导致回收每辆损坏单车的单位奖励增的关系加也在增加，即需要支付给代管员更多的奖励来激一般情况下，出于种种原因（调度车辆不足、预励其将损坏单车运走，以解决站点公共空间被损坏算限制等）原因，运营商并不会及时回收损坏单车，单车挤占的问题。由于总回收成本为卡车运输成常常导致损坏单车在站点内逐渐积压。本节论证在本和“第三方代管”的奖励支出之和，因此总回收本文所提回收策略下及时回收损坏单车反而会减少成本亦随着损坏单车数量的增加。其余回收需求运营成本。为方便求出最优解，令Ｃ＝２０，Ｔ＝１００，点可以得到类似结论。ω＝０．５，μ＝１，Ｈ＝４，ｒ＝０，｜Ｋ｜＝１，｜Ｕ｜＝５。坐标综上所述，在本文所提回收策略下，回收需求ｍｉｎ＝｛（１２，１０）；（８，２０）；（１４，７）；（１０，１５）；（１，３）；（５，点内损坏单车数量与总回收成本是正相关关系。６）；（２，２）；（０，０）｝。其中前三个点为中转点，其容这意味着本文所提回收策略下及时回收损坏单车，量分别为｛５，７，９｝，最后一个点为没有任何需求的车不仅能够减轻站点公共空间被损坏单车挤占的问场，其余点为回收需求点，损坏单车数量分别为｛４，题，还能有效减少回收成本。４，２，２，１｝。实验结果如图１所示。３．２算法性能测试数值实验环境是ｉ７⁃２６００ＣＰＵ主频３．４０ＧＨｚ内存１６ＧＢ的ＰＣ电脑，编程语言为Ｃ＃。为了测试所设计ＨＧＡ算法性能，采用Ｇｕｒｏｂｉ８．０和遗传算法（ＧＡ）作为比对算法。由于没有针对本文所研究问题的算例，因此依据Ｉ均匀分布于［１，５］，Ｌ均匀分ｉｉ布于［５，１０］，Ｔ设为１０００，站点坐标均匀分布于［０，５０］，Ｃ＝２０，Ｈ＝１０，ｒ＝０，ω＝１和μ＝１生成规模ｍｉｎ不同的数据组。ＨＧＡ参数中，μ＝２５，Ｎ＝２５，ｉｎｄｉｖＮ＝１０，Ｐ＝０．５，ξ＝０．２，λ＝４０，Ｉｔ＝０．４Ｉｔ。ｅｌｉｔｅｒｅｐａｉｒｄｉｖＮＩ表１最左侧展示了Ｇｕｒｏｂｉ求解结果，包括了上界（ＵＢ），下界（ＬＢ）以及反应求解质量的ｇａｐ（数值越小则表明解的质量越高）。表１中间和最右图１回收需求点内损坏单车数量与回收成本的关系侧分别展示了ＧＡ和ＨＧＡ运行２０次求得的结果，以回收需求点１为例论证损坏单车数量对运包括平均目标函数值（Ａｖｇ），最好的解（Ｍｉｎ），相应营成本的影响。在横坐标（损坏单车数量）由０至的ｇａｐ（数值越小则表明解的质量越高）以及终止１０的变化过程中，卡车运输成本呈增加趋势。这时间（ＣＰＵ／ｓ）。是由于中转点存在容量上限，当某个中转点达到容表１算法性能比较ＧｕｒｏｂｉＧＡＨＧＡ算例ＵＢＬＢｇａｐ（％）ＣＰＵ（ｓ）ＡｖｇＭｉｎｇａｐ（％）ＣＰＵ（ｓ）ＡｖｇＭｉｎｇａｐ（％）ＣＰＵ（ｓ）１１１４．９１１４．９００．３３１２２．１１１７．７６．３２１１６．１１１５．３１．１２２１１６．１１１５．３１．１３．４４１１３．１１０７．０１０．４３１０８．２１０４．８５．６３３１４９．５１４１．９５．１７２００１５１．８１４５．５７．０５１４８．３１４３．１４．５５４２５３．３２０８．８１７．６７２００２３６．２２２０．０１１．７５２２６．９２２１．３８．０５５２３４．５１９１．１１８．５７２００２２８．６２０７．１１９．６１０２１８．２２０５．４１４．２１０６３１０．６２０３．９３４．３７２００２６７．９２２５．８３１．４１５２４５．３２１９．６２０．３１５７－－－７２００２２２．１２０９．３－２０２１３．５２０２．１－２０８－－－７２００２４６．７２３１．６－２０２３２．３２２２．４－２０９－－－７２００３０９．６２８７．３－３０２８８．２２８０．２－３０均值－－－５６００．４２１０．９１９４．６－１２．２１９９．７１９０．５－１２．２注１：算例规模由｜Ｋ｜×｜Ｍ｜×｜Ｎ｜确定，算例１至９分别为２×１０×１０，３×１５×１５，４×２０×２０，４×２５×２５，５×２０×２０，５×３０×３０，７×４０×４０，８×４５×４５，１０×５０×５０。注２：Ｇｕｒｏｂｉｇａｐ＝（ＵＢ－ＬＢ）／ＵＢ∗１００％；ＧＡ和ＨＧＡｇａｐ＝（Ａｖｇ－ＬＢ）／Ａｖｇ∗１００％。

5４６运筹与管理２０２３年第３２卷首先，与Ｇｕｒｏｂｉ求解结果进行比较。从算例３ｕｓｅｒｓ’ｗｉｌｌｉｎｇｎｅｓｓｔｏｐａｒｔｉｃｉｐａｔｅｉｎｒｅｐａｉｒｉｎｇｄａｍａｇｅｄｂｉｃｙｃｌｅｓ：ｅｖｉｄｅｎｃｅｆｒｏｍＣｈｉｎａ［Ｊ］．ＴｒａｎｓｐｏｒｔａｔｉｏｎＲｅ⁃至算例６，发现在规定求解时间内Ｇｕｒｏｂｉ只能得到ｓｅａｒｃｈＰａｒｔＡ：ＰｏｌｉｃｙａｎｄＰｒａｃｔｉｃｅ，２０２０，１４１：一个上界和下界，已无法确定最优解。从算例７至２０３⁃２２０．［２］ＳｉＨ，ＳｈｉＪ，ＴａｎｇＤ，ｅｔａｌ．Ｕｎｄｅｒｓｔａｎｄｉｎｇｉｎｔｅｎｔｉｏｎａｎｄ算例９，Ｇｕｒｏｂｉ在规定时间内已无法确定一个上界ｂｅｈａｖｉｏｒｔｏｗａｒｄｓｕｓｔａｉｎａｂｌｅｕｓａｇｅｏｆｂｉｋｅｓｈａｒｉｎｇｂｙｅｘ⁃和下界。对于算例１，ＨＧＡ求解时间比Ｇｕｒｏｂｉ求ｔｅｎｄｉｎｇｔｈｅｔｈｅｏｒｙｏｆｐｌａｎｎｅｄｂｅｈａｖｉｏｒ［Ｊ］．Ｒｅｓｏｕｒｃｅｓ，ＣｏｎｓｅｒｖａｔｉｏｎａｎｄＲｅｃｙｃｌｉｎｇ，２０２０，１５２：１０４５１３．解时间要长，这是由于只要没有达到终止条件，［３］ＷａｎｇＹ，ＳｚｅｔｏＷＹ．ＳｔａｔｉｃｇｒｅｅｎｒｅｐｏｓｉｔｉｏｎｉｎｇｉｎｂｉｋｅＨＧＡ即使找到了最优解也不会终止算法，这是智ｓｈａｒｉｎｇｓｙｓｔｅｍｓｗｉｔｈｂｒｏｋｅｎｂｉｋｅｓ［Ｊ］．ＴｒａｎｓｐｏｒｔａｔｉｏｎＲｅｓｅａｒｃｈＰａｒｔＤ：ＴｒａｎｓｐｏｒｔａｎｄＥｎｖｉｒｏｎｍｅｎｔ，２０１８，６５：能优化算法常见的问题。从算例３至算例６，ＨＧＡ４３８⁃４５７．求解的ｇａｐ与Ｇｕｒｏｂｉ求解的ｇａｐ差距越来越大，这［４］ＫａｓｐｉＭ，ＲａｖｉｖＴ，ＴｚｕｒＭ．Ｂｉｋｅ⁃ｓｈａｒｉｎｇｓｙｓｔｅｍｓ：ｕｓｅｒｄｉｓｓａｔｉｓｆａｃｔｉｏｎｉｎｔｈｅｐｒｅｓｅｎｃｅｏｆｕｎｕｓａｂｌｅｂｉｃｙｃｌｅｓ［Ｊ］．表明ＨＧＡ求解质量显著超过了Ｇｕｒｏｂｉ。从算例７ＩＩＳＥＴｒａｎｓａｃｔｉｏｎｓ，２０１７，４９（２）：１４４⁃１５８．至算例９，相比Ｇｕｒｏｂｉ已无法确定一个可行解，［５］谢凌云．废弃共享单车强制回收制度探析［Ｄ］．上海：华东政法大学，２０１８．ＨＧＡ仍然能在短时间内求得可行解。［６］Ａｌｖａｒｅｚ⁃ＶａｌｄｅｓＲ，ＢｅｌｅｎｇｕｅｒＪＭ，ＢｅｎａｖｅｎｔＥ，ｅｔａｌ．其次，与ＧＡ求解结果进行比较。从算例１至算Ｏｐｔｉｍｉｚｉｎｇｔｈｅｌｅｖｅｌｏｆｓｅｒｖｉｃｅｑｕａｌｉｔｙｏｆａｂｉｋｅ⁃ｓｈａｒｉｎｇｓｙｓｔｅｍ［Ｊ］．Ｏｍｅｇａ，２０１６，６２：１６３⁃１７５．例９，ＨＧＡ全部指标性能均超过ＧＡ。在相同的运算［７］白雪，周支立，钱桂生，等．考虑维修车辆的公共单车时间内，ＨＧＡ平均目标函数值比ＧＡ降低约４．３％，以系统再平衡问题［Ｊ］．系统工程理论与实践，２０１８，３８（９）：２３２６⁃２３３４．ＨＧＡ最好的解数值比ＧＡ平均减少约０．６６％。［８］ＬｉａｎｇＸ，ＳｉＧ，ＪｉａｏＬ，ｅｔａｌ．Ｒｅｃｙｃｌｉｎｇｓｃｈｅｄｕｌｉｎｇｏｆｕｒｂａｎｄａｍａｇｅｄｓｈａｒｅｄｂｉｃｙｃｌｅｓｂａｓｅｄｏｎｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＬｏｇｉｓｔｉｃｓＲｅｓｅａｒｃｈ４结束语ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２０１９，２２（６）：５１９⁃５３２．［９］徐国勋，李妍峰，向婷，等．考虑损坏单车回收的共享单车调度问题［Ｊ］．系统工程，２０１９，３７（２）：９１⁃９９．基于实际中第三方代管参与短距离小批量共［１０］王涵霄，董明，张大力．考虑维修的共享单车调度优享单车回收这一情况，本文提出激励代管员将损坏化研究［Ｊ］．工业工程与管理，２０１９，２４（２）：３１⁃３７．［１１］ＬｕＨ，ＺｈａｎｇＭ，ＳｕＳ，ｅｔａｌ．Ｂｒｏｋｅｎｂｉｋｅｒｅｃｙｃｌｉｎｇ单车从回收需求点运送至附近的中转点，然后派遣ｐｌａｎｎｉｎｇｆｏｒｓｈａｒｉｎｇｂｉｋｅｓｓｙｓｔｅｍ［Ｊ］．ＩＥＥＥＡｃｃｅｓｓ，卡车将这些集中起来的损坏单车从中转点运送至２０１９，７：１７７３５４⁃１７７３６１．［１２］张巍，李鹏翔，仝自强，等．基于损坏车辆分布预测与维修中心。为衡量代管员完成一次任务应获得的损益阈值分析下的共享单车回收研究［Ｊ］．工业工奖励，考虑运送距离、回收需求点损坏单车数量和程，２０２０，２３（３）：１３２⁃１３７．［１３］王中秋．演化博弈视角下废旧共享单车回收合作机对中转点正常业务的影响程度。并把问题建模为制研究［Ｊ］．物流科技，２０２０，４３（６）：６９⁃７５．混合整数规划模型，同时针对问题特征设计了一种［１４］ＨｏＳＣ，ＳｚｅｔｏＷＹ．Ａｈｙｂｒｉｄｌａｒｇｅｎｅｉｇｈｂｏｒｈｏｏｄｓｅａｒｃｈｆｏｒｔｈｅｓｔａｔｉｃｍｕｌｔｉ⁃ｖｅｈｉｃｌｅｂｉｋｅ⁃ｒｅｐｏｓｉｔｉｏｎｉｎｇ改进遗传算法。其中遗传算法用来确定卡车路线ｐｒｏｂｌｅｍ［Ｊ］．ＴｒａｎｓｐｏｒｔａｔｉｏｎＲｅｓｅａｒｃｈＰａｒｔＢ：Ｍｅｔｈｏｄｏ⁃和中转点，嵌入的启发式算法用来确定代管员的路ｌｏｇｉｃａｌ，２０１７，９５：３４０⁃３６３．［１５］ＶｉｄａｌＴ，ＣｒａｉｎｉｃＴＧ，ＧｅｎｄｒｅａｕＭ，ｅｔａｌ．Ａｈｙｂｒｉｄ线和运送数量以及卡车在每个中转点的回收数量。ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｍｕｌｔｉ⁃ｄｅｐｏｔａｎｄｐｅｒｉｏｄｉｃｖｅｈｉｃｌｅ本文通过数值实验论证了所设计算法的高效ｒｏｕｔｉｎｇｐｒｏｂｌｅｍｓ［Ｊ］．ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２０１２，６０（３）：６１１⁃６２４．性，并验证了第三方代管参与的回收策略不仅能够［１６］ＶｉｄａｌＴ，ＣｒａｉｎｉｃＴＧ，ＧｅｎｄｒｅａｕＭ，ｅｔａｌ．Ａｈｙｂｒｉｄｇｅ⁃减轻站点公共空间被损坏单车挤占的问题，还能有ｎｅｔｉｃａｌｇｏｒｉｔｈｍｗｉｔｈａｄａｐｔｉｖｅｄｉｖｅｒｓｉｔｙｍａｎａｇｅｍｅｎｔｆｏｒａｌａｒｇｅｃｌａｓｓｏｆｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍｓｗｉｔｈｔｉｍｅ⁃效减少回收成本，对改进共享单车回收管理（包括提ｗｉｎｄｏｗｓ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２０１３，高回收效率和降低回收成本）具有重要的实际意义。４０（１）：４７５⁃４８９．［１７］ＶｉｄａｌＴ，ＣｒａｉｎｉｃＴＧ，ＧｅｎｄｒｅａｕＭ，ｅｔａｌ．Ａｕｎｉｆｉｅｄｓｏｌｕ⁃未来研究可考虑将本问题扩展到多重图网络中。ｔｉｏｎｆｒａｍｅｗｏｒｋｆｏｒｍｕｌｔｉ⁃ａｔｔｒｉｂｕｔｅｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍｓ［Ｊ］．ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ，２０１４，２３４（３）：６５８⁃６７３．参考文献：［１８］ＬｉＹ，ＳｚｅｔｏＷＹ，ＬｏｎｇＪ，ｅｔａｌ．Ａｍｕｌｔｉｐｌｅｔｙｐｅｂｉｋｅｒｅｐｏｓｉｔｉｏｎｉｎｇｐｒｏｂｌｅｍ［Ｊ］．ＴｒａｎｓｐｏｒｔａｔｉｏｎＲｅｓｅａｒｃｈＰａｒｔＢ：Ｍｅｔｈｏｄｏｌｏｇｉｃａｌ，２０１６，９０：２６３⁃２７８．［１］ＳｉＨ，ＳｕＹ，ＷｕＧ，ｅｔａｌ．Ｕｎｄｅｒｓｔａｎｄｉｎｇｂｉｋｅ⁃ｓｈａｒｉｎｇ