Location of Railway Emergency Rescue Spots Based on a Near-Full Covering Problem: From a Perspective of Diverse Scenarios

Abstract

The location of railway emergency rescue spots is facing diverse scenarios including the location of new facilities and optimization of existing layouts with limited or non-limited conditions. Generally there will be heavily redundant covering ability if all the edge demands on a network are fully covered. Here, we first proposed a near-full covering model to balance investment in the facility and the actual coverage rate, and successfully applied this model in the optimal location of railway emergency rescue spots under diverse scenarios. We also developed a feasible solution that can select an effective algorithm or a greedy algorithm based on the total consumed time. With the constraint of a fixed coverage rate threshold, a larger coverage radius may lead to fewer facilities and higher relative redundancy. Flexible designs of the important node set where all the elements must be selected and the exclusive node set where all the elements cannot be selected are carried out to construct several scenarios. The comparative analysis shows that the optimal solution is an obvious improvement on the existing emergency rescue spot layout in the real railway network. This study provides an alternative version of the edge covering problem, and shows a successful application in the location problem of railway rescue spots.

1. Introduction

In recent years, the railway network in China has been dramatically developed. According to the National Bureau of Statistics of China 2021, the total operational mileage of the railway network is nearly 150,000 km [1]. Unfortunately, some damage or accidents caused by uncontrollable factors, i.e., natural disaster or human activity, may occur anywhere on the railway network [2,3,4]. If unexpected operation disruptions occur, this will bring a series of negative consequences, such as economic loss, injury, and/or even death. For example, an especially serious railway traffic accident on the Ningbo–Wenzhou railway occurred on 23 July 2011, resulting in about 200 million RMB of direct economic loss and 40 dead as well as 172 injured. On 4 June 2022, a moving train hit a mudslide that collapsed on the Guiyang–Guangzhou railway, leading to the death of a train driver and 8 injured. Delayed rescue activities at the demand point may amplify negative impacts including delayed recovery of rail traffic, and less effective rescue time for injured persons. For instance, the Langfang section on the Beijing–Shanghai railway was damaged by color-coated steel blown by strong winds on 12 August 2018. Indeed, the nearly 5 h rescue time for this emergency event could have been reduced by 50% if the relief train had been located at Beijing Nan station, closer to the rescue demand point [2]. Obviously, location of the emergency rescue spot based on strategic decision plays an vital role in emergency rescue management [5], and the emergency rescue management is an important aspect in sustainable development of city and transportation [6,7,8,9].

The railway network has multi-connectivity and precise operation schedule, so it should be covered by rescue depots within a specific time. In particular, almost all the emergency events on the railway network randomly happen anywhere and at any time, and the amount of demand is hard to predict with good accuracy. In other words, this type of rescue demand is distributed over the railway network, including railway stations (nodes) and rail tracks (edges). In actual situations, potential locations of emergency rescue spots are near or at the railway stations. Based on the present consideration, this location problem can be defined as the Edge Covering Location Problem (ECLP). The ECLP can be further subdivided into the Edge Set Location Covering Problem (ESCP) and the Edge Maximal Covering Location Problem (EMCLP) [10,11,12]. For the ESCP, its objective function is to minimize the construction costs or the number of facilities with the constraint that the entire demand must be totally covered [10,13]. In fact, this entire covering of edge demand on the network usually contains redundant covering on edge covering which means that some edge demand can be covered by multiple facilities at the same time. This redundant covering means an additional economic investment in the rescue spot and equipment, and that entire coverage is not economical. The EMCLP focuses on the maximization of the covering region with a fixed number of facilities, but cannot ensure the entire coverage of edge demand [13,14]. It is valuable that coverage rate on edge demand approximates to a preset range close to 100% with minimum redundancy. To address this problem, we proposed a near-full edge covering problem to determine the minimum number or investment of facilities and their optimal locations to achieve the near-full covering of edge demand on a network with an accepted coverage rate (such as a coverage rate of 98%).

In practice, the location of emergency rescue spots may be multiple situations under non-limited and limited conditions; for example, a part of the rescue spot must be located in some railway stations or not. In terms of candidate location of emergency rescue spot, we constructed four scenarios to provide some suitable solutions for decision makers. The primary candidate set of an emergency rescue spot is a subset of network nodes (namely, they are near/at a railway station). The available candidate set (ACS) is produced by eliminating a set of some removed nodes (removed node set) from the primary candidate set. If the removed node set exists, it may contain some important nodes (important node set) that are necessarily selected or some exclusive nodes (exclusive node set) that must not be selected. First scenario: the removed node set is empty, meaning that all the nodes in the primary candidate set can be selected as the candidate location. Second scenario: the important node set is not empty, while the exclusive node set is empty. This means that some railway stations must be selected as the candidate set, and there is no exclusive position. Third scenario: the important node set and the exclusive node set are both not empty. This means that some railway stations must be selected as the candidate set, and there are also some exclusive positions. Fourth scenario: the important node set is empty, while the exclusive node set is not empty. This means that there are only some of the eliminated nodes. Clearly, diverse scenarios proposed in this work are meaningful for complex actual situations including initially unconstrained location and/or conditional upgrading location of a railway emergency rescue spot.

The main contributions of this study are to propose a near-full edge covering model to balance coverage rate and total input; to reveal the effects of coverage radius and covering rate threshold; and to construct candidate sets to obtain optimal solutions for diverse scenarios.

The rest of this paper is organized as follows. A systematic literature review and analysis on covering location problems and location of emergency rescue spots on the railway is carried out in Section 2. In Section 3, problem description, mathematical modeling, and effective solution are presented. In Section 4, combined with actual application in a railway network, joint effects of coverage radius and covering rate threshold are explored, and optimal location in diverse scenarios is also conducted. In Section 5, the main conclusions and findings are described.

2. Literature Review

Although the facility location problem includes the covering location problem and the p-center location problem, the focus of this work is the edge covering location problem. In this section, we conduct a comprehensive review about ECLP and railway emergency rescue.

Edge covering location problem: As described above, the ECLP can be subdivided into ESCLP and EMCLP. (a) The ECLP first appeared in the work of Revelle et al. [15], in which the total edge covering problem (TECP) is actually a kind of ESCLP where all the edge demand must be covered. Then, Guha et al. [16] proposed a kind of capacitated total edge covering problem where each edge is covered by one of its own vertices. Sadigh et al. [17] proposed a complementary edge covering problem, in which the partial cover of edge demand by several vertices is used to present the entire coverage of all the edge. Ran et al. [18] developed a continuous edge set covering problem where the facilities can be located anywhere along the network and the demand is continuously distributed all over the edges. The Euclidean distance was used in their work. The distance was developed as the shortest path along the network by Alamatsaz et al. [19] (b) The EMCLP was presented by Church and Meadows [20]. Next, they introduced the maximal arc-covering location model, defined the network intersect point set (NIPS) as the set of candidate points, and proposed the segment of equal coverage (SEC) whose endpoints can cover exactly the same demand point lying in the SEC [21]. Berman et al. [22] presented an alternative integer linear programming formulation under the assumption of uniformly distributed network demand, and designed a greedy heuristic solution for large-scale problems to reduce the computational time. Berman et al. [23] considered the classical MCLP and its obnoxious version on a network where the demand is distributed along the edges. Yin and Mu [24] proposed a modular capacitated maximal covering location problem that allows several facility capacity levels for each potential site. Paul et al. [25] developed a hierarchical extension of the maximal covering location problem where coverage of the population within a specific time is maximized with minimum modifications to the existing structure. Blanquero et al. [26] studied the MCLP with regional demand on a network, in which demand is continuously distributed along the edge and the locations of p facilities are along the edges of a network. Baldomero-Naranjo et al. [11] studied the single-facility minmax regret maximal covering location problem with demand distributed along the edges. Baldomero-Naranjo et al. [13] further conducted another study on the upgrading version of the maximal covering location problem with edge length modifications on networks, by assuming that the length of the edges can be reduced at a cost.

Railway emergency rescue management: Among many aspects of railway emergency rescue management, the location of emergency rescue is an important aspect. A survey on this topic shows that the related literature is fairly sparse. Cheng and Liang [5] developed a fuzzy multi-objective strategic planning model of emergency rescue units for both urban ambulance and railway emergency systems locating. The objective of this model is the maximization of the ambulance coverage on the population and the maximization of the risk covered on the railway line. Bababeik et al. [27] examined the optimal location and allocation of relief trains by using a bi-objective model. They recognized the priority of demand based on the concepts of link importance and exposure. Cooperative coverage from multiple facilities with decay coverage is permitted. In their work, edge demand on the railway network is actually simplified into a point of demand at the middle point of the edge. Tripathi et al. [4] addressed the location of different types of relief facilities in the railway network based on demand, considering the importance of each link that couples utility, frequency, and urgency of demand. Vaezi et al. [3] proposed a two-stage stochastic programming model to determine the location of response facilities and equipment packages and their allocation decision for rail hazmat incidents in order to achieve optimal design of the emergency response network for rail hazmat shipments. Tang and Sun [28] built a multi-objective model to minimize the dispatch time of railway emergency resources and the number of railway emergency rescue bases. Wang et al. [2] used a robust conditional vertex p-center problem for the location of a high-speed railway emergency rescue station. In their work, uncertainty of travel time between two points on the network is considered. Zhang et al. [29] proposed a nonlinear mixed-integer programming model to determine the location of the distribution center to improve the sustainable distribution network design for the maintenance components of electric multiple units.

According to the above literature review, it is concluded as follows: (1) Studies about optimal location of railway emergency rescue depots are rare. In the existing studies, the edge demand on the railway network is almost approximated by using point demand, although this approximation may bring some errors. (2) The near-full covering problem proposed in these studies is absent. (3) A comprehensive study on the candidate set of emergency rescue depots has been not completed. Nevertheless, this insight is very important for primary design and optimal upgrading of emergency rescue depots at multiple scenarios. Combining a compressive literature analysis with meaningful insights in railway emergency rescue management, we decided to conduct this study to provide some useful information for improving the emergency management levels of railways.

The main contributions of this work are as follows:

(1)

We innovatively developed a near-full covering model that can balance investment in the facility and the actual coverage rate.

(2)

We developed an effective solution algorithm that can select automatically effective algorithm or greedy algorithm based on the estimated consumed time.

(3)

We constructed diverse scenarios by adjusting a candidate set of rescue spots in which some important nodes and exclusive nodes can be given.

(4)

We successfully applied the developed method into the location of emergency rescue spots on the railway network.

3. Methodology

3.1. Problem Description

We designed a series of examples to show visually the significance of the near-full edge covering problem, as shown in Figure 1. We defined the relative redundancy (RR) that is a ratio of actual edge length repeatedly covered to the maximum edge length repeatedly covered, in which maximum edge length repeatedly covered corresponds to a special case where all the potential locations have facilities. Note that not all the examples existed in each railway network, but some of them may be a part of a real railway network structure. As shown in Figure 1, when there is only one facility for the EMCLP, its coverage rate is merely 64.29%. A low coverage rate is not consistent with the requirement of railway rescue. With the increasing of facility numbers from 1 to 2, coverage rate can be up to 91.43%. If all the edge demand is entirely covered for the ESCLP, an additional five facilities will be required. Consequently, the relative redundancy (RR) largely increases from 14.28% to 100%. This means that some uneconomic input must be included if the entire coverage is a strict constraint. It is doubtless that there must be an optimal state in the transition region between EMCLP and ESCLP. In this optimal state, coverage rate is not less than a threshold that is usually less than 100%; meanwhile, the value of RR is also within an accepted range. The above statement is exactly the task and significance of the near-full edge covering problem proposed in this work.

3.2. Mathmatic Modeling

We defined an undirected network G = (N, E) where N is the set of nodes of the network. E = {(i, j)|i and j∈N, i < j} are the edge set of the network.

We also defined some necessary indices, sets, and parameters.

• i, j and k: index of network nodes;
• L_ij: length of edge e (i,j);
• $L_{ij}^{kx}$: length covered by facility at node k from node i;
• $L_{ij}^{ky}$: length covered by facility at node k from node j;
• d_x,y−: shortest distance between any pair of points x, y∈N;
• R: coverage radius of the facility;
• X_k: is equal to 1 if the facility located at node k, otherwise, 0;
• N_a: available candidate set of facilities;
• $L_{ij}^{eff}$:effective coverage of edge e(i,j);
• CR: coverage rate for general demand is the ratio of actual coverage distance to total edge distance;
• $T_{CR}$: threshold of coverage rate;
• $T_{RR}$: threshold of relative redundancy;
• P: maximum number of rescue spots;

The near-full edge covering problem for diverse scenarios can be formulated as:

$$M\mathrm{ax}{\displaystyle \sum _{k=1}^{\left|N_{\mathrm{a}}\right|}{\displaystyle \sum _{e(i,j)\subset E}{X}_k{L}_{ij}^{eff}}}$$

(1)

$$M\mathrm{in} {\displaystyle \sum _{}^{}{X}_k}$$

(2)

Subject to:

$$L_{ij}^{eff}=\min \{\left(\max \right(L_{ij}^{kx})+\max \left(L_{ij}^{ky}\right),{\mathrm{L}}_{\mathrm{i}\mathrm{j}}\}, \forall (i, j)\in \mathrm{E},\mathrm{i}<\mathrm{j},\mathrm{k}\in {\mathrm{N}}_{\mathrm{a}}$$

(3)

$$L_{ij}^{kx}=0,if d_{k,i}\ge R; otherwise,L_{ij}^{kx}=(R-d_{k,i})$$

(4)

$$L_{ij}^{ky}=0,if d_{k,j}\ge R;otherwise,L_{ij}^{ky}=(R-d_{k,j})$$

(5)

$${\displaystyle \sum _{k=1}^{N_a}{X}_k\le P}$$

(6)

CR ≥ T_CR

(7)

RR ≤ T_RR

(8)

X_k ∈ {0,1}, ∀ k ∈ N_a

(9)

The objective formula (1) aims to maximize the effective coverage of all the edges on the railway network. The objective function (2) is to minimize the facility number. The task of this problem is to determine the minimum number of facilities with the satisfaction of the thresholds of coverage rate and relative redundancy. Constraint (3) refers to the fact that maximum effective coverage for any edge should not be more than edge length. Constraints (4) and (5) are used to obtain effective coverage length of all edges. Constraint (6) presents that the total facility number is not more than maximum number P. Constraint (7) ensures that coverage rate for rescue demand must not be less than a preset threshold. Constraint (8) ensures that the relative coverage rate must not be more than a preset threshold. Constraint (9) is the integrality constraint. If constraints (7) and (8) cannot be satisfied at the same time, we will adjust the T_CR to decrease the value of RR. For some special network structures, a slight increase of CR may lead to a sharp increase of RR. Note that constraints (6), (7), and (8) may not be satisfied at the same time.

3.3. Effective Solutions

Based on the interrelationship between two objectives and constraints in this problem, we design an effective solution method, whose logistic procedure is shown in Figure 2. First, the adjacency matrix of a network and the ACS for a specific situation should be obtained. Then, a set of parameters, including P, T_RR, and R, are also set. The initial number of the facility is equal to the integer of a half of P. The present facility number will also be recorded into set Num.

Second, we need to discuss the time-consumed feature of the proposed algorithm, especially for a large scale of ASC. In general, an exact algorithm can check all the possible solutions, which leads to a sharp increase in the consumed time for a large scale of candidate set. Referring to the work of Berman et al. [22], we adopt a greedy algorithm to decrease the consumed time for a large scale of the ACS, although it only obtains a sub-optimized solution. To make an available balance of calculation efficiency and accuracy, we design a self-switching method where, if calculation time exceeds a threshold, a greedy algorithm will be activated. Based on the self-switching method, we will obtain optimal solution X without constraints (6)–(8).

Third, constraints (6)–(8) must be introduced to satisfy the designed problem. The values of the CR and RR can then be calculated. To facilitate the description, we name four judgments as J1, J2, J3, and J4. J1: check if the value of CR is greater than T_CR or not. J2: check if the facility number is equal to P or not. J3: check if the value of RR is less than T_RR or not. J4: check if (∑X_k − 1) belongs to the set Num. If J1 is YES, it will be denoted by J1-YES. Otherwise, it will be denoted by J1-NO. This symbol rule is also used for J2, J3, and J4. If there are J1-NO and J2-NO, the current solution will be the optimal solution. If there are J1-NO and J2-YES, we will let ∑X_k = (∑X_k + 1). If there are J1-YES and J3-YES, the current solution will be the optimal solution. If there are J1-YES, J3-NO, and J4-YES, the current solution will be the optimal solution. If there are J1-YES, J3-NO, and J4-NO, we will let ∑X_k = (∑X_k − 1). Actually, we adjust the facility number to meet the constraints. It is necessary to note that the priority order of these three constraints is (6), (7), and (8), respectively. This regulation is consistent with the actual situation.

To determine the values of RR, we first obtain the total length of the repeated area, based on the following rules:

Rule1: 

If edge length $L_{ij}$ is no more than R, the full length of this edge will belong to the repeated area.

Rule2: 

For edge length $L_{ij}$ that ranges from R to 2R, total edge length covered repeatedly by not less than two facilities is equal to the sum of maximum length covered by other nodes through its two endpoints and length covered simultaneously by its two endpoints.

To calculate the actual covered length by the current optimal facility set, we developed a feasible method that is described as:

Step 1. Obtain actual covered length of each edge by every node in the current optimal facility set.

Step 2. Identify effective coverage (repeatedly) lengths of all the edges based on the following situation:

(1)

If an edge is not covered by any node, the effective covered length (ECL) is equal to 0.

(2)

If an edge is covered by a facility, the ECL is also equal to 0.

(3)

If an edge is covered by one facility through one of the two endpoints, and is also covered by another facility through another endpoint, the ECL is equal to the actual length covered repeatedly by these two facilities.

(4)

If an edge is only covered by not less than two facilities through one of two endpoints, the ECL is equal to the maximum potential length (MPL) covered by not less than two facilities.

(5)

If an edge is covered by not less than two facilities through one of two endpoints and also covered by another facility through another endpoint, the ECL is equal to the sum of the MPL_l (an edge length covered by facilities through left endpoint) or MPL_r (an edge length covered by facilities through right endpoint) covered by not less than two facilities through an endpoint plus MPL_l,r (an edge length covered by facilities through left and right endpoints) repeatedly through two endpoints.

(6)

If an edge is covered by not less than two facilities through two endpoints, the ECL is equal to the sum of MPL_l and MPL_r covered by not less than two facilities from two sides plus MPL_l,r covered repeatedly through two endpoints.

Note that effective covered length must be no more than edge length. To clearly show this rule, we construct an example 1 with situation (6) shown in Figure 3.

Example 1: The length of an edge with two endpoints ($v_l$ and $v_r$) is represented as $L_{lr}$. For situation (6), not less than two facilities cover this edge through two endpoints. Herein, lengths covered by 5 facilities from endpoint $v_l$ can be recorded into set CL_l (a set of covering ability of facilities from the left endpoint) with five elements. Similarly, lengths covered by 5 facilities from endpoint $v_r$ can be recorded into set CL_r (a set of covering ability of facilities from the right endpoint) with 5 elements. As shown in Figure 3, general expression of ECL is minimization of (MPL_l + MPL_l,r + MPL_r) and edge length $L_{lr}$. Actually, MPL_l, MPL_l,r and MPL_r range from 0 to $L_{lr}$. In order to show clearly the effective solution, the detailed procedure is given:

Step1:

The available candidate set and structure information (adjacency matrix) of network are necessarily obtained;

Step2:

A set of parameters, including P, T_CR, T_RR, and R, are input;

Step3:

The total consumed time (TCT) is estimated with current facility number that may be adjusted.

Step4:

The proper algorithm is selected by judging whether the TCT is more than preset T_max. Then, the optimal solution is obtained based on the selected algorithm.

Step5:

Judge whether CR corresponding to optimal solution is more than T_CR:

• If no, it is necessary to judge whether current facility number is equal to P:
  • If yes, the present solution is the optimal solution.
  • Otherwise; the current facility number needs to add one.
• Otherwise, judge whether RR is more than T_RR:
  • If yes, the present solution is the optimal solution.
  • Otherwise, the current facility number needs to subtract one.

4. Application in Real Railway Network

The near-full covering problem proposed in this study is applied in an optimal location of a rescue spot in the railway network of the China Railway Nanchang Group with 44 nodes and 47 edges, with a total length of 3926 km. This railway network structure is depicted in Figure 4. The detailed description about the railway network is presented in Appendix A (

Table A1. Indices of all the stations.

Station	Vertex Index	Station	Vertex Index	Station	Vertex Index	Station	Vertex Index
Xiamen	1	Tangang	13	Ganzhou	25	Changji	37
Zhangzhoudong	2	Zhangjiashan	14	Dingnan	26	Xiayang	38
Meishuikeng	3	Fenyi	15	Yingli	27	Jiangbiancun	39
Zhangping	4	Liling	16	Nanpingnan	28	Shangtang	40
Yongan	5	Chaling	17	Yanshanxi	29	Dongjia	41
Waiyang	6	Wenzhu	18	Mawei	30	Jianshan	42
Yingtan	7	Jiangjia	19	Shicuo	31	Jiafu	43
Yushan	8	Xiangtang	20	Lepingshi	32	Sanjiangzhen	44
Shangrao	9	Jiujiangxi	21	Xiangtun	33
Hengfeng	10	Konglong	22	Longyan	34
Guixi	11	Ruichang	23	Yongding	35
Liangjiadong	12	Jiujiangbei	24	Zhangzhou	36

and

Table A2. Link lengths of the China Railway Nanchang Group Railway Network.

Link	Link Length (km)	Link	Link Length (km)	Link	Link Length (km)	Link	Link Length (km)
(23,21)	29	(10,11)	47	(4,3)	20	(2,36)	12
(21,24)	20	(11,7)	21	(3,2)	106	(20,12)	7
(22,21)	40	(7,12)	109	(2,1)	55	(14,41)	24
(21,20)	150	(12,13)	16	(28,6)	29	(41,40)	24
(20,19)	7	(13,14)	54	(28,30)	179	(41,42)	45
(19,44)	8	(14,15)	97	(3,37)	65	(19,13)	5
(25,26)	148	(15,16)	134	(37,31)	155	(44,39)	107
(27,32)	92	(16,17)	119	(37,38)	24	(44,25)	369
(32,11)	97	(15,18)	153	(25,34)	297	(10,29)	23
(32,33)	50	(7,6)	289	(5,43)	31	(9,29)	47
(8,9)	30	(6,5)	120	(4,34)	68	(28,29)	228
(9,10)	48	(5,4)	104	(34,35)	58

). We numbered all the nodes, and represented the lengths of all the edges. In terms of this near-full covering problem, the effects of a series of parameters under diverse scenarios are also evaluated.

4.1. Joint Impact of Coverage Radius and Coverage Rate Threshold

The coverage radius of the emergency rescue spot is related to minimum rescue time and average speed of the rescue train. Generally, the speed of the rescue train is approximately 100 km/h, and allowable rescue time should be less than 1 h. Therefore, coverage radius of the rescue spot is set as about 200 km. In real cases, it is allowed that the coverage radius of the rescue spot is given from 180 km to 250 km [30]. For the proposed location problem, coverage radius and coverage rate threshold have a joint effect on the result of the optimal location of rescue spots. Therefore, we conduct a series of parametrical analyses to reveal this joint impact. The minimum R should be not less than half of the maximum edge length (369 km). The values of the radius are set as 185, 200, 220, and 240 km, while the coverage rate threshold ranges from 0.88 to 1.00 with an interval of 0.1. The value of T_RR is set as 0.3. It is worth noting that the value of T_RR can be adjusted based on the actual requirement. The outputs are facility number, CR, and RR. It is also stated that all the numerical experiments are conducted under a basic scenario, i.e., the ACS is totally equal to the node set. The related results are summarized in

Table 1. Calculation results for values of R and T_CR.

R (km)	TCR	CR	RR	Number of Facilities	Facility Index of the Optimal Solution
185	0.88	0.959	0.271	6	[12,4,28,25,11,15]
	0.89	0.959	0.271	6	[12,4,28,25,11,15]
	0.9	0.959	0.271	6	[12,4,28,25,11,15]
	0.91	0.959	0.271	6	[12,4,28,25,11,15]
	0.92	0.959	0.271	6	[12,4,28,25,11,15]
	0.93	0.959	0.271	6	[12,4,28,25,11,15]
	0.94	0.959	0.271	6	[12,4,28,25,11,15]
	0.95	0.959	0.271	6	[12,4,28,25,11,15]
	0.96	0.977	0.352	7	[12,4,28,25,11,15,16]
	0.97	0.977	0.352	7	[12,4,28,25,11,15,16]
	0.98	0.990	0.393	8	[12,4,28,25,11,15,16,31]
	0.99	0.990	0.393	8	[12,4,28,25,11,15,16,31]
	1	1.000	0.544	11	[12,4,28,25,11,15,16,31,44,21,27]
200	0.88	0.904	0.265	5	[12,4,28,25,11]
	0.89	0.904	0.265	5	[12,4,28,25,11]
	0.9	0.904	0.265	5	[12,4,28,25,11]
	0.91	0.977	0.331	6	[12,4,28,25,11,15]
	0.92	0.977	0.331	6	[12,4,28,25,11,15]
	0.93	0.977	0.331	6	[12,4,28,25,11,15]
	0.94	0.977	0.331	6	[12,4,28,25,11,15]
	0.95	0.977	0.331	6	[12,4,28,25,11,15]
	0.96	0.977	0.331	6	[12,4,28,25,11,15]
	0.97	0.977	0.331	6	[12,4,28,25,11,15]
	0.98	0.990	0.417	7	[12,4,28,25,11,15,16]
	0.99	1.000	0.465	8	[12,4,28,25,11,15,16,31]
	1	1.000	0.465	8	[12,4,28,25,11,15,16,31]
220	0.88	0.933	0.249	5	[12,4,28,25,15]
	0.89	0.933	0.249	5	[12,4,28,25,15]
	0.9	0.933	0.249	5	[12,4,28,25,15]
	0.91	0.933	0.249	5	[12,4,28,25,15]
	0.92	0.933	0.249	5	[12,4,28,25,15]
	0.93	0.933	0.249	5	[12,4,28,25,15]
	0.94	0.987	0.436	6	[12,4,28,25,15,7]
	0.95	0.987	0.436	6	[12,4,28,25,15,7]
	0.96	0.987	0.436	6	[12,4,28,25,15,7]
	0.97	0.987	0.436	6	[12,4,28,25,15,7]
	0.98	0.987	0.436	6	[12,4,28,25,15,7]
	0.99	0.995	0.486	7	[12,4,28,25,15,7,16]
	1	1.000	0.652	8	[12,4,28,25,15,7,16,3]
240	0.88	0.936	0.394	5	[12,5,25,7,15]
	0.89	0.936	0.394	5	[12,5,25,7,15]
	0.9	0.936	0.394	5	[12,5,25,7,15]
	0.91	0.936	0.394	5	[12,5,25,7,15]
	0.92	0.936	0.394	5	[12,5,25,7,15]
	0.93	0.936	0.394	5	[12,5,25,7,15]
	0.94	0.974	0.597	6	[12,5,25,7,15,3]
	0.95	0.974	0.597	6	[12,5,25,7,15,3]
	0.96	0.974	0.597	6	[12,5,25,7,15,3]
	0.97	0.974	0.597	6	[12,5,25,7,15,3]
	0.98	0.997	0.742	7	[12,5,25,7,15,3,6]
	0.99	0.997	0.742	7	[12,5,25,7,15,3,6]
	1	1.000	0.793	8	[12,5,25,7,15,3,6,13]

.

According to the calculation results, it can be seen that the values of CR and RR have an obviously nonlinear change with T_CR at a fixed R value. For example, with the increasing of T_CR from 0.88 to 1, the values of CR and RR for R of 180 km have three step changes that appear at T_CR transitions of 0.95~0.96, 0.97~0.98, and 0.99~1, respectively. If T_CR is set as 0.95, the CR will be up to 0.959 with only 6 facilities. There will be an additional 5 facilities if all the edge is totally covered. To some extent, this input in full coverage seems to be non-economic. This effect may be magnified for some specific network with more end-branches, as shown in Figure 1. Of course, the optimal solution set must have a change at each transition. This phenomenon is mainly caused by adjusting of the facility number required by the constraint of T_CR. Based on this result, we can set an economic T_CR to obtain a near-full covering for a specific network. When T_CR for R of 200 km is given as 0.97, adding one facility just increases the value of CR from 0.977 to 0.990, but also makes the value of RR increase from 0.331 to 0.417. Therefore, the related results show that it is valuable to adopt the near-full covering problem with proper T_CR in some cases. The finding about the changes of CR and RR with T_CR has a meaningful guide for this application, but still needs to be re-evaluated for other network structures.

For larger R, there are fewer facility numbers and/or larger CR at same T_CR. When T_CR is equal to 0.92, the CR for R of 200 km is larger than that for R of 180 km. Compared with R of 200 km, there are fewer facility numbers for R of 200 km. In some cases, there are both the increasing of R and decreasing of facility numbers. However, it is obvious that a larger R may also lead to a larger RR with the same facility number. This means that more of the edge region is repeatedly covered by facilities with larger coverage radius. With the constraint of T_CR, reasonable design of R is vital for fewer facility numbers and smaller RR. Based on the above consideration, the case for R of 220 km and T_CR of 0.93 only requires 5 facilities to achieve the satisfied CR and low RR.

4.2. Comparative Analysis of Optimal Location and Existing Facility Layout

To show improvement, we conducted a comparative analysis of optimal location obtained based on the near-full covering model and existing emergency rescue spots of the railway network of the China Railway Nanchang Group. Based on operational speed and maximum rescue time, we set the coverage radius as 200 km. Optimal results obtained based on the developed method show that only 6 facilities, whose numbers are 12, 4, 28, 25, 11, and 15, can achieve CR of 0.977 and RR of 0.331. For the real situation, there are 13 emergency rescue spots in the railway network of the China Railway Nanchang Group [31]. We undertook an approximate processing for location information of existing emergency rescue spots. Their numbers on Figure 4 are 1, 4, 5, 6, 7, 9, 15, 16, 20, 21, 25, 30, and 32, respectively. Although the existing emergency rescue spot can fully cover all the edges, it must bring a very high RR value, meaning heavily redundant covering ability. However, more spots may also bring a shorter average rescue time. If the maximum allowable rescue time can be satisfied, optimal location of the emergency spot is necessary to save economic input. All in all, the optimal solution is still better than the existing facility layout.

5. The Near-Full Covering Problem with Diverse Scenarios

5.1. Definition of Diverse Scenarios

In this problem, rescue demand is distributed over the edge, while potential location of relief spots is set as nodes in the network. To construct diverse scenarios, we also defined 5 node sets, i.e., the primary candidate set N₀ (N₀ ⊆ N); the removed node set N_r (N_r ⊆ N₀); the important node set N_im (N_im ⊆ N_r); the exclusive node set N_ex (N_ex ∪ N_im = N_r); and the available candidate set N_a (N_a = N₀\N_r). The facility location set is denoted by P = {P₁, P₂, …, P_p}, where $\left|P\right|=p$. Figure 5 shows the relationship of these defined sets in the ACS-based multiple scenarios.

In Scenario 1, the N_a is totally equal to N₀, and the N_r is empty. In this situation, the task is to obtain |P| from N₀. In Scenario 2, the N_r belongs to N₀ and P simultaneously. The task is to select (|P|--|N_r|) facilities from the ACS that are equal to N₀|N_r. In practice, some important nodes must be selected as facility locations. After that, the remaining facility location in $P$ is determined. In Scenario 3, N_r consists of N_im and N_ex. The task is to select (p-|N_im|) facilities from the ACS that are equal to N₀\N_r. This means that there are some important nodes that must be selected and some exclusive nodes that must not be selected. In Scenario 4, the N_a is equal to N_ex, and the N_im is empty. The task is to determine p facilities from the ACS that is equal to N₀\N_ex. This case appears when some exclusive positions must be removed from the N₀. Basically, the above four scenarios may possibly appear in the railway emergency rescue management.

5.2. Optimal Location in Diverse Scenarios

We study the near-full covering problem in the four scenarios described above (Scenario 1, Scenario 2, Scenario 3, and Scenario 4). First, we need to discuss how to obtain the primary candidate set N₀. For the near-full covering problem, optimal facilities are not located at the end-nodes with nodal degrees of 1. The set of all the end-nodes is noted by N_en. Based on the calculation results in Section 4.1, we remove all the end-nodes to generate the ACS. For all the following scenarios, the T_CR is set as 0.95, and R is given as 200 km.

Scenario 1: The task is to determine optimal facility location set from the N₀. This scenario can be used in the optimal location of new facilities or non-limited relocation of the existing facility layout.

Scenario 2: The task is to determine (p-|N_im|) facilities from the ACS that are equal to N₀|N_im. This scenario is available for the special case in which some |N_im| facilities must be selected. For example, some stations must be selected as locations of rescue spots. We randomly generated the N_r, and assume that the |N_r| is equal to 3. Note that the N_r belongs to N₀ and P at the same time.

Scenario 3: The task is to select (p-|N_im|) facilities from the ACS that are equal to N₀\(N_im ∪ N_ex). This scenario is available for the case in which |N_ex| nodes must not be the candidate node and N_im nodes must be the facility location. For example, some stations must be selected as facility locations, while some stations must not be selected. We assume that |N_im| and |N_ex| are equal to 2 and 2, respectively.

Scenario 4: The task is to select p facilities from the ACS that are equal to N₀\N_r. This scenario is available for the case in which N_r nodes must not be the candidate node. We assume that |N_r| is equal to 3.

The detailed descriptions of all the scenarios and their calculation results are listed in

Table 2. Calculation results in diverse scenarios.

Cases	N0	Nim	Nex	CR	RR	Facility Index of the Optimal Solution
Basic *	N	[]	[]	0.9765	0.3314	[4, 11, 12, 15, 25, 28]
Scenario 1	N|Nen	[]	[]	0.9765	0.3314	[4, 11, 12, 15, 25, 28]
Scenario 2	N|Nen	[6, 13, 41]	[]	0.9765	0.5961	[4, 6, 11, 12, 13, 15, 25, 28, 41]
		[6, 13, 41] **	[] **	0.7684 **	0.3761 **	[4, 6, 11, 13, 25, 41] **
Scenario 3	N|Nen	[6, 13]	[5, 11]	0.9735	0.4897	[4, 6, 7, 13, 15, 25, 28]
Scenario 4	N|Nen	[]	[5,11,15]	0.9654	0.3350	[4, 7, 12, 16, 25, 28]

* A basic scenario in which ACS is equal to N. ** Another version of Scenario 2 in which facility number is not more than 6. [] refers to empty set.

.

For Scenario 1, all the results including CR and RR as well as optimal solution are totally equal to those in the basic scenario. Although the removal of N_en can reduce the size of ACS, it has no effect on the optimal results. This indicates that this reduction method of ACS size is effective. In Scenario 2, the N_im is first given. Compared to Scenario 1, total facility number is up to 8 to meet the requirement that CR is more than 0.95, resulting in the higher value of RR. The existing N_im has a significant effect on the calculation result. For example, if all the elements in the N_im belong to the optimal solution in Scenario 1, its optimal solution will be same as that of Scenario 1. If total facility number must not exceed 6, the maximum value of CR is only 0.7684. In Scenario 3, N_im and N_ex are not both empty, meaning that node 6 and node 13 must exist at the optimal solution, and node 5 and node 11 cannot be selected. In this case, 7 facilities in the optimal solution are needed. Compared to Scenario 1, it has a lower CR and higher RR. For Scenario 4, the N_ex with 3 elements is given. Node 11 and node 15 both belong to the optimal solution in Scenario 1. Although the total facility number is still 6, it leads to lower CR and RR. All in all, if the N_im includes any element out of optimal solution in the basic scenario, or the N_ex includes any element in the optimal solution in the basic scenario, the optimal solution will have worse performance, i.e., there are more facility numbers, or lower CR, or higher RR. Moreover, it is proved that the near-full covering problem proposed in this study is also feasible in diverse scenarios. In real applications, the actual location case can be constructed by flexibly adjusting the important node set and the exclusive node set.

6. Discussion

In terms of location problem, the near-full covering problem developed in this study is actually an extension of the edge covering location problem in which demand is distributed over all the edges and facility candidate points are located at the network nodes. Typically, the edge maximum covering location problem is to maximize the total edge length covered by using a fixed facility number [21,22]. The method developed in this work is to determine an optimal facility set that has the minimum facility number to satisfy a preset covering rate. Generally, the developed method can also avoid a common phenomenon in the full coverage problem where there are redundant covering abilities or more facilities. This type of location problem is extremely valuable for several applications, such as the location of emergency rescue depots.

Regarding the algorithm, the P2 algorithm developed in the works of Berman et al. [22] has fewer decision variables and constraints relative to the Network Intersect Point Set (NIPS), but it totally adopted a heuristic procedure for solving large-scale problems. Although the heuristic procedure has an obvious reduction in consumed time, it may usually sacrifice solution precision. In this work, an effective solution algorithm that automatically selects an effective algorithm or a greedy algorithm based on the estimated consumed time was developed to balance consumed time and solution precisely.

To deal with diverse situations in the real applications, we constructed four typical scenarios by introducing the important node set and the exclusive node set. The flexible adjustments of the two sets are conducted based on the actual requirement. For example, some important nodes are necessarily selected, while some nodes cannot be selected for varying reasons. Of course, when these two sets are both empty, this scenario is a common case in which the candidate set is not limited. According to the review analysis, the literature on diverse scenarios is certainly rare. Thus, this point is considered to be valuable. In addition, application of the developed near-full covering model in the location of emergency rescue spots on a real railway network under diverse scenarios is a new and important insight.

7. Conclusions

In this article, we explored a near-full covering problem for edge demand on the network in which coverage rate may be less than 1. A relative redundancy was defined to measure the repeated covering extent. We developed an effective solution algorithm for this problem that has the ability to automatically select an effective algorithm or a greedy algorithm based on the estimated consumed time. In addition, we constructed four general scenarios to extend the application of the proposed location problem, which are also successfully applied into the optimal location of high-speed railway rescue spots. In terms of interactions among the parameters, although larger coverage radius can lead to fewer facility numbers, it can also bring higher relative redundancy. Compared to the near-full covering, full covering can ensure that all the edge can be covered, but requires a large number of additional facilities. In real application, the results also show that facility number for optimal solution based on near-full covering model is only half of that for the existing facility layout. These indicate that developing the near full-covering model that can achieve a balance between facility number and covering ability is an important and valuable task. For diverse scenarios, the important node set and the exclusive node set given first based on actual situations may have a negative effect on coverage rate and relative redundancy as well as facility number. This study not only extends the versions of the location problem with edge demand on a network, but also provides a feasible method for diverse scenarios for optimal location of high-speed railway rescue spot.

In future works, a coupling of the hierarchical facility location with the near-full covering model may be further conducted, especially for interactions among different levels of facilities. Additionally, some objectives about environmental factors can be inserted in this location problem.