基于双层禁忌搜索算法的共享单车再平衡问题
来源：计算机集成制造系统杂志2020年第12期北京时间：
作者：吕畅,张超勇,张道德,任亚平,孟磊磊
单位：1.华中科技大学数字制造装备与技术国家重点实验室2.湖北工业大学机械工程学院3.聊城大学计算机学院
摘要：共享单车系统需解决各个共享站点的供需平衡,这是一个复杂的NP-hard问题。针对共享单车系统的特点,提出一种基于供需关系的站点分块策略,并结合所提模型设计了相应的双层禁忌搜索算法进行求解。供需关系分块策略通过不足站点和过饱和站点之间的配对形成能自给自足的站点集;双层禁忌搜索算法分别基于分块站点集和站点集内部进行双层禁忌搜索,并通过一个嵌套变异算子,增强两层搜索间的信息交流,在提高算法搜索能力的同时增添解的多样性。应用提出算法求解共享单车再平衡国际基准实例,实验结果显示提出算法能在100s内获得150站点以内的较优解,降低作业周转库存80%以上,同时减少作业所需货车数至5辆以内。与同类算法对比,在目标函数求解结果和算法求解时间上均表现出显著优越性。
关键词：共享单车再平衡问题,供需关系,禁忌搜索,变异算子
基金资助：国家自然科学基金面上资助项目(51575211,51775238,51805330,51705263);浙江省基金青年科学基金资助项目(LQ16G010002)。
