公共自行车调度路径优化算法
传感器与微系统（ＴｒａｎｓｄｕｃｅｒａｎｄＭｉｃｒｏｓｙｓｔｅｍＴｅｃｈｎｏｌｏｇｉｅｓ）２０１９年第３８卷第１期
ＤＯI：１０．１３８７３／Ｊ．１０００—９７８７（２０１９）０１—０１４４—０４公共自行车调度路径优化算法
马智超，徐海涛
（杭州电子科技大学计算机学院，浙江杭州３１００１８）
摘要：针对如何计算出每次派出的最佳运输车数和每辆运输车的最优路线的问题，提出了一种用于求
解的数学模型，并提出了一种基于改进的混合智能水滴算法。提出了节约算子、启发式算子、最大最小调
制机制、变邻域搜索的融合策略。实验证明：所提出的新算法可以求解所述问题，与其他一些算法相比，求
解效率更高。
关键词：公共自行车调度；混合智能水滴算法；节约算子；变邻域搜索
中图分类号：ＴＵ４９１ 文献标识码：Ａ文章编号：１０００—９７８７（２０１９）０１—０１４４—０４
Alｇｏｒiｔｈｍｆｏｒｓｃｈｅｄｕliｎｇｒｏｕｔｅｏｐｔiｍiｚａｔiｏｎｏｆｐｕｂliｃｂiｃｙｃlｅ
ＭＡＺｈｉ-ｃｈａｏ，ＸＵＨａｉ-ｔａｏ
（ＳｃｈｏｏlｏｆＣｏｍｐｕｔｅｒＳｃiｅｎｃｅ，ＨａｎｇｚｈｏｕＤiａｎｚiＵｎiｖｅｒｓiｔｙ，Ｈａｎｇｚｈｏｕ３１００１８，Ｃｈiｎａ）
Aｂｓｔｒａｃｔ：Ａｉｍｉｎｇａｔｔｈｅｐｒｏｂｌｅｍｔｈａｔｈｏｗｔｏｇｅｔａｓｃｈｅｄｕｌｉｎｇ，ｉｎｃｌｕｄｉｎｇｔｈｅｏｐｔｉｍａｌｎｕｍｂｅｒｏｆｔｒａｎｓｐｏｒｔｅｒｓａｎｄ
ｒｏｕｔｅｓｏｆｅａｃｈｔｒａｎｓｐｏｒｔｅｒ．Ｔｏｓｏｌｖｅｉｔ，ａｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌａｎｄａｈｙｂｒｉｄｉｎｔｅｌｌｉｇｅｎｔｗａｔｅｒｄｒｏｐａｌｇｏｒｉｔｈｍａｒｅ
ｐｒｅｓｅｎｔｅｄ．Ａｌｇｏｒｉｔｈｍｆｕｓｉｏｎｓｔｒａｔｅｇｙｏｆｓａｖｉｎｇｏｐｅｒａｔｏｒ，ｈｅｕｒｉｓｔｉｃｆａｃｔｏｒ，ｍａｘ-ｍｉｎｍｏｄｕｌａｔｉｎｇｍｅｃｈａｎｉｓｍ，ｖａｒｉａｂｌｅ
ｎｅｉｇｈｂｏｒｈｏｏｄｓｅａｒｃｈｉｓｐｒｏｐｏｓｅｄ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓｈｏｗｓｔｈａｔｔｈｅｎｅｗａｌｇｏｒｉｔｈｍｃａｎｓｏｌｖｅｔｈｅａｂｏｖｅｐｒｏｂｌｅｍａｎｄｉｔ
ｉｓｍｏｒｅｅｆｆｅｃｔｉｖｅｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｔｈａｎｏｔｈｅｒａｌｇｏｒｉｔｈｍｓ．
Ｋｅｙｗｏｒｄｓ：ｓｃｈｅｄｕｌｉｎｇｏｆｐｕｂｌｉｃｂｉｃｙｃｌｅ；ｈｙｂｒｉｄｉｎｔｅｌｌｉｇｅｎｔｗａｔｅｒｄｒｏｐａｌｇｏｒｉｔｈｍ；ｓａｖｉｎｇｏｐｅｒａｔｏｒ；ｖａｒｉａｂｌｅ
ｎｅｉｇｈｂｏｒｈｏｏｄｓｅａｒｃｈ
０ 引言
研究公共自行车调度路径优化问题对提高市民对公共自行车使用的满意度，缓解交通拥堵，绿色出行具有重大意义。目前已经有一些人对该问题进行了研究，但相应的模型和算法还需要改进。文献［１，２］模型的优化目标只考虑了油费，文献［３］的模型考虑了用户的满意度，分别提出软时间窗和硬时间窗模型。为了求解自行车调度问题，文献［４］提出了改进的遗传算法，文献［５］提出了自适应遗传算法，文献［６］提出了用改进的蚁群算法，文献［７］提出了模拟退火算法。这类算法均容易陷入停滞。智能水滴算法在短时间内可以得到更优的解，并在多个领域得到验证，文献［８］用其求解旅行商问题（ＴＳＰ），文献［９，１０］用其求解车辆路径问题，但该算法本身也具有陷入停滞特点。变邻域搜索具有很强的搜索能力，从文献［１１，１２］可以看出，如果变邻域搜索有一个合适的领域结构和较优的初始解，其效率将会大大提高。为此本文将二者融合。
本文提出了一种带有混合时间窗的数学模型，既考虑了用户的满意度又考虑了调度成本。提出了一种混合智收稿日期：２０１７—１１—２２能水滴算法，与变邻域搜索融合，提出了两种适用于路径优化问题的邻域结构，提出了节约算子、启发式因子和最大最小调制的改进策略。仿真对比实验验证了算法的有效性。１ 问题描述与构建数学模型
１．１ 问题描述
假设有不同的工作区域，每个工作区域都有一个调度中心用于管理属于同一区域的自行车站点。系统会一直检查站点的状态，看是否需要调度。系统会计算出相应的需求，包含这个站点需要调度的自行车数量，最佳调度服务时间以及运输车和各个站点的位置信息。如何根据这些信息来计算调度方案，是本文要研究的问题。调度方案包括需要派出几辆运输车、每辆运输车的行驶路线。
１．２ 构建数学模型
假设有１个调度中心（｛０｝），公共自行车租赁站点Ｎ＝｛ｓ１，ｓ２，…，ｓＮ｝，需要Ｋ个运输车，每个最多可载Ｑ辆自行车；运输车到达站点ｓｉ的时刻为ｔｉ；从站点ｓｉ到ｓｊ所需要的时间为ｔｉｊ（ｓ），路程为ｄｉｊ（ｋｍ）。ｗｉｊ是运输车从ｓｉ到ｓｊ运行过程中装载的自行车数量，ｗｉ是在站点ｓｉ的等待时间。定义Ｃｗ为每秒给工作人员的薪资，Ｃｐ为单位里程的油费，
４４１
万方数据