求解开放式选址路径问题的离散烟花算法

A Discrete Fireworks Algorithm for Solving Open Location Routing Problem

在现代供应链管理中,确定仓库地址与设计车辆配送路线至关重要,对仓库和配送路线的合理决策不仅可以节约配送成本和时间,而且可提高企业竞争能力。将时间窗约束和同时取送货约束加入到开放式选址路径问题中,提出一种更具有实际应用背景的开放式选址路径问题,并以最小化仓库开放成本、配送成本、固定车辆车本、惩罚成本之和为目标构建问题数学模型。针对该数学模型,设计一种新型离散烟花算法,使用贪婪策略构建初始种群以提高初始解质量,基于交叉、逆转、插入操作重新定义爆炸算子和变异算子,同时加入自适应策略控制收敛速度。最后,通过应用离散烟花算法求解一系列算例,验证模型和算法有效性和可行性。相较于CPLEX与模拟退火算法,离散烟花算法可在平均21.48s内求得18组算例中17组最优解,求解效率提升了近800%,具有寻优效果好、求解效率高的优点。

In modern supply chain management,it is vital to determine the warehouse address and design the vehicle distribution route.Reasonable decision on the warehouse and distribution route can not only save the distribution cost and time,but also improve the competitiveness of enterprises.In this paper,the time windows constraint and simultaneous pickup-delivery constraint are added into the open capacitated location routing problem,and an open capacitated location routing problem with more practical application background is proposed.The mathematical model of the problem is constructed with the objective of minimizing the sum of the open warehouse cost,distribution cost,fixed vehicle cost and penalty cost.Aiming at the proposed mathematical model,a new discrete fire⁃work algorithm is designed,which uses greedy strategy to construct initial population to improve the quality of initial solution,rede⁃fines explosion operator and mutation operator based on crossover,reversal and insertion operation,and adds adaptive strategy to con⁃trol the convergence rate.Finally,the validity and feasibility of the model and algorithm are verified by solving a series of examples with discrete fireworks algorithm.Compared with CPLEX and simulated annealing algorithm,the discrete fireworks algorithm can ob⁃tain the optimal solution of 17 of the 18 groups of examples within 21.48 seconds on average,and the solving efficiency is improved by 799.95%,which has the advantages of good optimization effect and high solving efficiency.