Maximum independent set in planning freight railway transportation

Abstract

This work is devoted to the problem of planning of freight railway transportation. We define a special conflict graph on the basis of a set of acceptable train routes. The investigation aims to solve the classical combinatorial optimization problem in relation to the maximum independent set of vertices in undirected graphs. The level representation of the graph and its tree are introduced. With use of these constructions, the lower and upper bounds for the number of vertices in the maximum independent set are obtained.

Keywords

independent set / algorithm / planning of transportation / two-sided estimate

Introduction

The problems that arise from managing transport processes have a special scientific and practical actuality in view of the importance of their effective solution for economic development and ensuring the connections of territories.

Planning of freight railway transportation was investigated in the context of scheduling theory in (^{Burdett and Kozan, 2010}; ^{Gholami et al., 2012};. ^{Gholami and Sotskov, 2014}; ^{Akimova et al., 2015}; ^{Gafarov et al., 2015}; ^{Gainanov et al., 2016}; ^{Lazarev et al., 2018}). In this case, the schedules necessary for execution were built directly under the current conditions of the availability of network resources. ^{Pei et al. (2017a}, ^b) also developed several hybrid algorithms in scheduling, where a number of effective novel operators of variable neighborhood search was proposed. The computational results showed the good performance of these algorithms.

The development of railway network infrastructure is conservative and requires large-scale investments. By contrast, the demand for freight railway transportation is characterized by significant dynamics in terms of total traffic volume and the distribution of traffic across various sections of railway networks. Under these conditions, infrastructure resources or railway network capacity is deficient. In this regard, developing methods of planning of freight railway transportation, which will enable transportation without significant modernization of railway infrastructure, is becoming increasingly important.

In this work, the problem under investigation obtains a fundamentally new interpretation in terms of the classical combinatorial optimization problem. The main concept of the proposed approach is to form a set of potential train routes whose executions do not contradict each other. Thus, any subset of routes from this set can serve as a valid schedule. In terms of graph theory, this problem aims to explore the maximum independent set of vertices in undirected graphs.

Identifying the maximum independent set is a classical NP-hard problem. In this regard, developing algorithms that are effective in terms of computational complexity is actual. In other studies (^{Dasgupta et al., 2006}; ^{Korte and Vygen, 2008}; ^{Skiena, 2008}), general approaches to developing exact, approximate, and heuristic algorithms were explored. In another set of studies (^{Duarte A et al., 2015}; ^{Todosijevic and Mladenovic, 2016}; ^{Hansen et al., 2017}), significant results were obtained in the field of development of metaheuristic algorithms, such as solving applied problems of production control and transport processes.

In this research, we propose an approach in which two-sided estimates can be obtained for the number of vertices in the maximum independent set. This approach mainly aims to evaluate the accuracy of approximate solutions, which can be obtained by any available method, such as heuristic and metaheuristic algorithms. In addition, implementing the approach for different root vertices means that an exact solution can be expected when the lower and upper bounds coincide.

The paper is organized as follows. Section 1 presents a general formulation of the problem of planning of railway freight transportation. We also formalize a method for reducing the applied problem to finding the maximum independent set. Section 2 describes the approximate algorithm and its modification for the class of trees. In Section 3, special graph constructions of the level representation and its tree are introduced. These constructions underlie the proposed approach. Section 4 provides the lower and upper bounds for the number of vertices in the maximum independent set. An approximate algorithm and its modification for a class of trees are used to obtain these estimates. Section 6 presents the conclusion, an overview of the main results, and directions for further research.

Planning of freight railway transportation

In this section, the formulation of the private problem of planning of freight railway transportation is presented. In general, a set of potential train routes is required for the execution of a specific transportation plan. However, the selected routes cannot often be performed due to their intersections at stations and time of movement, which entail significant economic and time costs to execute the plan. In this connection, the problem of forming such a set of potential routes, that is, selecting any of the routes does not contradict the practical implementation, becomes actuality.

Consider the directed graph of the railway transport network

\overrightarrow{\Gamma }=(S,E)\hspace{0.17em},

where

S=\hspace{0.17em}\hspace{0.17em}\{s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_n\}

is a set of stations and

E\subseteq {\displaystyle \underset{i,j}{\cup }(s_i,s_j)}

is a set of directed railroads that connect stations.

Definition 2.1. The normative thread of the train traffic schedule is a sequence of the form

