基于遗传算法的多目标货物配载研究

doi:10.3969/j.issn.1000-5641.2021.05.016

摘要/Abstract

摘要：

针对多目标货物配载问题, 建立了以最大化总订单货物重量、最小化车次总数、最小化货物装卸地总数为目标的配载模型, 提出了一种快速收敛的基于精英策略多目标遗传算法(Fast Convergence Based on the Elitism Genetic Algorithm, FEGA). 首先, 在遗传算法的基础上加入Pareto支配关系上的分层结构和精英保留策略, 从而提高种群的多样性, 同时还可以加快算法的局部搜索能力; 其次, 修改初始种群的随机结构, 并加入双种群策略, 添加自适应操作算子, 依次提高算法的全局搜索能力, 加速种群的收敛速度; 最后, 基于新算法, 利用真实的货物数据验证算法的可行性与优化效果. 结果表明, 与传统遗传算法相比, 所提算法在求解强约束条件、庞大搜索空间的货物配载过程中具有较好的优化效果, 搜索性能与收敛性都有所提升.

关键词: 多目标优化, 货物配载, 遗传算法

Abstract:

In this paper, we propose a mathematical model to solve the multi-objective cargo allocation problem with greater stability and efficiency; the model for cargo allocation maximizes the total cargo weight, minimizes the total number of trips, minimizes the number of cargo loading and unloading points, and offers fast convergence based on the elitism genetic algorithm (FEGA). First, a hierarchical structure with the Pareto dominance relation and an elitism retention strategy were added on the basis of the genetic algorithm. This helped to improve the population diversity while accelerating the local search ability of the algorithm. Then, the random structure of the initial population was modified, and a double population strategy was designed. An adaptive operation was subsequently added to sequentially improve the global search ability of the algorithm and accelerate the convergence speed of the population. Based on the new algorithm, real cargo data were used to demonstrate the feasibility and optimization potential of the new method. The results show that compared with the traditional genetic algorithm, the proposed algorithm has a better optimization effect in solving the cargo allocation process with strong constraints and a large search space; the search performance and convergence, moreover, are also improved.

Key words: multi-objective optimization, cargo allocation, genetic algorithm

中图分类号:

TP311

于萍, 胡卉芪, 钱卫宁. 基于遗传算法的多目标货物配载研究[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 185-198.

Ping YU, Huiqi HU, Weining QIAN. Research on multi-objective cargo allocation based on an improved genetic algorithm[J]. Journal of East China Normal University(Natural Science), 2021, 2021(5): 185-198.

图/表 9

图1

图2

图3

图4

表1

图5

图6

表2

图7

参考文献 27

1	TIMOTHY R, JASBIR S. The weighted sum method for multi-objective optimization: New insights. Structural and Multidisciplinary Optimization, 2010, 41 (6): 853- 862. doi: 10.1007/s00158-009-0460-7
2	PINCHERA D, PERNA S, MIGLIORE M. A lexicographic approach for multi-objective optimization in antenna array design. Progress in Electromagnetics Research, 2017, 59 (2): 85- 102.
3	DAS I, DENNIS J. Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization, 1998, 8 (3): 631- 657. doi: 10.1137/S1052623496307510
4	MESSAC A, ISMAIL-YAHAYA A, MATTSON C. The normalized normal constraint method for generating the Pareto frontier. Structural and Multidisciplinary Optimization, 2003, 25 (2): 86- 98. doi: 10.1007/s00158-002-0276-1
5	MESSAC A, MATTSON C. Normal constraint method with guarantee of even representation of complete Pareto frontier. AIAA Journal, 2004, 42 (10): 2101- 2111. doi: 10.2514/1.8977
6	MUELLER D, GRAEB H, SCHLICHTMANN U. A successive approach to compute the bounded Pareto front of practical multi-objective optimization problems. SIAM Journal on Optimization, 2009, 20 (2): 915- 34. doi: 10.1137/080729013
7	TOHID E, SERGEI V. Directed search domain: A method for even generation of the Pareto frontier in multi-objective optimization. Engineering Optimization, 2011, 43 (5): 467- 484. doi: 10.1080/0305215X.2010.497185
8	VIKHAR P. Evolutionary algorithms: A critical review and its future prospects [C]//2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC). IEEE, 2016: 261-265.
9	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation. 2002, 6(2): 182-197.
10	YI J H, DEB S, DONG J Y, et al. An improved NSGA-III algorithm with adaptive mutation operator for Big Data optimization problems. Future Generation Computer Systems, 2018, 88, 571- 585. doi: 10.1016/j.future.2018.06.008
11	KIM M, HIROYASU T, MIKI M, et al. SPEA2+: Improving the performance of the strength Pareto evolutionary algorithm 2[C]//International Conference on Parallel Problem Solving from Nature. New York: Springer, 2004: 742-751.
12	ZHANG Q, LI H. MOEA/D: A multi-objective evolutionary algorithm based on decomposition [J]. IEEE Transactions on Evolutionary Computation, 2008, 11(6): 712-743.
13	ALAYA I, SOLNON C, GHEDIRA K. Ant colony optimization for multi-objective optimization problems [C]//19th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2007). IEEE, 2007: 450-457.
14	MOSTAGHIM S, TEICH J. Strategies for finding good local guides in multi-objective particle swarm optimization (MOPSO) [C]//Proceedings of the 2003 IEEE Swarm Intelligence Symposium. IEEE, 2003: 26-33.
15	SUMAN B, KUMAR P. A Survey of simulated annealing as a tool for single and multi-objective optimization. The Journal of the Operational Research Society, 2006, 57 (10): 1143- 1160. doi: 10.1057/palgrave.jors.2602068
16	AN Y J, CHEN X H, LI Y H, et al. An improved non-dominated sorting biogeography-based optimization algorithm for the (hybrid) multi-objective flexible job-shop scheduling problem. Applied Soft Computing, 2021, 99, 106869. doi: 10.1016/j.asoc.2020.106869
17	WU X, CAO W, WANG D, et al. Multi objective optimization based on SPEA for the microgrid energy dispatch [C]//2018 37th Chinese Control Conference (CCC). IEEE, 2018: 7543-7548.
18	郑斐峰, 梅启煌, 刘明, 等. 基于遗传算法与贪婪策略的多港口集装箱配载研究. 运筹与管理, 2018, 27 (5): 1- 7.
19	覃亮, 王志成. 整车物流中轿运车装载方案优化研究. 系统仿真学报, 2015, 27 (8): 1868- 1874.
20	徐佳毅. 建立整车物流装运模型及最优算法的应用研究 [D].上海: 上海交通大学, 2012.
21	NGATCHOU P, ZAREI A, EI A. Pareto multi objective optimization [C]//Proceedings of the 13th International Conference on Intelligent Systems Application to Power Systems. IEEE, 2005: 84-91.
22	张长勇, 刘佳瑜. 基于混合遗传算法的多箱型集装箱装载问题研究 [J]. 北京航空航天大学学报, 2021. DOI: 10.13700/j.bh.100-5965.2020.0665.
23	张程, 贾宝柱, 邹佳奇. 基于多目标遗传算法的柴电混合动力船舶功率分配优化. 计算机应用与软件, 2021, 38 (3): 26- 31.
24	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题 [J]. 计算机应用, 2021, 41(8): 2249-2257.
25	DE J, ALAN K. Analysis of the behavior of a class of genetic adaptive systems [C]//The Transactions of the Institute of Electrical Engineers of Japan. 1975: 721-726.
26	PENG Q K, WANG L, QIAN B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems. Computers and Operations Research, 2008, 36 (8): 2498- 2511.
27	ZITZLER E, THIELE L. Multi-objective evolutionary algorithms: A comparative case study and the strength Pareto approach [C]//IEEE Transactions on Evolutionary Computation. IEEE, 1999: 257–271.

序号	品种名称	取货仓库	卸货地址	货物件数	货物重量/t
1	冷成形纵切钢带	P7-P7剪切成品1库	青岛市胶州市	117	126.22
2	热轧花纹卷板	ZC-精整2#成品库	济宁市任城区	2	32.42
3	冷成形钢卷	P6-P6冷轧成品库	临沂市河东区	1	1.29
4	热轧卷板	F2-山东联储中间库	泰安市岱岳区	8	248.97
5	热轧盘条	F2-山东联储中间库	青岛市城阳区	2	4.96
6	热轧酸洗钢	P6-P6冷轧成品库	临沂市河东区	1	8.96

[1]	徐向阳, 刘文伟, 傅蝶, 徐刚, 金澈清, 王祥丰, 王江涛. 改进遗传算法求解新高考背景下的排课问题[J]. 华东师范大学学报（自然科学版）, 2020, 2020(4): 108-123.
[2]	蔡海鸾, 郭学萍. 一种新的自适应惩罚函数在遗传算法中的应用[J]. 华东师范大学学报(自然科学版), 2015, 2015(6): 36-45.
[3]	陈杰, 孙霄龙, 莫玮. 空间绳牵引并联机器人多目标优化设计[J]. 华东师范大学学报(自然科学版), 2015, 2015(1): 142-150.
[4]	宋娟;全惠云. 图像增强技术中的智能算法[J]. 华东师范大学学报(自然科学版), 2007, 2007(3): 93-99.
[5]	姜昌华;胡幼华. 基于遗传算法的随机(s,S)库存系统仿真优化[J]. 华东师范大学学报(自然科学版), 2006, 2006(3): 71-76.
[6]	刘灿文;刘婕. 基于求解非线性方程组的并行遗传算法的设计[J]. 华东师范大学学报(自然科学版), 2004, 2004(1): 29-34.
[7]	谢承桓;黄乐;朱守正. 一种宽带恒定束宽数字波束形成器的设计[J]. 华东师范大学学报(自然科学版), 2003, 2003(4): 36-41.
[8]	姚萌;孟海燕. 基于遗传算法的地下遗址GPR数据分析[J]. 华东师范大学学报(自然科学版), 2003, 2003(1): 48-54.