A Fast Heuristic Algorithm for Ladle Scheduling Based on Vehicle Routing Problem with Time Windows Model
A Fast Heuristic Algorithm for Ladle Scheduling Based on Vehicle Routing Problem with Time Windows Model
复制标题
基于时窗模型车辆路径问题的钢包调度快速启发式算法
DOI：
10.2355/isijinternational.54.2588
复制
发表时间：
2014-11
影响因子：
1.8
通讯作者：
Shixin LIU
中科院分区：
文献类型：
--
作者：
Zheng WEI;Tan ZHU;Tianzhang HE;Shixin LIU
在炼钢和连铸生产过程中，优化钢包制度将大大降低能耗，提高产量。钢包调度问题可以建模为带时间窗和附加约束的车辆路径问题。主要的额外限制是钢包的部件必须在正确的时间进行维修，不得晚于服务一定数量的炉次。钢包调度问题的目标是最小化服务钢包的数量并减少服务两个相邻炉次之间的等待时间。根据钢包的使用过程，建立了数学模型来解决这一具体问题。本文根据模型的特点和初步实验，提出了一个时间复杂度为O（n）的三步启发式算法。该算法已被测试的几个实际例子，从中国的钢铁厂。通过与实际生产中使用的调度方案进行比较，计算结果表明，该算法优化了钢包调度方案，并在不到1 s的时间内解决了问题，证明了算法的有效性。
In the process of steelmaking and continuous casting production, an optimized ladle schedule will greatly reduce energy consumption and improve production. The ladle scheduling problem can be modeled as vehicle routing problem with time windows (VRPTW) and extra constraints. The main extra constraint is that components of the ladle, at the right time, have to be repaired no later than serving certain number of heats. The objective of ladle scheduling problem is minimizing the number of serving ladles and reducing the waiting time between serving two adjacent heats. According to the serving process of ladles, a mathematical model is established to solve this specific problem. In this paper, a three-step heuristic algorithm with time complexity of O(n) is proposed, which is based on characteristics of the model and some preliminary experiments. The algorithm has been tested by several practical instances from a steel plant in China. Comparing with the schedules used in actual production, the computational results show that our algorithm optimizes the ladle schedules and solves the problem in less than 1 second, which proves the algorithm’s efficiency.