改进分散搜索算法求解包装废弃物回收路径规划问题  

Improved Scatter Search Algorithm to Solve Packaging Waste Recovery Vehicle Routing Problem

作　　者：张琦琪 陈群[1] ZHANG Qiqi;CHEN Qun(Shanghai Publishing and Printing College,Shanghai 200093,China)

机构地区：[1]上海出版印刷高等专科学校,上海200093

出　　处：《包装工程》2024年第9期193-200,共8页Packaging Engineering

基　　金：国家社科基金(18BT058);国家新闻出版署“智能与绿色柔版印刷”重点实验室项目(KLIGFP-01);上海市东方学者特聘教授基金(TP2022126)。

摘　　要：目的将包装废弃物回收路径规划归纳为一个带回路和时间窗的逆向物流车辆路径问题(RL-VRPBTW),以最小化回收成本、发车成本和时间窗惩罚为联合优化目标进行建模。方法引入“车辆剩余空间回收能力”因素,改进经典节约里程算法,求得较好的初始解;基于分散搜索框架,设计基于初始解改进的分散搜索算法(ISISS),根据问题模型,采用含0的编码方式,通过多样性产生、参考集更新、子集产生、子集合并、解改进等5个步骤实现算法功能。结果在“部分回收点分布较密集”的城市型地理场景下,针对快消企业的低值固废包装,生成回收点数量分别为50、100、200的3种规模算例,并考虑大小两种车型进行仿真实验。将ISISS算法与改进节约里程、遗传和分散搜索3种算法比较后可知,ISISS算法在大规模包装废弃物回收车辆路径问题上具有更优的求解性能。结论仿真实验结果表明,ISISS是一种求解多目标大规模包装废弃物回收路径规划问题的较优算法。The work aims to summarize the packaging waste recovery routing as a reverse logistics vehicle routing problem with back path and time window(RL-VRPBTW),so as to construct a model with the minimum recovery cost,departure cost and time window penalty as the joint optimization objective.A better initial solution was obtained by introducing the factor of"vehicle remaining space recovery ability"to improve the classical heuristic C-W algorithm.Based on the Scatter Search framework,a Scatter Search algorithm(ISISS)based on initial solution improvement was designed.According to the problem model,the algorithm functions were realized through five steps of diversity generation method,reference set update method,subset generation,merging method and solution improvement method.In the city-type geographical scenario of"dense distribution of some recovery points",three scale examples with 50,100 and 200 recovery nodes were randomly generated,and two vehicle types were considered for simulation experiments.The ISISS algorithm was compared with C-W,GA and SS algorithms to verify that the algorithm proposed had better performance in solving the routing problem of large-scale packaging waste recovery vehicles.The simulation results indicate that ISISS is a better algorithm to solve the multi-objective large-scale packaging waste recovery routing problem.

关 键 词：逆向物流 带时间窗和回路的车辆路径问题 分散搜索 局部搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TB498[自动化与计算机技术—计算机科学与技术]