\mathrm{n}:(s_{i_{\mathrm{1}}}(\mathrm{n}),s_{i_{\mathrm{2}}}(\mathrm{n}),No{m}_{i_{\mathrm{1}}{i}_{\mathrm{2}}}(\mathrm{n}),t_{i_{\mathrm{1}}{i}_{\mathrm{2}}}^{\mathrm{dep}}(\mathrm{n}),t_{i_{\mathrm{1}}{i}_{\mathrm{2}}}^{\mathrm{arr}}(\mathrm{n}),g_{i_{\mathrm{1}}{i}_{\mathrm{2}}}(\mathrm{n},t))\hspace{0.17em},

(s_{i_{\mathrm{2}}}(\mathrm{n}),s_{i_{\mathrm{3}}}(\mathrm{n}),No{m}_{i_{\mathrm{2}}{i}_{\mathrm{3}}}(\mathrm{n}),t_{i_{\mathrm{2}}{i}_{\mathrm{3}}}^{\mathrm{dep}}(\mathrm{n}),t_{i_{\mathrm{2}}{i}_{\mathrm{3}}}^{\mathrm{arr}}(\mathrm{n}),g_{i_{\mathrm{2}}{i}_{\mathrm{3}}}(\mathrm{n},t))\hspace{0.17em},\dots \hspace{0.17em},

\dots \hspace{0.17em},(s_{i_{k-\mathrm{1}}}(\mathrm{n}),s_{i_k}(\mathrm{n}),No{m}_{i_{k-\mathrm{1}}{i}_k}(\mathrm{n}),t_{i_{k-\mathrm{1}}{i}_k}^{\mathrm{dep}}(\mathrm{n}),t_{i_{k-\mathrm{1}}{i}_k}^{\mathrm{arr}}(\mathrm{n}),g_{i_{k-\mathrm{1}}{i}_k}(\mathrm{n},t))\hspace{0.17em},

where (s_{i_{j-\mathrm{1}}}(\mathrm{n}),s_{i_j}(\mathrm{n}))\in E and No{m}_{i_{j-\mathrm{1}}{i}_j}(\mathrm{n})\hspace{0.17em},\hspace{0.17em}{t}_{i_{j-\mathrm{1}}{i}_j}^{\mathrm{arr}}(\mathrm{n})\hspace{0.17em},\hspace{0.17em}{t}_{i_{j-\mathrm{1}}{i}_j}^{\mathrm{dep}}(\mathrm{n})\hspace{0.17em},\hspace{0.17em}{g}_{i_{j-\mathrm{1}}{i}_j}(\mathrm{n},t) are given path number, arrival time, departure time, and schedule of movement on the railroad (s_{i_{j-\mathrm{1}}}(\mathrm{n}),s_{i_j}(\mathrm{n})), respectively.

s^{\mathrm{beg}}(\mathrm{n})=s_{i_{\mathrm{1}}}(\mathrm{n}),t^{\mathrm{beg}}(\mathrm{n})=t_{i_{\mathrm{1}}{i}_{\mathrm{2}}}^{\mathrm{dep}}(\mathrm{n}),s^{\mathrm{fin}}(\mathrm{n})=s_{i_k}(\mathrm{n}),t^{\mathrm{fin}}(\mathrm{n})=t_{i_{k-\mathrm{1}}{i}_k}^{\mathrm{arr}}(\mathrm{n})\hspace{0.17em}.

Any normative thread represents a potential train route, which enables the execution of a certain transportation from the given plan.

Definition 2.2. Let {\mathrm{n}}_{\mathrm{1}},{\mathrm{n}}_{\mathrm{2}} be such threads that a directed railroad enters the sequence of each thread, and enable them to pass this railroad in the same or opposite directions yet remain on the same path.

\{\begin{array}{l}(s_i,s_j)=(s_k({\mathrm{n}}_{\mathrm{1}}),s_{k+\mathrm{1}}({\mathrm{n}}_{\mathrm{1}}))=(s_m({\mathrm{n}}_{\mathrm{2}}),s_{m+\mathrm{1}}({\mathrm{n}}_{\mathrm{2}}))\hspace{0.17em}\hfill \\ No{m}_{ij}({\mathrm{n}}_{\mathrm{1}})=No{m}_{ij}({\mathrm{n}}_{\mathrm{2}})\hspace{0.17em},\hfill \end{array}

or

\{\begin{array}{l}(s_i,s_j)=(s_k({\mathrm{n}}_{\mathrm{1}}),s_{k+\mathrm{1}}({\mathrm{n}}_{\mathrm{1}}))=(s_{m+\mathrm{1}}({\mathrm{n}}_{\mathrm{2}}),s_m({\mathrm{n}}_{\mathrm{2}}))\hspace{0.17em}\hfill \\ No{m}_{ij}({\mathrm{n}}_{\mathrm{1}})=No{m}_{ji}({\mathrm{n}}_{\mathrm{2}})\hspace{0.17em}.\hfill \end{array}

Then, if time moment t exists from the planning period [T_{\mathrm{0}},T] such that the distance between the trains following the threads {\mathrm{n}}_{\mathrm{1}} and {\mathrm{n}}_{\mathrm{2}} at this moment becomes less than the permissible distance d; that is,

|g_{ij}({\mathrm{n}}_{\mathrm{1}},t)-g_{ij}({\mathrm{n}}_{\mathrm{2}},t)|\le d,

or

|g_{ij}({\mathrm{n}}_{\mathrm{1}},t)-(l_{ij}-g_{ji}({\mathrm{n}}_{\mathrm{2}},t))|\le d\hspace{0.17em},

where l_{ij} is the given length (l_{ij}=l_{ji}) of the railroad (s_i,s_j), then normative threads {\mathrm{n}}_{\mathrm{1}} and {\mathrm{n}}_{\mathrm{2}} have unidirectional or multidirectional conflict, respectively.

Let the set of all normative threads

\mathcal{N}=\{{\mathrm{n}}_i\}\hspace{0.17em},\hspace{0.17em}i=\mathrm{1},\mathrm{2},\dots \hspace{0.17em},

be ordered with respect to the beginning time t^{\mathrm{beg}}(\mathrm{n}) and finishing time t^{\mathrm{fin}}(\mathrm{n}) of the movement by threads.

The following construction is a mathematical model of the applied problem under consideration, within the framework of which the research can be reduced to solving the classical problem of combinatorial optimization.

Definition 2.3. An undirected conflict graph is a graph whose vertices are normative threads. These vertices are connected by edge if and only if a unidirectional or multidirectional conflict exists for the respective normative threads.

G=(\mathcal{N},\epsilon ):\{{\mathrm{n}}_i,{\mathrm{n}}_j\}\in \epsilon \iff \hspace{0.17em}thereexiststheconflict\hspace{0.17em}.

The problem of planning of freight railway transportation is that of selecting the maximum conflict-free subset from an entire set of normative threads. Then, any subset of conflict-free normative threads can serve as an acceptable schedule for the organization of transportation.

Problem 2.1. For a given set of normative threads, the maximum subset has to be identified. The conflict graph generated by this subset must be empty; that is, it has no edges.

{\mathcal{N}}^{\prime }\hspace{0.17em}\subseteq \hspace{0.17em}\mathcal{N}\mathrm{.}\hspace{0.17em}

\left|{\mathcal{N}}^{\prime }\right|\hspace{0.17em}=\hspace{0.17em}\max \{\left|{\mathcal{N}}^{″}\right|:G\langle {\mathcal{N}}^{″}\rangle \hspace{0.17em}=\hspace{0.17em}({\mathcal{N}}^{″},\varnothing )\}\mathrm{.}\hspace{0.17em}

In terms of graph theory, the abovementioned problem is that of the maximum independent set of vertices in an undirected graph. In the following chapters, an approach is developed, within which estimates can be obtained for the number of vertices in the maximum independent set. Then, the solutions found by approximate methods can be characterized by their degree of closeness to the optimal solution. Conflict graphs that arise during railway operation are typically highly sparse. However, when an exact solution cannot be found, the proposed approach to estimating the approximate solution becomes rather actuality.

Algorithms for finding the maximum independent set

A previous study (^{Gainanov and Rasskazova, 2016}) provided an algorithm for inferring a monotone Boolean function that is generated by an undirected graph; this algorithm can be interpreted in terms of independent sets of vertices. The following are necessary definitions.

Definition 3.1. For an integer k\in [n-\mathrm{1}], we call a vertex v\in V of the graph G=(V,ϵ) a k-vertex, if |\mathcal{N}(v)|=k and the induced subgraph G\langle \mathcal{N}(v)\rangle of the graph G is complete.

The algorithm described in the previous study (^{Gainanov and Rasskazova, 2016}) is based on the abovementioned concept of k-vertices. That is, k vertices are included at each step in the independent set being constructed. If the algorithm converges (that is, the current set of vertices of the graph becomes empty at certain steps), then the independent set found is the maximum.

Following the source, we denote the neighborhood of vertex v in the induced subgraph G\langle V\rangle using \mathcal{N}(v,V)\subset V.

Isolated vertices can appear after excluding from the current parent set the vertex selected for inclusion in the maximum independent set being constructed.

Consider an example of the implementation of the algorithm IndSetTree(G).

Example 3.1 Let the tree G=(V,E) be given (Fig. 1).

1. S=\{\}

V=\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{5}},v_{\mathrm{6}},v_{\mathrm{7}},v_{\mathrm{8}},v_{\mathrm{9}},v_{\mathrm{10}}\}

v_{\mathrm{1}}— is not a leaf or an isolated vertex

v_{\mathrm{2}}— is a leaf

S=\{v_{\mathrm{2}}\}

V=\{v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{5}},v_{\mathrm{6}},v_{\mathrm{7}},v_{\mathrm{8}},v_{\mathrm{9}},v_{\mathrm{10}}\}

2. v_{\mathrm{3}}— is an isolated vertex

S=\{v_{\mathrm{2}},v_{\mathrm{3}}\}

V=\{v_{\mathrm{4}},v_{\mathrm{5}},v_{\mathrm{6}},v_{\mathrm{7}},v_{\mathrm{8}},v_{\mathrm{9}},v_{\mathrm{10}}\}

3. v_{\mathrm{4}},v_{\mathrm{5}}— is not a leaf or an isolated vertexv_{\mathrm{6}}— is a leaf

S=\{v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{6}}\}

V=\{v_{\mathrm{4}},v_{\mathrm{7}},v_{\mathrm{8}},v_{\mathrm{9}},v_{\mathrm{10}}\}

4. v_{\mathrm{4}},v_{\mathrm{7}}— is not a leaf or an isolated vertexv_{\mathrm{8}}— is a leaf

S=\{v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{6}},v_{\mathrm{8}}\}

V=\{v_{\mathrm{4}},v_{\mathrm{9}},v_{\mathrm{10}}\}

5. v_{\mathrm{4}}— is an isolated vertex

S=\{v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{6}},v_{\mathrm{8}}\}

V=\{v_{\mathrm{9}},v_{\mathrm{10}}\}

6. v_{\mathrm{9}}— is a leaf

S=\{v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{6}},v_{\mathrm{8}},v_{\mathrm{9}}\}

V=\{\}

End of the algorithm

At each step, either a leaf or an isolated vertex is included in the independent set. That is, the k-vertices for k=\mathrm{1} and k=\mathrm{0}. Thus, the independent set S=\{v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{6}},v_{\mathrm{8}},v_{\mathrm{9}}\} is the maximum.

The problem of the maximum independent set of vertices in a tree can be effectively solved using dynamic programming. However, structural differences remain in these approaches.

Let us consider the case when the current set of vertices at certain steps of Algorithm \mathcal{A}(G,V_{\mathrm{0}}) does not have a k-vertex.

Definition 3.2. For integersk,m\in [n-\mathrm{1}], we call a vertex v\in V of the graph G=(V,E)a (k,m)-vertex, if k=|\mathcal{N}(v)| and m=C_k^{\mathrm{2}}-|E\cap \left(\begin{array}{l}\mathcal{N}(v)\\ \mathrm{2}\end{array}\right)|.

In other words, a vertex is called a (k,m)-vertex if it has degree k and m edges are loosed in the neighborhood to be a complete induced subgraph.

Proposition 3.1. Let two graphs G_{\mathrm{1}}=(V_{\mathrm{1}},E_{\mathrm{1}}) and G_{\mathrm{2}}=(V_{\mathrm{2}},E_{\mathrm{2}}) have the same set of vertices V_{\mathrm{1}}=V_{\mathrm{2}} such that E_{\mathrm{1}}\subseteq E_{\mathrm{2}}. Then, the following inclusion holds:

{\mathbb{S}}_{\max }(G_{\mathrm{2}})\subseteq \mathbb{S}(G_{\mathrm{1}})\hspace{0.17em},

where \mathbb{S}(G) is the set of all independent sets of the graph G and {\mathbb{S}}_{\max }(G) is the set of all maximum independent sets of the graph G.

The relation between the maximum independent sets of two undirected graphs follows from Proposition 3.1. Let us define the quantity \max S(G)=\left|S\right|, where S\in {\mathbb{S}}_{\max }(G). That is, the cardinality of the maximum independent set of graph G.

Corollary 3.1. Let G_{\mathrm{1}}=(V,{ϵ}_{\mathrm{1}}) and G_{\mathrm{2}}=(V,{ϵ}_{\mathrm{2}}) be graphs such that {ϵ}_{\mathrm{1}}\subseteq {ϵ}_{\mathrm{2}}. Then,

\max S(G_{\mathrm{1}})\ge \max S(G_{\mathrm{2}})\hspace{0.17em}.

Thus, if no applicants are to be included in the independent set under construction at certain steps of Algorithm \mathcal{A}(G,V_{\mathrm{0}}), then the neighborhood of any vertex for complete subgraphs can be artificially increased by consideration of the relation between the initial and new graphs. The following statement shows the details of the relation established in Corollary 1.1.

Proposition 3.2. Let G=(V(G),E(G)) be a graph in which vertices v_i and v_j are not adjacent. Let G^{\prime }=(V(G^{\prime }),E(G^{\prime })) be a graph in which the set of vertices is the same V(G^{\prime })=V(G) and that of edges is such that E(G^{\prime })=E(G)\cup \{(v_i,v_j)\}. Hence, vertices v_i and v_j are adjacent in this graph. Then,

\max S(G)\ge \max S(G^{\prime })\ge \max S(G)-\mathrm{1}\hspace{0.17em}.

The case where the neighborhood of any vertex is increased by unique edges can be continued for a larger number of edges.

Corollary 3.2. For graph G=(V,E(G)) let e_{\mathrm{1}},\dots ,e_k\notin E(G) be a subfamily of kvertex pairs that are not edges of graph G. In addition, let graph G^{\prime }=(V,E(G^{\prime })), where E(G^{\prime })=E(G^{\prime })\cup \{e_{\mathrm{1}},\dots ,e_k\}. Then,

\max S(G)\ge \max S(G^{\prime })\ge \max S(G)-k\hspace{0.17em}.

According to Corollary 3.2, at each step of Algorithm \mathcal{A}(G,V_{\mathrm{0}}), an arbitrary vertex of the graph can be included into the independent set under construction. With consideration of the value of the parameter m of this vertex, the value of the deviation of the obtained approximate solution from the optimal one can be calculated. Let us consider the following approximate algorithm.

Algorithm ℬ(G,V) operates with several functions. Function Calculate(k,v) is used to calculate the values of parameter k for each vertex v. Function Calculate(m,v) is similarly used for calculating the values of parameter mfor each vertex v. Function MinMaxParam(v) executes the choice of the vertex with minimal values of parameter m and choice of the vertex with the maximum value of parameter k among all previously selected vertices. If the unique vertex exists with the minimum value of parameter m, then selecting the vertex with the maximum value of parameter k is unnecessary. Thus, following Proposition 3.2, we obtain the next feature that is related to Algorithm ℬ(G,V).

Proposition 3.3. Let S and Est be found by ℬ(G,V). Then

\left|S\right|\hspace{0.17em}\ge \hspace{0.17em}\left|\max S(G)\right|-Est\hspace{0.17em}.

Let us consider an example of using Algorithm ℬ(G,V) for finding an independent set of the arbitrary undirected graph. We also demonstrate the accumulation of the deviation estimate of the approximate solution from the optimal one.

Example 3.2. Let the undirected graph G=(V,E) be given by the following list of adjacency vertices.

Thus, we conclude that the maximum independent set of the initial graph contains less than 8 vertices. That is, \left|\max S(G)\right|\le \left|S\right|+Est=\mathrm{8}\hspace{0.17em}.

Section 1 states that the applied problem of planning freight railway transportation can be solved in the frame of the problem of the maximum independent set of undirected conflict graphs. Graphs that arise in such applied areas are sparse. In this connection, the approximate algorithmℬ(G,V)acquires special interest for solving the applied problem under consideration.

Level representation of the graph

Consider an undirected connected graph G=(V,E). Let v,v\in V be an arbitrary vertex of the graph G=(V,E).

Definition 4.1. The sequence of subsets of vertices of graph G=(V,E) is called level representation with the root vertex v.

\mathbb{V}(G,v):V_{\mathrm{1}}(G,v),V_{\mathrm{2}}(G,v),\dots ,V_k(G,v)\hspace{0.17em}

if it is constructed as follows:

V_{\mathrm{1}}(G,v)=\{v\}\hspace{0.17em},

V_{\mathrm{2}}(G,v)=\mathcal{N}(V_{\mathrm{1}})-V_{\mathrm{1}}(G,v)\hspace{0.17em},

\mathrm{......},

V_k(G,v)=\mathcal{N}(V_{k-\mathrm{1}})-V_{k-\mathrm{2}}(G,v)\hspace{0.17em},

V_{k+\mathrm{1}}(G,v)=\{\}\hspace{0.17em},

where a neighborhood of a subset of vertices pertains to a union of neighborhoods of vertices entering this subset. That is,

\mathcal{N}(V_i)={\displaystyle \cup \{}\mathcal{N}(v):v\in V_i(G,v)\}\hspace{0.17em}.

For definiteness, we assume that for any level in the representation \mathbb{V}(G,v), the following holds:

where n is the number of vertices of the original graph. In other words, the vertices of any level in the representation \mathbb{V}(G,v) are ordered by increasing indexes.

Suppose that the level representation \mathbb{V}(G,v) of the graph G=(V,E) with root vertex v has k levels. Consider the adjacent levels V_n(G,v) and V_{n-\mathrm{1}}(G,v), where n\in [\mathrm{2},k+\mathrm{1}]. Let

E(v_i,V_n(G,v))=\{(v_i,v_j):v_j\in V_{n-\mathrm{1}}(G,v)\}

be the set of between-level edges incident to the vertex v_i\in V_n(G,v). The edges incident to the vertices of level V_{n+\mathrm{1}}(G,v) for n\in [\mathrm{2},k-\mathrm{1}] are not considered at this stage.

For each vertex v_i\in V_n(G,v), we order the set E(v_i,V_n(G,v)) by increasing the indexes of vertices v_j. Thus, if

e_{m_{\mathrm{1}in}}=(v_i,v_{j_{\mathrm{1}}})\hspace{0.17em},\hspace{0.17em}{e}_{m_{\mathrm{1}in}}\in E(v_i,V_n(G,v))

and

e_{m_{\mathrm{2}in}}=(v_i,v_{j_{\mathrm{2}}})\hspace{0.17em},\hspace{0.17em}{e}_{m_{\mathrm{2}in}}\in E(v_i,V_n(G,v))\hspace{0.17em},

then the following holds:

Indexes m_{in} of edges in the ordered set E(v_i,V_n(G,v)) are called relative indexes of edges, that is, edges incident to vertex v_i from level V_n(G,v) and a few vertices from the previous level V_{n-\mathrm{1}}(G,v) in the representation \mathbb{V}(G,v).

Definition 4.2. The tree of level representation Tr\mathbb{V}(G,v) is a construction obtained from \mathbb{V}(G,v) by the removal of all edges in each level and between-level edges whose relative indexes are more than 1.

Tr{V}_{\mathrm{1}}(v)=\{v\}

Tr{V}_{\mathrm{2}}(v)=\{v_i:v_i\in V_{\mathrm{2}}(v)\}

and

Tr{V}_k(v)=\{v_i:v_i\in V_k(v)\}.

We note that the removal of multiples between-level edges is designed to preserve the tree structure, that is, the elimination of cycles.

Example 4.1. Figure 2 shows an undirected graph G=(V,E), its level representation with root vertex v_{\mathrm{1}}, and the corresponding tree of the level representation.

By definition, the tree of the level representation contains the same number of levels as does the level representation itself.

Estimates for the number of vertices in the maximum independent set

On the basis of the level representation, the lower and upper bounds for the number of vertices in the maximum independent set are obtained in this section. In addition, the section illustrates that Algorithms \mathcal{A}(G,V_{\mathrm{0}}), ℬ(G,V) and modified algorithm IndSetTree(G) can be used to obtain these bounds as well as any other effective algorithm.

Lower bound

Let the undirected connected graph G=(V,ϵ) be given and its level representation for an arbitrary vertex v.

Let S(G) be the maximum independent set of vertices in graph G=(V,ϵ), and S(V(G,v)) is the maximum independent set of vertices in the subgraph generated by the vertices of a certain level V(G,v). For brevity, we denote

S(V)=S(V(G,v))\hspace{0.17em},

which pertains to the maximum independent set of vertices in the corresponding level.

Let I be the set of indexes of non-adjacent levels in the level representation \mathbb{V}(G,v).

(1)I=\{i:\hspace{0.17em}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{y}\hspace{0.17em}{i}_{\mathrm{1}},i_{\mathrm{2}}\hspace{0.17em}\mathrm{h}\mathrm{o}\mathrm{l}\mathrm{d}\mathrm{s}\hspace{0.17em}|i_{\mathrm{1}}-i_{\mathrm{2}}|>\mathrm{1}\}\hspace{0.17em},

where i\in [\mathrm{1},k]. We denote the set of all maximal by inclusion sets of the form (1)

(2)\mathit{I}=\{I:\hspace{0.17em}\mathrm{for\; any}\hspace{0.17em}i\notin I\hspace{0.17em}\mathrm{one\; can\; find}\hspace{0.17em}j\in I\hspace{0.17em}\mathrm{such\; that}\hspace{0.17em}|i-j|=\mathrm{1}\}\hspace{0.17em}.

The lower bound for the maximum independent set of vertices of the graph G=(V,E) given in the form of the level representation with the root vertex v,v\in V is the quantity

(3)\left|S\right|\ge \max \left\{{\displaystyle \sum _{i\in I}\left|S(V_i)\right|},I\in ℐ\right\}\hspace{0.17em},

All levels with indexes from any set I\in ℐ are not adjacent to each other by construction. Consequently, the maximum of the sums (4) is an independent set in the graph G=(V,ϵ).

In each level, the maximum independent set of vertices S(V_i),i=[\mathrm{1},k] can be found by either algorithms \mathcal{A}(G,V_{\mathrm{0}}) and ℬ(G,V) or for each level, an analogous lower bound can be obtained. Then, the lower bound for the maximum independent set of vertices of the original graph will be no less than the greatest of the sums of the lower bounds obtained.

Thus, either a lower bound will be obtained for the maximum independent set of vertices of the original graph (if one can find the maximum independent sets of vertices for each level) or a substantial reduction in the dimension of the original problem will be achieved by moving to a series of simpler problems. The sets of indexes of even and odd non-adjacent levels and subsequent choice of the maximum of the sums of the form (3) can be naturally considered.

Upper bound

Consider the graph G=(V,E) given by its level representation \mathbb{V}(G,v) with an arbitrary root v. The tree of this level representation is Tr\mathbb{V}(G,v).

The maximum independent set of vertices in the tree Tr\mathbb{V}(G,v) can be found using the modified algorithm IndSetTree(G) (or any other algorithm, such as dynamic programming method). Then, the upper bound for the maximum independent set of vertices in the original graph is

(4)\left|S(G)\right|\le \left|S(Tr\mathbb{V}(G,v))\right|\hspace{0.17em}.

The relation (4) easily follows from Proposition 3.1. By construction, the tree of the level representation Tr\mathbb{V}(G,v) has the same vertices as the original graph. However, its set of edges is evidently smaller. Hence, inequality (4) holds under Proposition 3.1.

Two-sided estimate

Considering (3) and (4), we obtain a two-sided estimate for the maximum independent set of vertices in an undirected graph.

Proposition 5.1. Let G=(V,E) be an undirected connected graph defined by its level representation \mathbb{V}(G,v) for an arbitrary vertex v. Then,

(5)\max \left\{{\displaystyle \sum _{i\in I}\left|S(V_i)\right|},I\in ℐ\right\}\le \left|S(G)\right|\le \left|S(Tr\mathbb{V}(G,v))\right|\hspace{0.17em}.

Proof. The proof follows from the arguments presented as comments on the validity of the relations (3) and (4).

An important feature of the two-sided estimate obtained is the possibility of using it for any level representation of the original graph.

We denote LowB(v) and UpB(v) as the lower and upper bounds, respectively, of the form that is obtained for level representation with root vertex v. Then, using the abovementioned approach for each vertex of the graph, we obtain

\max \{LowB(v)\hspace{0.17em},\hspace{0.17em}v\in V\}\le \left|S(G)\right|\le \min \{UpB(v)\hspace{0.17em},\hspace{0.17em}v\in V\}\hspace{0.17em}.

Let us consider the example of using the approach described above for the undirected graph on the basis of Example 3.2.

Example 5.1. For each vertex of the graph as a root, level representations of the graph, and corresponding trees of level representations are constructed. To find the maximum independent set in each level V_i Algorithmℬ(G,V) is used. For finding the maximum independent set of the tree, Algorithm IndSetTree(G) is used. Hence, in particular, from the level representation with the root vertex v_{\mathrm{1}}, a two-sided estimate of the maximum independent set of form \mathrm{8}\le \left|S(G)\right|\le \mathrm{13}\hspace{0.17em} is obtained. Among all upper bounds, we obtain the minimum one from the level representation with root vertex v_{\mathrm{4}}, and this bound is equal to \mathrm{12}. Similarly, the maximum of the lower bounds is equal to \mathrm{8}, and this bound is obtained from the level representation with root vertex v_{\mathrm{8}}. Thus, we obtain

\max \{LowB(v)\hspace{0.17em},\hspace{0.17em}v\in V\}=LowB(v_8)=8\le \left|S(G)\right|\le 12=UpB(v_4)=\min \{UpB(v)\hspace{0.17em},\hspace{0.17em}v\in V\}\hspace{0.17em}\mathrm{.}

According to the results obtained in Example 3.2, the cardinality of the maximum independent set of the initial graph is equal to \mathrm{8}.

Conflict graphs that arise in railway operation are usually sparse. In this connection, the implementation of the approach described above for solving applied problems means that an exact solution that is a coincidence of the upper and lower bounds can be expected for the maximum independent set of vertices.

Conclusions

This work investigates the applied problem of management of transport processes at the planning stage of freight railway transportation. Within the framework of the graph model, the investigation focuses on solving the problem of finding the maximum independent set of vertices in the undirected graph. To solve this problem, special graph constructions are introduced to the level representation and tree of the level representation. On the basis of the approximate algorithm and its modification for the class of trees, the lower and upper bounds for the number of vertices in the maximum independent set are obtained. The implementation of the approach is closely related to the abovementioned graph constructions. In particular, the upper bound is obtained using a modified algorithm for the tree of level representation.

The direction of further research is mainly connected with computational experiments and using the developed approach to solve the applied problem of planning of freight railway transportation.

Another aspect of further research concerns the excess normative threads in the conflict-free set; these threads are an important feature of the developed approach. In general, this case is sufficient for the execution of an arbitrary transportation plan. However, the normative threads are unsuitable for the execution of transportation. Thus, an adapted model where each vertex of the undirected conflict graph corresponds to a certain priority must be developed. Thus, further studies of the authors’ team will be devoted to the development of such a model and effective algorithms for solving the planning problem while considering the given transportation plan.

References

[1] Akimova E, Gainanov D, Golubev O (2015). The problem of scheduling for the linear section of a single-track railway with independent edges orientations. In: Proceedings of CEUR Workshop. 1513: 130–136

[2] Burdett O, Kozan E (2010). A disjunctive graph model and framework for constructing new train schedules. European Journal of Operational Research, 200(1): 85–98

[3] Dasgupta S, Papadimitriou C, Vazirani U (2006). Algorithms. New York: McGraw-Hill

[4] Duarte A, Pantrigo J, Pardo E, Mladenovic N (2015). Multi-objective variable neighborhood search: An application to combinatorial optimization problems. Journal of Global Optimization, 63(3): 515–536

[5] Gafarov E, Dolgui A, Lazarev A (2015). Two-station single-track railway scheduling problem with trains of equal speed. Computers & Industrial Engineering, 85: 260–267

[6] Gainanov D, Konygin A, Rasskazova V (2016). Modelling railway freight traffic using the methods of graph theory and combinatorial optimization. Automation and Remote Control, 77(11): 1928–1943

[7] Gainanov D, Rasskazova V (2016). An inference algorithm for monotone boolean functions associated with undirected graphs. Bulletin of the SUSU, 9(3): 17–30

[8] Gholami O, Sotskov Y N (2014). Scheduling algorithm with controllable train speeds and departure times to decrease the total train tardiness. Int Journal of Industrial Engenering Computations, 5(2): 281–294

[9] Gholami O, Sotskov Y N, Werner F (2012). Job-shop problems with objectives appropriate to train scheduling in a single-track railway. In: Proceedings of 2nd International Conference on Simulation and Modeling Methodologies, Roma. Technologies and Applications: 425–430

[10] Hansen P, Mladenovic N, Todosijevic R, Hanafi S (2017). Variable neighborhood search: basics and variants. European Journal on Computational Optimization, 5(3): 423–454

[11] Korte B, Vygen J (2008). Combinatorial Optimization. Berlin: Springer

[12] Lazarev A, Nekrasov I, Pravdivets N (2018). Evaluating typical algorithms of combinatorial optimization to solve continuous-time based scheduling problem. Algorithms, 4(11): 1–13

[13] Pei J, Cheng B, Liu X, Pardalos P M, Kong M (2017a). Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time. Annals of Operations Research, doi: 10.1007/s10479-017-2481-8

[14] Pei J, Liu X, Fan W, Pardalos P M, Lu S (2017b). A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega, doi: 10.1016/j.omega.2017.12.003

[15] Skiena S (2008). The Algorithm Design Manual. Berlin: Springer

[16] Todosijevic R, Mladenovic N (2016). Nested general variable neighborhood search for the periodic maintenance problem. European Journal of Operational Research, 252(2): 385–396

RIGHTS & PERMISSIONS

The Author(s) 2018. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)