面向双目标应急物资调度的改进差分进化算法
|
摘要
本文对应急物资调度模型的建立及求解该模型的优化算法进行了研究.首先,在资源受限情况下,以配送费用总成本最小和最大缺失损失最小为优化目标,建立了连续消耗问题的多供应点对多受灾点的应急物资调度模型.然后,通过引入DE/best/1变异策略与DE/rand/2变异策略对差分进化算法进行了改进,提出了一种基于双变异策略的改进差分进化算法,将Pareto非支配等级分层与拥挤距离的概念引入到改进差分进化算法中,对约束双目标调度模型进行求解.最后,通过两种不同规模的四组仿真实验,验证了本文提出模型及改进的差分进化算法的可行性和有效性.与基本差分进化算法对比,双变异策略的改进差分进化算法对相同应急物资调度问题进行求解时,得到了更多的Pareto前沿解个数,和较低的应急物资调度配送费用成本与较小的最大缺失损失,同时解分布的广泛性也得到了显著提高.
We aim to establish a suitable emergency material scheduling model and optimize a differential evolution algorithm to solve the model. Under the condition of limited resources,this model aims to obtain the minimum total cost of delivery and the maximum reduction of disaster sites about continuous consumption,considering multiple supply points and multiple disaster points. According to the concept of Pareto domination and crowding distance,differential evolution algorithm has been used to solve constraint and bi-objective models. We optimize a differential evolution algorithm by combining DE/best/1 variation strategy and DE/rand/2 variation strategy to form an improved algorithm involving a double-mutation strategy,which increases the algorithm' s scapability. Our simulation test proves that the model and the algorithm are feasible and effective. According to comparison results involving big and small scale examples,the proposed algorithm can decrease the total delivery cost of emergency resource scheduling and obtain the maximum reduction of the disaster sites. Meanwhile,this improved algorithm increases the quantity of the Pareto non-dominated front solutions and increases extension distribution of the solutions.
We aim to establish a suitable emergency material scheduling model and optimize a differential evolution algorithm to solve the model. Under the condition of limited resources,this model aims to obtain the minimum total cost of delivery and the maximum reduction of disaster sites about continuous consumption,considering multiple supply points and multiple disaster points. According to the concept of Pareto domination and crowding distance,differential evolution algorithm has been used to solve constraint and bi-objective models. We optimize a differential evolution algorithm by combining DE/best/1 variation strategy and DE/rand/2 variation strategy to form an improved algorithm involving a double-mutation strategy,which increases the algorithm' s scapability. Our simulation test proves that the model and the algorithm are feasible and effective. According to comparison results involving big and small scale examples,the proposed algorithm can decrease the total delivery cost of emergency resource scheduling and obtain the maximum reduction of the disaster sites. Meanwhile,this improved algorithm increases the quantity of the Pareto non-dominated front solutions and increases extension distribution of the solutions.
引文
[1]高淑萍,刘三阳.应急系统调度问题的最优决策[J].系统工程与电子技术,2003,25(10):1222-1224.Gao S P,Liu S Y. Research optimal decision for scheduling problem in emergency systems[J]. Systems Engineering and Electronics,2013,25(10):1222-1224.
[2]郭子雪,郭亮,张培,等.应急物资调度时间最小化模糊优化模型[J].中国安全科学学报,2015,25(10):172-176.Guo Z X,Guo L,Zhang P,et al. Time minimization model for emergency material dispatching based on triangle fuzzy information[J]. ChinaSafety Science Journal,2015,25(10):172-176.
[3] Karaboga D,Basturk B. A powerful and efficient algorithm for numerical function optimization artificial bee colony algorithm[J]. Journal ofGlobal Optimization,2007,39(3):459-471.
[4]赵明,宋晓宇,常春光.改进人工蜂群算法及其在应急调度优化问题中的应用[J].计算机应用研究,2016,33(12):3596-3601.Zhao M,Song X Y,Chang C G. Improved artificial bee colony algorithm and its application on optimization of emergency scheduling[J]. Ap-plication Research of Computers,2016,33(12):3596-3601.
[5]宋晓宇,张卿,常春光.求解双层应急物资调度的改进蜂群算法[J].信息与控制,2016,44(6):729-738.Song X Y,Zhang Q,Chang C G. Improved bee colony algorithm for solving double layer emergency resource scheduling[J]. Information andControl,2016,44(6):729-738.
[6]于小兵.基于改进粒子群算法的多目标应急物资调度[J].工业工程,2014,17(3):18-22.Yu X B. Multi-objective emergency supplies scheduling based on improved particle swarm optimization[J]. Industrial Engineering Journal,2014,17(3):18-22.
[7] Zdamar L,Ekinci E,Kücükyazici B. Emergency logistics planning in natural disasters[J]. Annals of Operation Research,2004,129(1):218-219.
[8]郑斌,马祖军,李双琳.基于双层规划的震后初期应急物流系统优化[J].系统工程学报,2014,29(1):113-125.Zheng B,Ma Z J,Li S L. Integrated optimization of emergency logistics systems frost-earthquake initial stage based on bi-level programming[J]. Journal of Systems Engineering,2014,29(1):113-125.
[9]李进,张江华,朱道立.灾害链中多资源应急调度模型和算法[J].系统工程理论与实践,2011,31(3):488-495.Li J,Zhang J H,Zhu D L. Multi-resource emergency scheduling model and algorithm in disaster chain[J]. Systems Engineering:Theory&Practice,2011,31(3):488-495.
[10]李守英,马祖军,郑斌,等.洪灾被困人员搜救问题的集成优化研究[J].系统工程学报,2012,27(3):287-294.Li S Y,Ma Z J,Zheng B,et al. Integrated optimization of searching for trapped personnel in flood disaster[J]. Journal of System Engineer-ing,2012,27(3):287-294.
[11]Vicente L,Savard G,Judice J. Descent approaches for quadratic bi-level programming[J]. Journal of Optimization Theory and Applications,1994,81(2):379-399.
[12]但兵兵,朱万红,桑杨阳.需求可拆分的应急物资调度问题的蚁群算法[J].指挥控制与仿真,2013,35(4):81-83.Dan B B,Zhu W H,Sang Y Y. Ant colony optimization algorithm for split routing problem of dispatching emergency materials[J]. CommandControl&Simulation,2013,35(4):81-83.
[13]Yuan Y,Wang D W. Path selection model and algorithm for emergency logistics management[J]. Science Direct,Computers&Industrial En-gineering,2009,10(56):1081-1094.
[14]Afshar A,Haghani A. Modeling integrated supply chain logistics in real-time large-scale disaster relief operations[J]. Socioeconomic PlanningSciences,2012,46(4):327-338.
[15]Storn R,Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of GlobalOptimization,1997,11(4):341-359.
[16]Fan H Y,Lampinen J. A trigonometric mutation operation to differential evolution[J]. Journal of Global Optimization,2003,27(1):105-129.
[17]Zhang J,Sanderson A C. JADE:Adaptive differential evolution with optional external archive[J]. IEEE Transactions on Evolutionary Compu-tation,2009,13(5):945-958.
[18]Deb K,Pratap A,Agarwal S,et al. A fast and elitist multi-objective genetic algorithm:NSGA-II[J]. IEEE Transactions on EvolutionaryComputation,2002,6(2):182-197.
[19]Li H,Zhang Q F. Multi-objective optimization problems with complicated Pareto sets,MOEA/D and NSGA-II[J]. IEEE Transaction on Evo-lutionary Computation,2009,13(2):284-302.
[20]Zitzler E,Deb K,Thiele L. Comparison of multi-objective evolutionary algorithms:Empirical results[J]. Evolutionary Computation,2000,8(2):173-195.
[2]郭子雪,郭亮,张培,等.应急物资调度时间最小化模糊优化模型[J].中国安全科学学报,2015,25(10):172-176.Guo Z X,Guo L,Zhang P,et al. Time minimization model for emergency material dispatching based on triangle fuzzy information[J]. ChinaSafety Science Journal,2015,25(10):172-176.
[3] Karaboga D,Basturk B. A powerful and efficient algorithm for numerical function optimization artificial bee colony algorithm[J]. Journal ofGlobal Optimization,2007,39(3):459-471.
[4]赵明,宋晓宇,常春光.改进人工蜂群算法及其在应急调度优化问题中的应用[J].计算机应用研究,2016,33(12):3596-3601.Zhao M,Song X Y,Chang C G. Improved artificial bee colony algorithm and its application on optimization of emergency scheduling[J]. Ap-plication Research of Computers,2016,33(12):3596-3601.
[5]宋晓宇,张卿,常春光.求解双层应急物资调度的改进蜂群算法[J].信息与控制,2016,44(6):729-738.Song X Y,Zhang Q,Chang C G. Improved bee colony algorithm for solving double layer emergency resource scheduling[J]. Information andControl,2016,44(6):729-738.
[6]于小兵.基于改进粒子群算法的多目标应急物资调度[J].工业工程,2014,17(3):18-22.Yu X B. Multi-objective emergency supplies scheduling based on improved particle swarm optimization[J]. Industrial Engineering Journal,2014,17(3):18-22.
[7] Zdamar L,Ekinci E,Kücükyazici B. Emergency logistics planning in natural disasters[J]. Annals of Operation Research,2004,129(1):218-219.
[8]郑斌,马祖军,李双琳.基于双层规划的震后初期应急物流系统优化[J].系统工程学报,2014,29(1):113-125.Zheng B,Ma Z J,Li S L. Integrated optimization of emergency logistics systems frost-earthquake initial stage based on bi-level programming[J]. Journal of Systems Engineering,2014,29(1):113-125.
[9]李进,张江华,朱道立.灾害链中多资源应急调度模型和算法[J].系统工程理论与实践,2011,31(3):488-495.Li J,Zhang J H,Zhu D L. Multi-resource emergency scheduling model and algorithm in disaster chain[J]. Systems Engineering:Theory&Practice,2011,31(3):488-495.
[10]李守英,马祖军,郑斌,等.洪灾被困人员搜救问题的集成优化研究[J].系统工程学报,2012,27(3):287-294.Li S Y,Ma Z J,Zheng B,et al. Integrated optimization of searching for trapped personnel in flood disaster[J]. Journal of System Engineer-ing,2012,27(3):287-294.
[11]Vicente L,Savard G,Judice J. Descent approaches for quadratic bi-level programming[J]. Journal of Optimization Theory and Applications,1994,81(2):379-399.
[12]但兵兵,朱万红,桑杨阳.需求可拆分的应急物资调度问题的蚁群算法[J].指挥控制与仿真,2013,35(4):81-83.Dan B B,Zhu W H,Sang Y Y. Ant colony optimization algorithm for split routing problem of dispatching emergency materials[J]. CommandControl&Simulation,2013,35(4):81-83.
[13]Yuan Y,Wang D W. Path selection model and algorithm for emergency logistics management[J]. Science Direct,Computers&Industrial En-gineering,2009,10(56):1081-1094.
[14]Afshar A,Haghani A. Modeling integrated supply chain logistics in real-time large-scale disaster relief operations[J]. Socioeconomic PlanningSciences,2012,46(4):327-338.
[15]Storn R,Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of GlobalOptimization,1997,11(4):341-359.
[16]Fan H Y,Lampinen J. A trigonometric mutation operation to differential evolution[J]. Journal of Global Optimization,2003,27(1):105-129.
[17]Zhang J,Sanderson A C. JADE:Adaptive differential evolution with optional external archive[J]. IEEE Transactions on Evolutionary Compu-tation,2009,13(5):945-958.
[18]Deb K,Pratap A,Agarwal S,et al. A fast and elitist multi-objective genetic algorithm:NSGA-II[J]. IEEE Transactions on EvolutionaryComputation,2002,6(2):182-197.
[19]Li H,Zhang Q F. Multi-objective optimization problems with complicated Pareto sets,MOEA/D and NSGA-II[J]. IEEE Transaction on Evo-lutionary Computation,2009,13(2):284-302.
[20]Zitzler E,Deb K,Thiele L. Comparison of multi-objective evolutionary algorithms:Empirical results[J]. Evolutionary Computation,2000,8(2):173-195.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |