华东师范大学学报(自然科学版) ›› 2021, Vol. 2021 ›› Issue (5): 185-198.doi: 10.3969/j.issn.1000-5641.2021.05.016

• 数据分析与应用 • 上一篇    

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

于萍, 胡卉芪*(), 钱卫宁   

  1. 华东师范大学 数据科学与工程学院, 上海 200062
  • 收稿日期:2021-07-27 出版日期:2021-09-25 发布日期:2021-09-28
  • 通讯作者: 胡卉芪 E-mail:hqhu@dase.ecnu.edu.cn
  • 基金资助:
    国家自然科学基金(U1911203)

Research on multi-objective cargo allocation based on an improved genetic algorithm

Ping YU, Huiqi HU*(), Weining QIAN   

  1. School of Data Science and Engineering, East China Normal University, Shanghai 200062, China
  • Received:2021-07-27 Online:2021-09-25 Published:2021-09-28
  • Contact: Huiqi HU E-mail:hqhu@dase.ecnu.edu.cn

摘要:

针对多目标货物配载问题, 建立了以最大化总订单货物重量、最小化车次总数、最小化货物装卸地总数为目标的配载模型, 提出了一种快速收敛的基于精英策略多目标遗传算法(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

中图分类号: