Many-to-Many Locomotive Routing Problem for the Steel Industry

Ohhyun Kweon^a, Byung-In Kim^a*

^aDepartment of Industrial and Management Engineering, Pohang University of Science and Technology (POSTECH). ohhyun5676@postech.ac.kr, bkim@postech.ac.kr

^*Corresponding author. Tel.: +82 54 279 2371; Fax: +82 54 279 2870.

Benchmark Instances (click)

Last updated: 2024/2/5

1. Introduction

The locomotive routing problem (LRP) was first proposed by Huang et al. (2023), and it is a variant of pickup and delivery problem time windows with last-in-first-out (LIFO) constraints (PDPTWL). For transporting molten iron in the LRP, torpedo ladle cars (TPCs) are utilized. TPCs are unable to move on their own and require locomotives for transportation. TPCs act as products while locomotives act as vehicles in PDPTWL.

The many-to-many locomotive routing problem (M2MLRP) covers not only one-to-one (1-1) requests but also one-to-many (1-M) and many-to-one (M-1) requests for the steel industry. M-1 requests are generated when there is a demand in several locations. In such cases, several TPCs that can fulfil this demand are eligible for pick-up. In contrast, 1-M requests are generated when a newly available TPC is generated and needs to be delivered to a location within a factory. Additionally, 1-1 requests specify the exact TPC that needs to be picked up and its designated delivery location

The goal of M2MLRP is to minimize the total travel time of locomotives when meeting all requests. Several constraints are required for M2MLRP:

1) Compatibility (empty and loaded TPCs cannot be connected at the same time)

2) LIFO

3) Clearance

4) Locomotive capacity (maximum of 2 TPCs)

5) Loading time

6) Time window of pickup and delivery

7) Eligibility for the TPC destination

2. Benchmark Problems

To the best our knowledge, M2MLRP is introduced in this study for the first time, and therefore no available benchmark exists. A total of 40 instances were generated randomly to simulate a real-world factory in South Korea. These instances were categorised into three different sizes, representing varying levels of complexity (see Tables 1 and 2). In all the instances, the number of ironmaking facilities (IFs), steelmaking facilities (SFs), heater (HR), buffer area (BA), and repair factory (RF) remained fixed with value of 5, 2, 1, 1, and 1, respectively. To model the factory layout, a roadmap was designed based on the actual environment.

To ensure safety and maintain continuous production, TPCs must be prepared under the IFs at least 5 min before the pouring process begins. Once the TPCs are fully loaded in the IFs, they need to be picked within 20 min and delivered to the SFs. During preparation for the next process, the empty TPCs generated after pouring molten iron in the SFs must also be picked up within 20 min. Pickup and delivery operations from RF and HR have a time window of 60 min. The loading and unloading service time  was set to 2 min, the locomotive capacity  was set to 2, and the loading time limit  was set to 120 min. Instances are classified by the size of requests.

Table 1. Size of Instances

	Small	Small	Medium	Large
Working hours (h)	1.5	2	4	8
Total requests	14-17	25-29	71-75	162-165
Cold TPCs	2	2	2	2
Reheated TPCs	2-3	3	3	3
Heating requests	0	0-1	1	2
Repair factory requests	0	0-1	0-1	0-1
Locomotives	5	10	10	10
Number of instances	10	10	10	10

Table 2. Detailed Information of Instances

Instance	M-1 Request			1-M Request	TPC	Place	Locomotive
	BF	HS	RF
S1	4	0	0	10	21	35	5
S2	4	0	0	10	21	32	5
S3	5	0	0	11	22	35	5
S4	5	0	0	10	21	34	5
S5	4	0	0	10	21	35	5
S6	2	0	0	11	22	31	5
S7	5	0	0	12	23	37	5
S8	5	0	0	11	22	38	5
S9	5	0	0	11	22	36	5
S10	5	0	0	12	23	38	5
S11	6	1	0	20	43	50	10
S12	6	1	0	19	42	50	10
S13	7	0	0	18	41	49	10
S14	5	0	0	20	43	49	10
S15	7	0	0	18	41	49	10
S16	9	0	0	17	40	49	10
S17	9	1	0	16	39	50	10
S18	10	0	0	18	41	49	10
S19	8	0	0	17	40	49	10
S20	9	1	0	19	42	50	10
M1	24	1	0	47	70	95	10
M2	23	1	0	47	70	95	10
M3	23	1	0	48	71	95	10
M4	23	1	0	48	71	95	10
M5	24	1	1	49	71	96	10
M6	25	1	0	47	70	95	10
M7	25	1	0	46	69	95	10
M8	23	1	0	48	71	95	10
M9	23	1	0	48	71	95	10
M10	24	1	0	47	70	95	10
L1	53	2	0	107	130	186	10
L2	53	2	0	107	129	186	10
L3	52	2	0	109	129	186	10
L4	53	2	0	108	133	186	10
L5	53	2	1	109	131	187	10
L6	54	2	0	108	129	186	10
L7	54	2	1	108	130	187	10
L8	53	2	0	107	129	186	10
L9	53	2	0	108	130	186	10
L10	53	2	0	107	130	186	10

The total number of TPCs in this study refers to the number of TPCs considered in the problem formulation. It is important to note that this number does not necessarily reflect the actual number of TPCs in the steelworks. This study assumes that new, empty TPCs are generated from the SFs and are consumed in the IFs, while loaded TPCs are generated from the IFs and consumed in the SFs. Therefore, the number of TPCs can vary depending on the duration of the work hours being considered.

The number of locations in the problem formulation is influenced by the number of TPCs. Because M2MLRP is a variant of PDPTW, it is necessary to distinguish between different destinations for each TPC. In cases where multiple TPCs have the same destination, the destination is split into multiple locations. For example, if TPC1 and TPC2 both need to go to the same SF, the SF is split into SF1 and SF2, where SF1 is only eligible for TPC1 and SF2 is only eligible for TPC2. This allows for the proper differentiation and assignment of TPCs to their respective destinations.

Instance Generation Process

To generate instances, we initially examined the production schedule of IFs (blast furnace). In real-world scenarios, the tasks in IFs often represent the bottleneck in production processes. Therefore, the production schedule for SFs should consider that of IFs. Subsequently, requests related to the RF and HR, which are relatively independent, were determined sequentially. After establishing the production schedules, we generated information concerning TPCs considering SFs, BA, HR, RF, and IFs. The instance generation process was defined as follows.

1. Creating production schedules for IFs: Initially, we generated random schedules for each IF, with values chosen from the set (0, 5, 10, 15, 20, 25, 30, 35, 40)m. Then, we created subsequent schedules for each IF by adding 40 min, which is the production duration of each ironmaking facility. For example, if the first production schedule for ironmaking facility ‘A’ is set at 15, the second schedule for ‘A’ is set at 15 + 40 = 55, the third is 95, and so on. Those production schedules are then used to generate demand requests in ironmaking facilities. We stipulated that a TPC should arrive between 25 to 5 min before production. For instance, if the production time was set at 30, the time window for the demand is [5,25]. To prevent excessively tight time windows, production schedules with a production time of less than 25 were excluded.

2. Creating production schedules for SFs: Because five loaded TPCs are generated from five IFs working during a 40-min interval, an empty TPC is generated with an 8-min interval from SFs. The first production schedule was randomly chosen from the interval [0,8]. Subsequent production schedules were then created by adding 8 min. To avoid excessively tight time windows, production schedules with a production time of less than 20 were excluded.

3. Generating requests for the RF and HR: To generate requests for the RF, we first determined whether repair requests are to be considered. Repair schedules are randomly calculated with the range of [0,24] h. If the starting time for necessary repairs is less than the number of working hours minus 60 min, the repair schedule is included as a request in the instance. For creating requests for the HR, we initially determine the number of vacancies in the HR, employing the same mechanism as used for the repair factory. The heating schedule is then calculated within the range of [0,6] h for each vacancy.

4. Generating TPCs from SFs: TPCs are supplied from SFs. We initiated the supply of TPCs based on the production schedule of SFs.

5. Generating TPCs in the buffer area: A total of 20 TPCs are used with varying characteristics. TPCs in the buffer area exhibit variations in temperature; certain TPCs may be sufficiently hot to transport molten iron to IFs, while others may be cold and require transportation to the HR for reheating. Additionally, some cold TPCs remain on standby in the BA for potential repairs.

6. Generating TPCs in the HR and RF: TPCs become available from the HR or RF once their assigned tasks are completed. The available times are randomly chosen within the range of 0 to 0.5 working hours, with a time window interval of 60 min.

7. Generating TPCs from IFs: Considering the production schedules of IFs, we generated loaded TPCs. The time windows were set between 0 to 20 min after the production was finished.

8. Creating a distance matrix: Distances between each facility were generated using the values shown in Table 3.

9. Generating locomotives: The available locations of each locomotive were randomly set among all facilities, and their available time was set to 0.

Six input files are provided as Excel CSV files. These files include ‘Filelist.csv’, ‘OD.csv’, ‘Request_1M.csv’, ‘Request_M1.csv’, ‘Train.csv’, and ‘parameter_s.csv.’ ‘Filelist.csv’ simply contains directory of each input file. In ‘OD.csv’, the distances between all locations for an instance are listed as an adjacency list. Information concerning OD is shown in Table 3.

In ‘Request_1M.csv’, information about the TPCs is provided. The column ‘Paired TPC’ in this file is not used. The explanations for all columns are as follows:

- TPC ID: name of the TPC

- Eligible place: possible destination of the TPC. Listed using ‘;’.

- TW_min: fastest time of the pickup time window

- TW_max: latest time of the pickup time window

- Available place: current location of the TPC

- Loaded: E if the TPC is empty; F if the TPC is full with molten iron

- Priority: H if the TPC is the subject of a request; L if the TPC is not the subject of a request.

- Paired TPC: not used in this problem

 ‘Request_M1.csv’ contains information about demands. The column explanations in this file are as follows:

- Place ID: location where the demand is generated

- TW_min: fastest time of the required delivery time window

- TW_max: latest time of the required delivery time window

- Type (D/R/H): type of request. D: request from the blast furnace (iron-making facility); R: request from the repair factory; H: request from the heater

Table 3. OD matrix (units: min)

	SF	BA	HS	RF	IF1	IF2	IF3	IF4	IF5
SF	0	15	20	20	20	21	22	23	24
BA		0	10	10	15	16	17	18	19
HS			0	10	10	11	12	13	14
RF				0	25	26	27	28	29
IF1					0	1	2	3	4
IF2						0	1	2	3
IF3							0	1	2
IF4								0	1
IF5									0

- * The OD-matrix is provided symmetrically.

In ‘Train.csv’, information about the locomotives is provided. The column explanations in this file are as follows:

- Train ID: name of the locomotive

- Available place: current location of the locomotive

- Available time: available time of the locomotive

 ‘parameter_s.csv’ contains information about the parameters in this system. The service time, capacity of the locomotive, and loading time limit are provided. ‘parameter_s.csv’ is used for small-sized instances while ‘parameter_m.csv’ is used for medium-sized instances.

Regarding the iteration settings in the matheuristic, the maximum iteration count was set to 1000 for small-sized instances and 100 for medium- and large-sized instances. The improvement_threshold and infeasible_threshold values were set at 50 and 30, respectively, for small-sized instances. For medium- and large-sized instances, they were set at 10 and 5, respectively. The initial_fixed_ratio and final_gap values were both set at 0.1. The hyperparameters are described in Table 4.

Table 4. Hyperparameters

	Small-sized	Medium- and Large-sized
Maximum iteration	1000	100
ending_threshold	200	20
improvement_threshold	50	10
infeasible_threshold	30	5
initial_fixed_ratio	0.1	0.1
final_gap	0.1	0.1

Reference

Huang, B., Tang, L., Baldacci, R., Wang, G., & Sun, D. 2023. “A metaheuristic algorithm for a locomotive routing problem arising in the steel industry.” European Journal of Operational Research 308 (1): 385-399.