运筹与管理 ›› 2024, Vol. 33 ›› Issue (6): 7-13.DOI: 10.12005/orms.2024.0174

• 理论分析与方法探讨 • 上一篇    下一篇

基于自适应邻域模拟退火算法的零部件接收与转运优化

毛照昉, 宋满金, 黄典, 方侃   

  1. 天津大学 管理与经济学部,天津 300072
  • 收稿日期:2022-04-27 出版日期:2024-06-25 发布日期:2024-08-14
  • 通讯作者: 黄典(1989-),男,安徽六安人,博士,讲师,研究方向:物流优化。
  • 作者简介:毛照昉(1977-),男,天津人,博士,教授,研究方向:智能制造;宋满金(1998-),男,吉林四平人,硕士研究生,研究方向:厂内物流优化;方侃(1985-),男,浙江台州人,博士,副教授,研究方向:组合优化。
  • 基金资助:
    国家自然科学基金重大研究计划重点支持项目(92167206);科技部创新方法专项(2020IM030300);天津市哲学社会科学规划项目(TJGL21-016)

Optimization of In-Plant Parts Receiving and Transferring Based on Adaptive Neighborhood Simulated Annealing Algorithm

MAO Zhaofang, SONG Manjin, HUANG Dian, FANG Kan   

  1. College of Management and Economics, Tianjin University, Tianjin 300072, China
  • Received:2022-04-27 Online:2024-06-25 Published:2024-08-14

摘要: 现代混线生产对于多品种小批量零部件物流的准确度和准时性提出更高要求,其中零部件接收与转运是管理者面临的首要难题,需要考虑三种情形,一是供应商的卡车交付与装配线需求均具有时间窗口;二是车辆调度问题,即决定每个仓库门服务的车辆的处理顺序;三是车辆分配问题,即每辆牵引车承载的需求,这大大提升了问题的复杂性。为优化零部件接收与转运,本文建立一套考虑准时制的零部件超市物流模式,将交叉转运应用于工厂物流管理,研究了中心仓侧的车辆分配与调度问题(Vehicle Assignment and Scheduling Problem, VASP),并对问题进行了建模和线性化处理。由于该类问题的内在复杂性,本文设计一种自适应邻域模拟退火算法(Adaptive Neighborhood Simulated Annealing, ANSA),并将其与先进的商业优化求解器进行比较。本文开展了大量计算数值实验,结果表明ANSA算法在不同规模的算例上均有较好表现。

关键词: 交叉转运, 车辆调度, 超市, 准时制, 模拟退火

Abstract: With the continuous development of society and economy, manufacturing plants are required to diversify their product offerings in order to meet the varied needs of customers. The mixed-line production method, which allows for the production of different products with a large number of common basic parts on the same production line, has gained popularity in modern manufacturing industry. However, this demand for mixed-line production puts significant pressure on the logistics system due to the requirement for multiple varieties and small quantities of parts. To enhance efficiency in production logistics operations and effectively implement the just-in-time (JIT) principle, many manufacturing companies have adopted a supermarket logistics model as an intermediate warehouse for nearby workstations’ part requirements. This model utilizes frequent small-volume deliveries through milk-run cycles to deliver parts to the assembly line. Such just-in-time delivery systems are widely used in mixed-line production models such as automotive assembly and agricultural machinery parts plants.
As the head of production logistics, managers face a primary challenge in optimizing parts receiving and transferring. In factories that implement the JIT principle, there are three scenarios in efficient parts receiving and transferring: firstly, coordinating time windows for both supplier’s truck delivery and assembly line demand; secondly, solving the vehicle scheduling problem by determining the processing order of vehicles serviced at each warehouse door; and thirdly, addressing the vehicle allocation problem which involves assigning appropriate demands to each tractor-trailer. These factors significantly contribute to the complexity of this issue.
To optimize parts receiving and transferring, this study establishes a just-in-time-based parts supermarket logistics model and implements cross-docking in factory logistics management. Compared to the traditional approach, the cross-docking model enables intelligent sorting, reduces storage and retrieval costs, and enhances the management of multi-species and small-lot parts. Building upon this foundation, we investigate the Vehicle Assignment and Scheduling Problem (VASP), which incorporates time window constraints, vehicle scheduling, and vehicle assignment considerations. We formulate and linearize the problem.
To address this challenge effectively, an Adaptive Neighborhood Simulated Annealing (ANSA) algorithm is proposed in this paper. The ANSA algorithm encompasses various neighborhood operations along with adaptive rules for comparison against state-of-the-art commercial optimization solvers. Extensive computational experiments are conducted to validate the effectiveness of our proposed ANSA algorithm.
The innovations of this paper are as follows: (1)The concept of cross-docking is applied to optimize production logistics, effectively enhancing the management of multi-species and small-lot parts in logistics. (2)In the cross-docking problem, the outbound vehicle typically corresponds to a customer’s demand. This paper extends this assumption based on practical factory experience, enabling tractor-trailers to simultaneously transport multiple demands from the supermarket. The research findings have significant implications for production practice. (3)This paper designs an efficient meta-heuristic algorithm tailored to the problem characteristics. The experimental results demonstrate its excellent performance across various scale scenarios.

Key words: cross docking (CD), vehicle scheduling, supermarket, just-in-time (JIT), simulated annealing

中图分类号: