基于物流配送路线规划的改进型果蝇优化算法
|
摘要
针对物流业普遍关注的物流配送路线规划问题,以配送路程为性能指标并结合配送点之间是否可直接通行的实际因素,获得0-1规划模型。在基本果蝇优化算法中,引入基因互换和最大保留交叉操作增强果蝇种群的多样性,借助基因逆位操作和邻域探测策略搜索优质果蝇,获得计算复杂度依赖于种群规模和配送点数的改进型果蝇优化算法。比较性的数值实验和工程应用结果表明,该算法在搜索效果与稳定性、收敛速度及获得的配送路线方案的合理性方面具有明显优势。
Aiming at the actual factor that whether any two distribution points can arrive to each other,one 0-1 programming model with the objective function of distribution route was modeled to formulate the hot problem of logistics distribution route planning.An improved fruit fly optimization algorithm was developed to seek the optimal route planning scheme,in which the modules of gene exchange and maximum saving crossover were used to strength the diversity of fruit fly population and also those of gene inversion and neighbor exploitation were cited to seek elitist fruit flies.Its computational complexity depended mainly on the sizes of fruit flies and distribution points.Numerically comparative experimental results show that the proposed algorithm clearly performs well over the compared approaches in terms of performance effect,search stability,convergence speed,and the rationality of the acquired logistics distribution scheme.
Aiming at the actual factor that whether any two distribution points can arrive to each other,one 0-1 programming model with the objective function of distribution route was modeled to formulate the hot problem of logistics distribution route planning.An improved fruit fly optimization algorithm was developed to seek the optimal route planning scheme,in which the modules of gene exchange and maximum saving crossover were used to strength the diversity of fruit fly population and also those of gene inversion and neighbor exploitation were cited to seek elitist fruit flies.Its computational complexity depended mainly on the sizes of fruit flies and distribution points.Numerically comparative experimental results show that the proposed algorithm clearly performs well over the compared approaches in terms of performance effect,search stability,convergence speed,and the rationality of the acquired logistics distribution scheme.
引文
[1]Song L,Gu H,Huang H.A lower bound for the adaptive two-echelon capacitated vehicle routing problem[J].Journal of Combinatorial Optimization,2017,33(4):1-23.
[2]ZHU Jiaxiang,TAN Qingmei,CAI Jianfei,et al.Emergency logistics distribution strategy based on double uncertainty[J].System Engineering,2016,34(3):1-8(in Chinese).[朱佳翔,谭清美,蔡建飞,等.基于双重不确定性的应急物流配送策略[J].系统工程,2016,34(3):1-8.]
[3]ZHOU Xiang,XU Maozeng,LQiguang.Two-stage layout optimization model for distribution center and terminal node under B2C mode[J].Computer Integrated Manufacturing Systems,2014,20(12):3140-3149(in Chinese).[周翔,许茂增,吕奇光.B2C模式下配送中心与末端节点的两阶段布局优化模型[J].计算机集成制造系统,2014,20(12):3140-3149.]
[4]Wu S,Yao J.Optimization of cold-chain logistics distribution path based on Dijkstra algorithm[J].Boletin Tecnico/Technical Bulletin,2017,55(7):439-444.
[5]REN Pengfei,QIN Guihe,DONG Jinnan,et al.Improved Dijkstra algorithm with traffic rule constraints[J].Journal of Computer Applications,2015,35(9):2503-2507(in Chinese).[任鹏飞,秦贵和,董劲男,等.具有交通规则约束的改进Dijkstra算法[J].计算机应用,2015,35(9):2503-2507.]
[6]JIA Xianzhao,QI Hengliang,JIA Qisu,et al.Optimization of distribution route of fresh agricultural products in the same city under real-time road conditions[J].Jiangsu Agricultural Sciences,2017,45(17):292-295(in Chinese).[贾现召,戚恒亮,贾其苏,等.实时路况下同城生鲜农产品配送路径优化[J].江苏农业科学,2017,45(17):292-295.]
[7]SONG Juan,CUI Yan.A city express delivery model based on improved genetic algorithm[J].Electronic Technology Application,2014,40(12):136-139(in Chinese).[宋娟,崔艳.基于改进遗传算法的同城快递配送模型[J].电子技术应用,2014,40(12):136-139.]
[8]LUO Qing,ZHOU Jun.Optimization of agricultural product logistics distribution route based on hybrid genetic algorithm[J].Jiangsu Agricultural Sciences,2017,45(12):174-177(in Chinese).[罗庆,周军.基于混合遗传算法的农产品物流配送路径优化[J].江苏农业科学,2017,45(12):174-177.]
[9]DENG Binian.Study on logistics distribution route based on ant colony optimization algorithm[J].Modern Electronics Technique,2017,40(15):167-170(in Chinese).[邓必年.基于蚁群优化算法的物流配送路径研究[J].现代电子技术,2017,40(15):167-170.]
[10]Yu M,Yue G,Lu Z,et al.Logistics terminal distribution mode and path optimization based on ant colony algorithm[J].Wireless Personal Communications,2018,102(4):1-17.
[11]YU Cheng,CAO Qian,WANG Shimin.The simulation of logistics vehicle routing planning[J].Computer Simulation,2016,33(8):359-364(in Chinese).[余成,曹倩,王世民.关于物流系统车辆配送路径规划仿真[J].计算机仿真,2016,33(8):359-364.]
[12]Zhang K,Qiu B,Mu D.Low-carbon logistics distribution route planning with improved particle swarm optimization algorithm[C]//International Conference on Logistics.Sydney:Informatics and Service Sciences.IEEE,2017:1-4.
[13]CHEN Jiumei.Solving two-echelon location-routing problem by artificial fish swarm algorithm[J].Computer Engineering and Design,2014,35(7):2520-2525(in Chinese).[陈久梅.求解两级定位-路径问题的人工鱼群算法[J].计算机工程与设计,2014,35(7):2520-2525.]
[14]MA Xiangli,ZHANG Huizhen,MA Liang.Application of bat algorithm in vehicle routing problem of logistics distribution[J].Mathematics in Practics and Theory,2015,45(24):80-86(in Chinese).[马祥丽,张惠珍,马良.蝙蝠算法在物流配送车辆路径优化问题中的应用[J].数学的实践与认识,2015,45(24):80-86.]
[15]HAO Juan,ZHANG Zhuhong,TU Xin.RSSI localization in noisy environment and its fruit fly optimization algorithm[J].Computer Engineering and Applications,2018,54(7):121-126(in Chinese).[郝娟,张著洪,凃歆.噪声环境下RSSI定位问题及其求解的果蝇优化算法[J].计算机工程与应用,2018,54(7):121-126.]
[16]CAO Qian,SHAO Juping,SUN Yan’an.Multi-objective fresh agricultural product distribution path optimization based on improved genetic algorithm[J].Industrial Engineering Journal,2015,18(1):71-76(in Chinese).[曹倩,邵举平,孙延安.基于改进遗传算法的生鲜农产品多目标配送路径优化[J].工业工程,2015,18(1):71-76.]
[17]ZHAN Xiaolong.Genetic algortithm for vehicle routing problem with time windows[D].Nanchang:Jiangxi University of Science and Technology,2014:8-13(in Chinese).[詹孝龙.遗传算法在带时间窗的车辆路径问题中的应用[D].南昌:江西理工大学,2014:8-13.]
[18]JIANG Kunlin,LI Mei’an,ZHANG Hongwei.Improved ant colony algorithm for travelling salesman problem[J].Journal of Computer Applications,2015,35(S2):114-117(in Chinese).[姜坤霖,李美安,张宏伟.面向旅行商问题的蚁群算法改进[J].计算机应用,2015,35(S2):114-117.]
[19]ZHANG Yong,CHEN Ling,XU Xiaolong,et al.Rresearch on time optimal TSP based on hybrid PSO-GA[J].Application Research of Computer,2015,32(12):3613-3617(in Chinese).[张勇,陈玲,徐小龙,等.基于PSO-GA混合算法时间优化的旅行商问题研究[J].计算机应用研究,2015,32(12):3613-3617.]
[20]FAN Yingying.Research on the site selection of power supplies distribution center based on improved ICA[D].Beijing:North China Electric Power University,2017:29-43(in Chinese).[范莹莹.基于改进ICA算法的电力物资配送中心选址研究[D].北京:华北电力大学,2017:29-43.]
[2]ZHU Jiaxiang,TAN Qingmei,CAI Jianfei,et al.Emergency logistics distribution strategy based on double uncertainty[J].System Engineering,2016,34(3):1-8(in Chinese).[朱佳翔,谭清美,蔡建飞,等.基于双重不确定性的应急物流配送策略[J].系统工程,2016,34(3):1-8.]
[3]ZHOU Xiang,XU Maozeng,LQiguang.Two-stage layout optimization model for distribution center and terminal node under B2C mode[J].Computer Integrated Manufacturing Systems,2014,20(12):3140-3149(in Chinese).[周翔,许茂增,吕奇光.B2C模式下配送中心与末端节点的两阶段布局优化模型[J].计算机集成制造系统,2014,20(12):3140-3149.]
[4]Wu S,Yao J.Optimization of cold-chain logistics distribution path based on Dijkstra algorithm[J].Boletin Tecnico/Technical Bulletin,2017,55(7):439-444.
[5]REN Pengfei,QIN Guihe,DONG Jinnan,et al.Improved Dijkstra algorithm with traffic rule constraints[J].Journal of Computer Applications,2015,35(9):2503-2507(in Chinese).[任鹏飞,秦贵和,董劲男,等.具有交通规则约束的改进Dijkstra算法[J].计算机应用,2015,35(9):2503-2507.]
[6]JIA Xianzhao,QI Hengliang,JIA Qisu,et al.Optimization of distribution route of fresh agricultural products in the same city under real-time road conditions[J].Jiangsu Agricultural Sciences,2017,45(17):292-295(in Chinese).[贾现召,戚恒亮,贾其苏,等.实时路况下同城生鲜农产品配送路径优化[J].江苏农业科学,2017,45(17):292-295.]
[7]SONG Juan,CUI Yan.A city express delivery model based on improved genetic algorithm[J].Electronic Technology Application,2014,40(12):136-139(in Chinese).[宋娟,崔艳.基于改进遗传算法的同城快递配送模型[J].电子技术应用,2014,40(12):136-139.]
[8]LUO Qing,ZHOU Jun.Optimization of agricultural product logistics distribution route based on hybrid genetic algorithm[J].Jiangsu Agricultural Sciences,2017,45(12):174-177(in Chinese).[罗庆,周军.基于混合遗传算法的农产品物流配送路径优化[J].江苏农业科学,2017,45(12):174-177.]
[9]DENG Binian.Study on logistics distribution route based on ant colony optimization algorithm[J].Modern Electronics Technique,2017,40(15):167-170(in Chinese).[邓必年.基于蚁群优化算法的物流配送路径研究[J].现代电子技术,2017,40(15):167-170.]
[10]Yu M,Yue G,Lu Z,et al.Logistics terminal distribution mode and path optimization based on ant colony algorithm[J].Wireless Personal Communications,2018,102(4):1-17.
[11]YU Cheng,CAO Qian,WANG Shimin.The simulation of logistics vehicle routing planning[J].Computer Simulation,2016,33(8):359-364(in Chinese).[余成,曹倩,王世民.关于物流系统车辆配送路径规划仿真[J].计算机仿真,2016,33(8):359-364.]
[12]Zhang K,Qiu B,Mu D.Low-carbon logistics distribution route planning with improved particle swarm optimization algorithm[C]//International Conference on Logistics.Sydney:Informatics and Service Sciences.IEEE,2017:1-4.
[13]CHEN Jiumei.Solving two-echelon location-routing problem by artificial fish swarm algorithm[J].Computer Engineering and Design,2014,35(7):2520-2525(in Chinese).[陈久梅.求解两级定位-路径问题的人工鱼群算法[J].计算机工程与设计,2014,35(7):2520-2525.]
[14]MA Xiangli,ZHANG Huizhen,MA Liang.Application of bat algorithm in vehicle routing problem of logistics distribution[J].Mathematics in Practics and Theory,2015,45(24):80-86(in Chinese).[马祥丽,张惠珍,马良.蝙蝠算法在物流配送车辆路径优化问题中的应用[J].数学的实践与认识,2015,45(24):80-86.]
[15]HAO Juan,ZHANG Zhuhong,TU Xin.RSSI localization in noisy environment and its fruit fly optimization algorithm[J].Computer Engineering and Applications,2018,54(7):121-126(in Chinese).[郝娟,张著洪,凃歆.噪声环境下RSSI定位问题及其求解的果蝇优化算法[J].计算机工程与应用,2018,54(7):121-126.]
[16]CAO Qian,SHAO Juping,SUN Yan’an.Multi-objective fresh agricultural product distribution path optimization based on improved genetic algorithm[J].Industrial Engineering Journal,2015,18(1):71-76(in Chinese).[曹倩,邵举平,孙延安.基于改进遗传算法的生鲜农产品多目标配送路径优化[J].工业工程,2015,18(1):71-76.]
[17]ZHAN Xiaolong.Genetic algortithm for vehicle routing problem with time windows[D].Nanchang:Jiangxi University of Science and Technology,2014:8-13(in Chinese).[詹孝龙.遗传算法在带时间窗的车辆路径问题中的应用[D].南昌:江西理工大学,2014:8-13.]
[18]JIANG Kunlin,LI Mei’an,ZHANG Hongwei.Improved ant colony algorithm for travelling salesman problem[J].Journal of Computer Applications,2015,35(S2):114-117(in Chinese).[姜坤霖,李美安,张宏伟.面向旅行商问题的蚁群算法改进[J].计算机应用,2015,35(S2):114-117.]
[19]ZHANG Yong,CHEN Ling,XU Xiaolong,et al.Rresearch on time optimal TSP based on hybrid PSO-GA[J].Application Research of Computer,2015,32(12):3613-3617(in Chinese).[张勇,陈玲,徐小龙,等.基于PSO-GA混合算法时间优化的旅行商问题研究[J].计算机应用研究,2015,32(12):3613-3617.]
[20]FAN Yingying.Research on the site selection of power supplies distribution center based on improved ICA[D].Beijing:North China Electric Power University,2017:29-43(in Chinese).[范莹莹.基于改进ICA算法的电力物资配送中心选址研究[D].北京:华北电力大学,2017:29-43.]