基于蚁群选择超启发算法的低碳选址—路径问题
2020-08-06赵燕伟冷龙龙张春苗蒋海青
王 舜,赵燕伟,冷龙龙,张春苗,蒋海青
(浙江工业大学 特种装备制造与先进加工技术教育部重点实验室,浙江 杭州 310014)
0 引言
选址—路径问题(Location-Routing Problem, LRP)是一个经典的组合优化问题,可以看作是配送中心选址分配问题(Location Allocation Problem, LAP)与车辆路径问题(Vehicle Routing Problem, VRP)[1-2]的组合问题,是结合了两个复杂决策问题的NP-hard问题。配送中心选址与客户地理位置、车辆配送路线规划之间的相互依赖关系有利于帮助企业全面协调物流系统的各个环节,以最少成本、最短配送距离等满足客户的需求。
通过考虑现实物流的附加要求和各种路线建设限制,衍生出许多类型的LRP,其中包括带容量约束的LRP(Capacitated LRP, CLRP)[3-7]、带同时取送货的LRP(LRP with Simultaneous Pickup and Delivery, LRPSPD)[8-11]、带时间窗的LRP(LRP with Time Windows, LRPTW)[12-16]、多目标LRP(Multi-Objective LRP, MOLRP)[17-22]等。然而,基本LRP以及衍生出不同类型的LRP大多是以总运行成本为优化目标,少数以最小化配送时间、最大化客户满意度为目标。但是在全球低碳经济以及绿色经济的响应下,大量二氧化碳等温室气体的排放造成了日趋严重的环境污染,因此在物流配送过程中减少二氧化碳气体的排放已成为物流公司不得不解决的问题。基于此,本文提出了低碳选址—路径问题(Low Carbon LRP, LCLRP),并设计了一种基于蚁群选择机制的进化式超启发算法(Hyper-Heuristic algorithm of Ant colony Selection mechanism, HHAS)进行问题模型求解,为物流公司提供参考。据笔者所知,目前尚未有学者将超启发算法用于求解LCLRP,本文采HHAS算法求解LCLRP,将大洪水、模拟退火、只接受好解作为高层自适应接受准则机制,以引导全局搜索并加快收敛。
考虑二氧化碳排放的LRP文献还比较欠缺,但是在VRP中考虑二氧化碳排放以及燃油消耗的文献比较丰富。……
