assignment problem in networks

Network flow problem

Author: Aaron Wheeler, Chang Wei, Cagla Deniz Bahadir, Ruobing Shui, Ziqiu Zhang (ChemE 6800 Fall 2020)

• 1 Introduction
• 2.1.1 The Assignment Problem
• 2.1.2 The Transportation Problem
• 2.1.3 The Shortest-Path Problem
• 2.1.4 Maximal Flow Problem
• 2.2.1 Ford–Fulkerson Algorithm
• 3.1 Formulation of the Problem
• 3.2 Solution of the Problem
• 4.1 The Minimum Cost Flow Problem
• 4.2 The Assignment Problem
• 4.3 The Shortest Path Problem
• 5 Conclusion
• 6 References

Introduction

Network flow problems arise in several key instances and applications within society and have become fundamental problems within computer science, operations research, applied mathematics, and engineering. Developments in the approach to tackle these problems resulted in algorithms that became the chief instruments for solving problems related to large-scale systems and industrial logistics. Spurred by early developments in linear programming, the methods for addressing these extensive problems date back several decades and they evolved over time as the use of digital computing became increasingly prevalent in industrial processes. Historically, the first instance of an algorithmic development for the network flow problem came in 1956, with the network simplex method formulated by George Dantzig. [1] A variation of the simplex algorithm that revolutionized linear programming, this method leveraged the combinatorial structure inherent to these types of problems and demonstrated incredibly high accuracy. [2] This method and its variations would go on to define the embodiment of the algorithms and models for the various and distinct network flow problems discussed here.

Theory, Methodology, and Algorithms

Additional constraints of the network flow optimization model place limits on the solution and vary significantly based on the specific type of problem being solved. Historically, the classic network flow problems are considered to be the maximum flow problem and the minimum-cost circulation problem, the assignment problem, bipartite matching problem, transportation problem, and the transshipment problem. [2] The approach to these problems become quite specific based upon the problem’s objective function but can be generalized by the following iterative approach: 1. determining the initial basic feasible solution; 2. checking the optimality conditions (i.e. whether the problem is infeasible, unbounded over the feasible region, optimal solution has been found, etc.); and 3. constructing an improved basic feasible solution if the optimal solution has not been determined. [3]

General Applications

The assignment problem.

Various real-life instances of assignment problems exist for optimization, such as assigning a group of people to different tasks, events to halls with different capacities, rewards to a team of contributors, and vacation days to workers. All together, the assignment problem is a bipartite matching problem in the kernel. [3] In a classical setting, two types of objects of equal amount are  bijective (i.e. they have one-to-one matching), and this tight constraint ensures a perfect matching. The objective is to minimize the cost or maximize the profit of matching, since different items of two types have distinct affinity.

Figure 2 can be viewed as a network. The nodes represent people and tasks, and the edges represent potential assignments between a person and a task. Each task can be completed by any person. However, the person that actually ends up being assigned to the task will be the lone individual who is best suited to complete. In the end, the edges with positive flow values will be the only ones represented in the finalized assignment. [5]

The concise-form formulation of the problem is as follows [3] :

Subject to:

The first constraint captures the requirement of assigning each person  to a single task. The second constraint indicates that each task must be done by exactly one person. The objective function sums up the overall benefits of all assignments.

To see the analogy between the assignment problem and the network flow, we can describe each person supplying a flow of 1 unit and each task demanding a flow of 1 unit, with the benefits over all “channels” being maximized. [3]

A potential issue lies in the branching of the network, specifically an instance where a person splits its one unit of flow into multiple tasks and the objective remains maximized. This shortcoming is allowed by the laws that govern the network flow model, but are unfeasible in real-life instances. Fortunately, since the network simplex method only involves addition and subtraction of a single edge while transferring the basis, which is served by the spanning tree of the flow graph, if the supply (the number of people here) and the demand (the number of tasks here) in the constraints are integers, the solved variables will be automatically integers even if it is not explicitly stated in the problem. This is called the integrality of the network problem, and it certainly applies to the assignment problem. [6]

The Transportation Problem

People first came up with the transportation problem when distributing troops during World War II. [7] Now, it has become a useful model for solving logistics problems, and the objective is usually to minimize the cost of transportation.

Consider the following scenario:

Several quantities should be defined to help formulate the frame of the solution:

Here, the amount of material being delivered and being consumed is bound to the supply and demand constraints:

The objective is to find the minimum cost of transportation, so the cost of each transportation line should be added up, and the total cost should be minimized.

Using the definitions above, the problem can be formulated as such:

The problem and the formulation is adapted from Chapter 8 of the book: Applied Mathematical Programming by Bradley, Hax and Magnanti. [3]

The Shortest-Path Problem

The shortest-path problem can be defined as finding the path that yields the shortest total distance between the origin and the destination. Each possible stop is a node and the paths between these nodes are edges incident to these nodes, where the path distance becomes the weight of the edges. In addition to being the most common and straightforward application for finding the shortest path, this model is also used in various applications depending on the definition of nodes and edges. [3] For example, when each node represents a different object and the edge specifies the cost of replacement, the equipment replacement problem is derived. Moreover, when each node represents a different project and the edge specifies the relative priority, the model becomes a project scheduling problem.

A graph of the general shortest-path problem is depicted as Figure 4:

The first term of the constraint is the total outflow of the node i, and the second term is the total inflow. So, the formulation above could be seen as one unit of flow being supplied by the origin, one unit of flow being demanded by the destination, and no net inflow or outflow at any intermediate nodes. These constraints mandate a flow of one unit, amounting to the active path, from the origin to the destination. Under this constraint, the objective function minimizes the overall path distance from the origin to the destination.

Similarly, the integrality of the network problem applies here, precluding the unreasonable fractioning. With supply and demand both being integer (one here), the edges can only have integer amount of flow in the result solved by simplex method. [6]

In addition, the point-to-point model above can be further extended to other problems. A number of real life scenarios require visiting multiple places from a single starting point. This “Tree Problem” can be modeled by making small adjustments to the original model. In this case, the source node should supply more units of flow and there will be multiple sink nodes demanding one unit of flow. Overall, the objective and the constraint formulation are similar. [4]

Maximal Flow Problem

This problem describes a situation where the material from a source node is sent to a sink node. The source and sink node are connected through multiple intermediate nodes, and the common optimization goal is to maximize the material sent from the source node to the sink node. [3]

The given structure is a piping system. The water flows into the system from the source node, passing through the intermediate nodes, and flows out from the sink node. There is no limitation on the amount of water that can be used as the input for the source node. Therefore, the sink node can accept an unlimited amount of water coming into it. The arrows denote the valid channel that water can flow through, and each channel has a known flow capacity. What is the maximum flow that the system can take?

For the source and sink node, they have net flow that is non-zero:

Flow capacity definition is applied to all nodes (including intermediate nodes, the sink, and the source):

The main constraints for this problem are the transport capacity between each node and the material conservation:

Overall, the net flow out of the source node has to be the same as the net flow into the sink node. This net flow is the amount that should be maximized.

Using the definitions above:

This expression can be further simplified by introducing an imaginary flow from the sink to the source.

By introducing this imaginary flow, the piping system is now closed. The mass conservation constraint now also holds for the source and sink node, so they can be treated as the intermediate nodes. The problem can be rewritten as the following: 

The problem and the formulation are derived from an example in Chapter 8 of the book: Applied Mathematical Programming by Bradley, Hax and Magnanti. [3]

Ford–Fulkerson Algorithm

A broad range of network flow problems could be reduced to the max-flow problem. The most common way to approach the max-flow problem in polynomial time is the Ford-Fulkerson Algorithm (FFA). FFA is essentially a greedy algorithm and it iteratively finds the augmenting s-t path to increase the value of flow. The pathfinding terminates until there is no s-t path present. Ultimately, the max-flow pattern in the network graph will be returned. [8]

Numerical Example and Solution

A Food Distributor Company is farming and collecting vegetables from farmers to later distribute to the grocery stores. The distributor has specific agreements with different third-party companies to mediate the delivery to the grocery stores. In a particular month, the company has 600 ton vegetables to deliver to the grocery store. They have agreements with two third-party transport companies A and B, which have different tariffs for delivering goods between themselves, the distributor, and the grocery store. They also have limits on transport capacity for each path. These delivery points are numbered as shown below, with path 1 being the transport from the Food Distributor Company to the transport company A. The limits and tariffs for each path can be found in the Table 2 below, and the possible transportation connections between the distributor company, the third-party transporters, and the grocery store are shown in the figure below. The distributor companies cannot hold any amount of food, and any incoming food should be delivered to an end point. The distributor company wants to minimize the overall transport cost of shipping 600 tons of vegetables to the grocery store by choosing the optimal path provided by the transport companies. How should the distributor company map out their path and the amount of vegetables carried on each path to minimize cost overall?

This question is adapted from one of the exercise questions in chapter 8 of the book: Applied Mathematical Programming by Bradley, Hax and Magnanti [3] .

Formulation of the Problem

The second step is to write down the constraints. The first constraint ensures that the net amount present in the Transport Company A, which is the deliveries received from path 1 and path 2 minus the transport to Transport Company B should be delivered to the grocery store with path 5. The second constraint ensures this for the Transport Company B. The third and fourth constraints are ensuring that the total amount of vegetables shipping from the Food Distributor Company and the total amount of vegetables delivered to the grocery store are both 600 tons. The constraints 5 to 10 depict the upper limits of the amount of vegetables that can be carried on paths 1 to 6. The final constraint depicts that all variables are non-negative.

Solution of the Problem

This problem can be solved using Simplex Algorithm [11] or with the CPLEX Linear Programming solver in GAMS optimization platform. The steps of the solution using the GAMS platform is as follows:

variables x1,x2,x3,x4,x5,x6,z;

obj.. z=e= 10*x1+12.5*x2+5*x3+7.5*x4+10*x5+20*x6;

Overall, there are 10 constraints in this problem. The constraints 1, and 2 are equations for the paths 5 and 6. The amount carried in path 5 can be found by summing the amount of vegetables incoming to Transport Company A from path 1 and path 4, minus the amount of vegetables leaving Transport Company A with path 3. This can be attributed to the restriction that barrs the companies from keeping any vegetables and requires them to eventually deliver all the incoming produce. The equality 1 ensures that this constraint holds for path 5 and equation 2 ensures it for path 6. A sample of these constraints is written below for path 5:

c1.. x5 =e=x1-x3+x4;

Constraint 3 ensures that the sum of vegetables carried in path 1 and path 2 add to the total of 600 tons of vegetables that leave the Food Distributor Company. Likewise, the constraint 4 ensures that the sum amount of food transported in paths 5 and 6 adds up to 600 tons of vegetables that have to be delivered to the grocery store. A sample of these constraints is written below for the total delivery to the grocery store:

c3.. x5+x6=e=600;

Constraints 5 to 10 should ensure that the amount of food transported in each path should not exceed the maximum capacity depicted in the table. A sample of these constraints is written below for the capacity of path 1:

c5.. x1=l=250;

After listing the variables, objective function and the constraints, the final step is to call the CPLEX solver and set the type of the optimization problem as lp (linear programming). In this case the problem will be solved with a Linear Programming algorithm to minimize the objective (cost) function.

The GAMS code yields the results below:

x1 = 250, x2 = 350, x3 = 0, x4 = 50, x5 = 300, x6 = 300, z =16250.

Real Life Applications

Network problems have many applications in all kinds of areas such as transportation, city design, resource management and financial planning. [6]

There are several special cases of network problems, such as the shortest path problem, minimum cost flow problem, assignment problem and transportation problem. [6] Three application cases will be introduced here.

The Minimum Cost Flow Problem

Minimum cost flow problems are pervasive in real life, such as deciding how to allocate temporal quay crane in container terminals, and how to make optimal train schedules on the same railroad line. [12]

R. Dewil and his group use MCNFP to assist traffic enforcement. [13] Police patrol “hot spots”, which are areas where crashes occur frequently on highways. R. Dewil studies a method intended to estimate the optimal route of hot spots. He describes the time it takes to move the detector to a certain position as the cost, and the number of patrol cars from one node to next as the flow, in order to minimize the total cost. [13]

Dung-Ying Lin studies an assignment problem in which he aims to assign freights to ships and arrange transportation paths along the Northern Sea Route in a manner which yields maximum profit. [14] Within this network  composed of a ship subnetwork and a cargo subnetwork( shown as Figure 12 and Figure 13), each node corresponds to a port at a specific time and each arc represents the movement of a ship or a cargo. Other types of assignment problems are faculty scheduling, freight assignment, and so on.

The Shortest Path Problem

Shortest path problems are also present in many fields, such as transportation, 5G wireless communication, and implantation of the global dynamic routing scheme. [15][16][17]

Qiang Tu and his group studies the constrained reliable shortest path (CRSP) problem for electric vehicles in the urban transportation network. [15] He describes the reliable travel time of path as the objective item, which is made up of planning travel time of path and the reliability item. The group studies the Chicago sketch network consisting of 933 nodes and 2950 links and the Sioux Falls network consisting of 24 nodes and 76 links. The results show that the travelers’ risk attitudes and properties of electric vehicles in the transportation network can have a great influence on the path choice. [15] The study can contribute to the invention of the city navigation system.

Since its inception, the network flow problem has provided humanity with a straightforward and scalable approach for several large-scale challenges and problems. The Simplex algorithm and other computational optimization platforms have made addressing these problems routine, and have greatly expedited efforts for groups concerned with supply-chain and other distribution processes. The formulation of this problem has had several derivations from its original format, but its overall methodology and approach have remained prevalent in several of society’s industrial and commercial processes, even over half a century later. Classical models such as the assignment, transportation, maximal flow, and shortest path problem configurations have found their way into diverse settings, ranging from streamlining oil distribution networks along the gulf coast to arranging optimal scheduling assignments for college students amidst a global pandemic. All in all, the network flow problem and its monumental impact, have made it a fundamental tool for any group that deals with combinatorial data sets. And with the surge in adoption of data-driven models and applications within virtually all industries, the use of the network flow problem approach will only continue to drive innovation and meet consumer demands for the foreseeable future.

1. Karp, R. M. (2008). George Dantzig’s impact on the theory of computation . Discrete Optimization, 5(2), 174-185.

2. Goldberg, A. V. Tardos, Eva, Tarjan, Robert E. (1989). Network Flow Algorithms, Algorithms and Combinatorics . 9. 101-164.

3. Bradley, S. P. Hax, A. C., & Magnanti, T. L. (1977). Network Models. Applied mathematical programming (p. 259). Reading, MA: Addison-Wesley.

4. Chinneck, J. W. (2006). Practical optimization: a gentle introduction. Systems and Computer Engineering . Carleton University, Ottawa. 11.

5. Roy, B. V. Mason, K.(2005). Formulation and Analysis of Linear Programs, Chapter 5 Network Flows .

6. Vanderbei, R. J. (2020). Linear programming: foundations and extensions (Vol. 285) . Springer Nature.

7. Sobel, J. (2014). Linear Programming Notes VIII: The Transportation Problem .

8. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 26.2: The Ford–Fulkerson method". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill.

9. Jon Kleinberg; Éva Tardos (2006). "Chapter 7: Network Flow". Algorithm Design. Pearson Education.

10. Ford–Fulkerson algorithm . Retrieved December 05, 2020.

11. Hu, G. (2020, November 19). Simplex algorithm . Retrieved November 22, 2020.

12. Altınel, İ. K., Aras, N., Şuvak, Z., & Taşkın, Z. C. (2019). Minimum cost noncrossing flow problem on layered networks . Discrete Applied Mathematics, 261, 2-21.

13. Dewil, R., Vansteenwegen, P., Cattrysse, D., & Van Oudheusden, D. (2015). A minimum cost network flow model for the maximum covering and patrol routing problem . European Journal of Operational Research, 247(1), 27-36.

14. Lin, D. Y., & Chang, Y. T. (2018). Ship routing and freight assignment problem for liner shipping: Application to the Northern Sea Route planning problem . Transportation Research Part E: Logistics and Transportation Review, 110, 47-70.

15. Tu, Q., Cheng, L., Yuan, T., Cheng, Y., & Li, M. (2020). The Constrained Reliable Shortest Path Problem for Electric Vehicles in the Urban Transportation Network . Journal of Cleaner Production, 121130.

16. Guo, Y., Li, S., Jiang, W., Zhang, B., & Ma, Y. (2017). Learning automata-based algorithms for solving the stochastic shortest path routing problems in 5G wireless communication . Physical Communication, 25, 376-385.

17. Haddou, N. B., Ez-Zahraouy, H., & Rachadi, A. (2016). Implantation of the global dynamic routing scheme in scale-free networks under the shortest path strategy . Physics Letters A, 380(33), 2513-2517.

Navigation menu

Deep Neural Networks for Linear Sum Assignment Problems

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Open Access is an initiative that aims to make scientific research freely available to all. To date our community has made over 100 million downloads. It’s based on principles of collaboration, unobstructed discovery, and, most importantly, scientific progression. As PhD students, we found it difficult to access the research we needed, so we decided to create a new Open Access publisher that levels the playing field for scientists across the world. How? By making research easy to access, and puts the academic needs of the researchers before the business interests of publishers.

We are a community of more than 103,000 authors and editors from 3,291 institutions spanning 160 countries, including Nobel Prize winners and some of the world’s most-cited researchers. Publishing on IntechOpen allows authors to earn citations and find new collaborators, meaning more people see your work not only from your own field of study, but from other related fields too.

Brief introduction to this section that descibes Open Access especially from an IntechOpen perspective

Want to get in touch? Contact our London head office or media team here

Our team is growing all the time, so we’re always on the lookout for smart people who want to help us reshape the world of scientific publishing.

Home > Books > Intelligent System and Computing

Parallel Processing for Range Assignment Problem in Wireless Sensor Networks

Submitted: 19 June 2019 Reviewed: 27 August 2019 Published: 25 November 2019

DOI: 10.5772/intechopen.89368

Cite this chapter

There are two ways to cite this chapter:

From the Edited Volume

Intelligent System and Computing

Edited by Yang (Cindy) Yi

To purchase hard copies of this book, please contact the representative in India: CBS Publishers & Distributors Pvt. Ltd. www.cbspd.com | [email protected]

Chapter metrics overview

698 Chapter Downloads

Impact of this chapter

Total Chapter Downloads on intechopen.com

Total Chapter Views on intechopen.com

Wireless sensor network is a collection of autonomous devices called sensor nodes which sense the environmental factors such as temperature, pressure, humidity, moisture, etc. The nodes sense the data, process it and transmit to the other nodes within their transmission range through radio propagation. Energy minimization in wireless sensor networks is a significant problem since the nodes are powered by a small battery of limited capacity. In case of networks with several thousand nodes, the simulation of algorithms can be very slow. The parallel computing model provides significantly faster simulation time for larger networks. Parallel processing involves executing the program instructions by dividing them among multiple processors with the objective of reducing the running time. So, we propose algorithms for the range assignment problem in wireless sensor networks using the parallel processing techniques. We also discuss the complexity of the proposed algorithms and significance of the parallel processing techniques in detail. The proposed techniques will be useful for implementing the distributed algorithms in WSNs.

• range assignment
• parallel processing
• minimum spanning tree
• wireless sensor networks

Author Information

M. prasanna lakshmi *.

• Indian Institute of Information Technology, Sri City, India

D. Pushparaj Shetty

• National Institute of Technology Karnataka, India

*Address all correspondence to: [email protected]

1. Introduction

In this section, preliminaries of Wireless Sensor Networks (WSNs) and parallel processing are discussed in detail.

1.1 Wireless sensor networks

Wireless Sensor Network (WSN) is a group of spatially dispersed autonomous devices called sensor nodes equipped with a radio transceiver along with an antenna. The devices are responsible for sending and receiving radio signals. Transmission range is assigned to the nodes to facilitate the communication between the nodes of a network. The sensor nodes sense the physical conditions of the environment such as temperature, pressure, sound, heat, light and humidity, etc., at various locations, process the data and transmit to the other nodes that lie within their transmission range through radio propagation. WSN monitors a physical system in real world and has applications in several fields such as environmental monitoring, biological detection, military and health care, etc. [ 1 ]. Because of the power constraints for the nodes using batteries with limited capacity, minimization of energy consumption is a significant problem in WSNs [ 2 ].

Constructing an efficient topology by assigning transmission range to the nodes of a network to minimize the total energy consumption has become a major challenge in WSNs. In general, the transmission range assigned to a node can be tuned so that the required connectivity constraint for the resultant network is satisfied and the total energy is minimized; this class of problems is categorized as topology control problems [ 3 ]. Some of the specified constraints include simple connectivity, bi-connectivity, k -connectivity, etc. [ 4 ]. By using an appropriate topology, the energy utilization of the network can be minimized which results in an increased lifetime of a WSN.

Transmission range of a node is the range within which the data sent by other node is received properly [ 5 ]. Two nodes in a WSN can communicate if and only if one node is in the transmission range of the other. Transmission range of a node u with the range r in three different dimensions is shown in the Figure 1 . In general, the communication is multi hop in nature, and a node transmits the data to the destination node in its range using the relay nodes. In order to minimize the energy consumption, it is desirable to use short edges rather than the long energy-inefficient edges.

Radio coverage in different dimensional networks.

Let P s be the range of source node u to transmit the signal to the destination node v . Then a signal transmitted by the source node u is attenuated by a factor: P r ∝ P s dist u v α , where dist u v is the Euclidean distance between u and v , and α is the distance range gradient or path loss coefficient that depends on various environmental factors and generally lies between 2 and 6 [ 6 ]. In this chapter, the terms range and power are used interchangeably.

In reality, some problems use mathematical models that describe the problem in a systematic way and enable us to solve the problem efficiently. Graphs can be used to model many relations and represent many physical problems in the real world. A WSN is modeled as an undirected graph to solve the energy minimization problems. In this model, a vertex of the undirected graph represents a node and the edge joining two vertices represents the communication link between the nodes. The nodes are deployed on a Euclidean plane and each pair of two nodes is associated to the Euclidean distance between the nodes. Each node is located by its x and y coordinates and the distance function is used to find the Euclidean distance between any two nodes x and y , and is denoted by w xy which is given by w xy = x 1 − x 2 2 + y 1 − y 2 2 .

Figure 2 illustrates the graph theoretic modeling of a WSN with four sensor nodes v 1 , v 2 , v 3 , and v 4 . In this, Figure 2(a) shows a network of four nodes with their respective transmission ranges and its asymmetric and symmetric versions are shown in Figure 2(b) and (c) , respectively [ 7 ]. There is an edge between two vertices in symmetric graph if and only if it is bidirectional. A network is said to be bidirectional if and only if each edge is bidirectional and there exists a bidirectional path between every pair of two nodes of the network. Since the signal transmitted by a sensor node must be acknowledged by the receiver node, the bidirectional links are given preference.

Illustration of graph theoretic modeling.

Throughout this chapter, the considered topology is bidirectional. Therefore, we use an undirected graph along with the weight function w to represent a WSN. Once a WSN is formulated as an undirected graph G = V E w , the transmission range R v assigned to each vertex v ∈ G is the maximum of all its adjacent edge weights and is mathematically given as follows:

The total range of the graph which is the sum of the ranges of all the vertices of G is given by R G = Σ i = 1 n R v i . Figure 3 is presented to illustrate the range assignment of a WSN. In this, Figure 3(a) shows a spanning tree of 11 vertices along with weights assigned to the edges and Figure 3(b) shows the range values assigned to the vertices as the maximum of all its adjacent edge weights in the spanning tree, as given in Eq. (1) .

Illustration of range assignment.

Minimum range assignment problem in a WSN is to assign transmission range to the nodes of the network such that the resultant subgraph H satisfies the specified constraints and the total range of the network, i.e., R H is minimized [ 8 ]. Let H be a spanning subgraph of the given graph G = V E w , R H v be the range assigned to vertex v ∈ V H as given in Eq. (1) and R H be total range of the subgraph H . For various problems considered in this chapter, our interest is to find a spanning tree with minimum range.

Chen et al. [ 9 ] studied the problem of strong connectivity in multi hop packet radio networks and proposed a 2-approximation algorithm which initially considers an undirected Minimum Spanning Tree (MST) and later establishes the bidirectional connectivity. Strong Minimum Energy Topology problem (SMET) in a WSN is studied by Cheng et al. [ 10 ], in which the objective is to assign transmission range to the nodes of the network such that the total range of the network is minimized and the reduced topology is connected. The authors have proved that the SMET problem is NP-complete and proposed two algorithms namely: Minimum Spanning Tree (MST) based Heuristic which is of 2-approximation ratio and an Incremental Power Greedy Heuristic and performed the simulation to show that the Incremental Power Greedy Heuristic performs better than the MST Heuristic. Formulation of the SMET problem is as follows:

Problem : Strong Minimum Energy Topology problem (SMET).

Instance : A complete graph G = V E w , where w : V × V → R + is a weight function.

Question : A range assignment such that the induced subgraph H is connected and the and the total range of H , i.e., R H is minimized.

1.2 Parallel processing

Large scale WSNs such as environmental monitoring systems produce large amount of data in the order of Peta bytes. The challenges in this case are storage and computation as the sensors are constrained by their resources which are scarcely available [ 11 ]. If the large amount of data is processed centrally, all data needs to be transmitted to a central server using multi hop transmissions which leads to high computational cost. One of the best ways to avoid such problem is to exploit the advantages of the distributed storage and parallel processing. Instead of transmitting data to a central server, data is stored and processed in network which reduces the computational cost. In this process, the computational task is decomposed into many small tasks, and the computation is executed in parallel by the distributed sensors.

Sullivan et al. [ 12 ] proposed a set of new parallel algorithms for a tree decomposition-based approach to solve the maximum weighted independent set problem. Independent set problem for a given graph is to find a subset of vertices with maximum cardinality such that no two vertices in the graph are adjacent to each other. Maximum Weighted independent set problem in which, the vertices are assigned weights, is to find an independent set with maximum weight [ 13 ]. Zhu et al. [ 14 ] proposed parallel algorithm for the hierarchical-based protocol for WSNs based on the Low-Energy Adaptive Clustering Hierarchy (LEACH) algorithm in order to improve the routing efficiency of the networks. Authors have implemented the algorithms using the parallel processing technique and showed that this technique has increased the overall performance. Lounis et al. [ 15 ] presented a new model for parallel computing of energy consumption in WSNs, and implemented on GPU architecture. Through simulation, authors showed that the proposed model provides simulation times significantly faster than that of the sequential model for large networks and for long simulations.

Andoni et al. [ 16 ] gave algorithms for geometric graph problems in the modern parallel models. The authors found a 1 + ϵ approximation algorithm for a Geometric Minimum Spanning tree (MST) problem. In geometric MST, set of n points are plotted on a low dimension space such as R d and other bounded metric spaces, in which weights of the edges are the distances between their endpoints. Authors also gave a general algorithmic framework that also applies to Earth-Mover Distance and the transportation cost problem. Katsigiannis et al. [ 17 ] presented a Helper Threading scheme for parallelizing the Kruskal’s algorithm [ 18 ] which is used for finding a Minimum Spanning Forest (MSF). The implementation employs one main thread, which executes the serial algorithm, and several helper threads, that run in parallel and reduce the work of the main thread.

In this chapter, we discuss the parallel processing techniques for the range assignment problem for simple connectivity. We propose algorithms for this problem using parallel processing techniques and determine the complexity. The proposed algorithms initially find an MST and assign range to each vertex of the network based on its range in the Euclidean MST. We find the Euclidean MST using well known algorithms: Prim’s and Kruskal’s and later we assign the range using parallel processing technique for both the cases. We also discuss the complexity of the proposed algorithms in detail for both the algorithms.

Simulation is an act of imitating operation of real world process or system over time [ 19 ]. The simulation is performed on a model which represents the system. It is known that simulations closely reflect accurate behavior of the system. Simulations help in evaluating the algorithm before investing on the physical hardware.

2. Related work

Finding a Euclidean MST is an important problem in Graph Theory and there are several algorithms in the literature [ 20 ]. MST problems have significant applications in computer and communication network design, as well as indirect applications in fields such as computer vision and cluster analysis [ 21 ]. Parallelization of Prim’s algorithm is studied by Deo and Yoo [ 22 ] and the proposed algorithms used shared memory computers. Gonina et al. [ 23 ] studied the parallel implementation of the Prims’s algorithm for finding the MST of dense graphs. Authors presented the simulation results which demonstrate the advantage of proposed algorithms.

Vladimir et al. [ 24 ] studied serial variants of Prim’s and Kruskal’s algorithm and presented their parallelization, targeting message passing parallel machine with distributed memory. Authors have considered large graphs and presented experimental results which show that Prim’s algorithm is a good choice for dense graphs while Kruskal’s algorithm is better for sparse graphs. Authors have proposed algorithms based on the sequential algorithms of Prim and Kruskal, targeting message passing parallel machine with distributed memory. The proposed algorithm which uses the Prim’s algorithm has a running time of O n 2 k + O n log k and the one which uses the Kruskal’s algorithm has a running time of O n 2 k + O n 2 log k where n is the number of vertices and k is the number of partitioned subsets of V such that each subset has n k consecutive vertices and their edges. In this section, we discuss the parallel processing algorithms for computing Euclidean MST using both Prim’s and Kruskal’s algorithms separately. In both the algorithms, each processor gets a subset of vertices from the given set of vertices to process.

The considered input for the parallelization of both Prim’s and Kruskal’s algorithm by Vladimir et al. [ 24 ] is an undirected simple graph with weights assigned to the edges. For our research the input considered is a complete graph along with edge weights, where the edge weights are the Euclidean distance between the nodes.

2.1 Parallelization of Prim’s algorithm by Loncar et al.

Prim’s algorithm starts from an arbitrary vertex and then grows the subtree by choosing a new vertex from the set of unvisited vertices and adding it to the subtree in each iteration. The Prim’s algorithm runs until the number of edges becomes n − 1 or all the vertices are added to the subtree. The complexity of the Prim’s algorithm is O n 2 where n is the number of vertices of the given graph. In this algorithm, the input considered is an undirected graph with n vertices and m edges along with the edge weights in which weight of edge uv is denoted by w uv [ 24 ].

The weights are represented using the adjacency matrix which is defined as follows:

Prim’s algorithm is implemented using the auxiliary array d of length n which stores the weights from each vertex to the MST. The lightest weight edge is chosen from d and is added to MST in each iteration and the array d is updated accordingly. The main loop of the Prim’s algorithm cannot be parallelized since the minimum edge weights incident to MST change in each iteration. So, only two steps are parallelized: finding a minimum weight edge that connects a new vertex not in MST to a vertex in MST and updating the array d . The complexity of the proposed algorithm is O n 2 k + O n log k where n is the number of vertices and k is the number of processors.

2.2 Parallelization of Kruskal’s algorithm by Loncar et al.

Kruskal’s algorithm finds a minimum weighted edge which connects two components in the forest in each iteration, i.e., it grows multiple trees in parallel. Initially, Kruskal’s algorithm creates a forest considering each vertex as a tree and next it sorts all the edges. Each time a minimum weighted edge is chosen and added to the forest if it connects two different trees else it is discarded. This process is repeated until the forest becomes a spanning tree. The complexity of the proposed algorithm is O m log n where m is the number of edges and n is the number of vertices [ 24 ].

Similar to the Prim’s algorithm, we have adjacency matrix which stores the weights between the vertices, and each processor is assigned a subset of vertices. In parallelization of Kruskal’s algorithm, each processor sorts the edges of its vertices according to their weights. At each process, a local MST is found using Kruskal’s algorithm and finally, all the local MST’s are merged. The complexity of the proposed algorithm is O n 2 k + O n 2 log k where n is the number of vertices and k is the number of processors.

3. Parallelization of range assignment problem

In this section, we present the proposed algorithms for range assignment problem using parallel processing techniques. The proposed algorithms adopt the algorithms for parallelization of both Prim’s and Kruskal’s algorithms by Loncar et al. [ 24 ]. In this environment, the nodes are deployed on a Euclidean plane and each pair is associated with the Euclidean distances between those nodes. Since a WSN is modeled as an undirected graph along with a weight function, the input for these algorithms is a complete graph G = V E w where the weight function is as explained in Section 1. The range assigned to a vertex v is denoted by R v .

Objective of this problem is to find a spanning tree such that the total range of the spanning tree is minimized. In the proposed algorithms, we initially find the spanning tree of the given complete graph and assign the range to the vertices based on their range in the Euclidean MST using parallel processing. We propose two algorithms: one using the Prim’s algorithm and the other using the Kruskal’s algorithm. We also compute the complexity of the proposed algorithm in both the cases. The list of notations used in this chapter is given in Table 1 .

List of notations.

3.1 Range assignment using Prim’s algorithm

Let G = V E w be the given complete graph. In this algorithm initially, we find a spanning tree by parallelizing the Prim’s algorithm and range is assigned to the vertices based on their range in the MST by using parallel processing. The formulation of the problem is as follows:

Problem: Parallel Algorithm for Range assignment using Prim’s algorithm (PARA-Prim’s).

Input: A complete graph G = V E w , where w is a weight function and P the set of processors.

Objective: To find a spanning tree such that the total energy is minimized, using parallel processing.

In the proposed algorithm, we consider a complete graph and the number of processors as input and compute a spanning tree which minimizes the total range. In this algorithm, we partition the vertices into k groups and each processor gets n k consecutive vertices and their edges. Each processor also contains auxiliary array d of the vertices which maintains the distances of the vertices to the MST. Let V i and d i be the set of vertices and the auxiliary array of the processor p i , respectively.

Each process finds a minimum weighted edge which connects the MST with vertices of the set V i and sends to the leader processor using all-to-one reduction. The leader processor selects one with the minimum weight among all the received edges, adds it to MST and broadcasts to all the processors. Processors mark the vertices connected to MST and update their auxiliary array d and this process is repeated until all the vertices are added to the subtree.

Next, we assign range to the vertices in the following way: for a vertex, each process finds the farthest vertex to it in the MST and sends the distance between them to the leader processor using all-to-one reduction. Later, leader processor selects one with maximum edge weight among all the received edge weights and that weight is assigned as range to the vertex v . This process of range assignment is repeated for all the vertices. The sequence of steps is presented in Algorithm 1.

Theorem 1.1 [ 24 ] The parallelization of Prim’s algorithm takes O n 2 k + O n log k running time where n is the number of nodes and k is the number of processors.

Theorem 1.2 The algorithm PARA-Prim’s takes O n 2 k + O n log k running time, where n is the number of nodes and k is the number of processors.

Proof: From Theorem 1.1, it is clear that finding the MST by parallelizing the Prim’s algorithm takes O n 2 k + O n log k running time for n number of nodes and k number of processors. In PARA-Prim’s algorithm the range assignment is done based on the MST obtained by parallelizing the Prim’s algorithm. For each vertex, we find the farthest vertex in each processor which takes the running time of O n k and for all such vertices it takes a running time of O n 2 k . Next each processor sends the farthest vertex to the leader process and leader processor finds the global farthest vertex which takes a running time of O n k and for all such n vertices it takes a running time of O n 2 k . So the running time of PARA-Prim’s algorithm is O n 2 k + O n log k .

3.2 Range assignment using Kruskal’s algorithm

Similar to the Prim’s algorithm in this algorithm, we have k number of processors assigned with n k set of consecutive vertices. Each processor sorts the edges of its vertices and finds a local MST using the Kruskal’s algorithm. Finally all the local MSTs are merged in the following way: first processor sends its set of edges of the local MST to the second processor and forms a new local MST by using the set of edges from both the processors. Now, the first process remains no longer and terminates, and this process of merging continues until single process remains. Range assignment is done to the vertices in parallel way similar to the PARA-Prim’s algorithm as explained in the previous subsection. The formulation of the problem is as follows:

Problem: Parallel Algorithm for Range assignment using Kruskal’s algorithm (PARA-Kruskal’s).

The sequence of steps for the above explained procedure is presented in Algorithm 2 named PARA-Kruskal’s.

Theorem 1.3 [ 24 ] The parallelization of Kruskal’s algorithm takes O n 2 k + O n 2 log k where n is the number of vertices and k is the number of processors.

Theorem 1.4 The algorithm PARA-Kruskal’s takes O n 2 k + O n 2 log k running time, where n is the number of nodes and k is the number of processors.

Proof: From Theorem 1.3, it is clear that, the running time of the parallelization of Kruskal’s algorithm is O n 2 k + O n 2 log k . Next, we do the range assignment to the vertices based on its range in the MST formed by parallelizing the Kruskal’s algorithm. From Theorem 1.3, it is clear that the running time of the range assignment for all the vertices is O n 2 k . So, the running time of the PARA-Kruskal’s algorithm is O n 2 k + O n 2 log k .

4. Comparison with the state of arts

Solving the range assignment problem by computing Euclidean MST using Prim’s algorithm and Kruskal’s algorithm takes running time of O n 2 and O n 2 log n , respectively. For WSNs with large number of sensor nodes, this complexity is quite high which can be improved by using parallel processing techniques. Simulation can be performed on hardware that supports multiple cores in order to realize the improvements over serial programming environments. The complexities of the range assignment problem using Prim’s algorithm and Kruskal’s algorithm by employing parallel processing techniques are O n 2 k + O n log k and O n 2 k + O n 2 log k , respectively. So, theoretically there is a significant improvement in the complexity of the range assignment problem by applying parallel processing techniques. Simulation can be performed to study the stability of the proposed algorithms and to compare the proposed algorithms with the existing algorithms for the range assignment algorithms.

5. Conclusions

In this research, we have studied the range assignment problem by employing parallel processing techniques of both Prim’s and Kruskal’s algorithms. The complexity of the proposed two algorithms is discussed in detail and it is shown that complexity can be improved by using parallel processing techniques for larger networks. It is an interesting problem to study variations of range assignment problems using parallel processing techniques. The implementation of the proposed algorithms can be realized using CUDA programming which supports programming GPU with multiple cores.

Abbreviations

• 1. Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. Wireless sensor networks: A survey. Computer Networks. 2002; 38 (4):393-422
• 2. Clementi, AE, Penna P, Silvestri R. The power range assignment problem in radio networks on the plane. In: Annual Symposium on Theoretical Aspects of Computer Science. Berlin, Heidelberg: Springer; February 2000. pp. 651-660
• 3. Lloyd EL, Liu R, Marathe MV, Ramanathan R, Ravi SS. Algorithmic aspects of topology control problems for ad hoc networks. Mobile Networks and Applications. 2005; 10 (1–2):19-34
• 4. West DB. Introduction to Graph Theory. Vol. 2. Upper Saddle River, NJ: Prentice hall; 1996
• 5. Santi P. Topology control in wireless ad hoc and sensor networks. ACM Computing Surveys (CSUR). 2005; 37 (2):164-194
• 6. Carmi P, Chaitman-Yerushalmi L. On the minimum cost range assignment problem. In: International Symposium on Algorithms and Computation. Berlin, Heidelberg: Springer; 2015. pp. 95-105
• 7. Calinescu G, Wan PJ. Range assignment for high connectivity in wireless ad hoc networks. In: International Conference on Ad-Hoc Networks and Wireless. Berlin, Heidelberg: Springer; 2003. pp. 235-246
• 8. Fuchs B. On the hardness of range assignment problems. Networks: An International Journal. 2008; 52 (4):183-195
• 9. Chen WT, Huang NF. The strongly connecting problem on multihop packet radio networks. IEEE Transactions on Communications. 1989; 37 (3):293-295
• 10. Cheng X, Narahari B, Simha R, Cheng MX, Liu D. Strong minimum energy topology in wireless sensor networks: NP-completeness and heuristics. IEEE Transactions on Mobile Computing. 2003; 2 (3):248-256
• 11. Wang Y, Wang Y. Distributed storage and parallel processing in large-scale wireless sensor networks. In: High Performance Computing Workshop. Cetraro, Italy: IOS Press; 2010. pp. 288-305
• 12. Sullivan BD, Weerapurage D, GroÃńr C. Parallel algorithms for graph optimization using tree decompositions. In: 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum. IEEE; 2013. pp. 1838-1847
• 13. Minty GJ. On maximal independent sets of vertices in claw-free graphs. Journal of Combinatorial Theory, Series B. 1980; 28 (3):284-304
• 14. Zhu Y, Yao Q, George G, Wu S, Zhang C. Parallel LEACH algorithm for wireless sensor networks. In: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA). The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp); 2012. p. 1
• 15. Lounis M, Bounceur A, Laga A, Pottier B. GPU-based parallel computing of energy consumption in wireless sensor networks. In: 2015 European Conference on Networks and Communications (EuCNC). IEEE; 2015, June. pp. 290-295
• 16. Andoni A, Nikolov A, Onak K, Yaroslavtsev G. Parallel algorithms for geometric graph problems. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing. ACM; 2014. pp. 574-583
• 17. Katsigiannis A, Anastopoulos N, Nikas K, Koziris N. An approach to parallelize Kruskal’s algorithm using helper threads. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum. IEEE; 2012. pp. 1601-1610
• 18. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. Cambridge, Massachusetts, London, England: McGraw-Hill Book Company; 2009
• 19. Sobeih A, Hou JC, Kung LC, Li N, Zhang H, Chen WP, et al. J-Sim: A simulation and emulation environment for wireless sensor networks. IEEE Wireless Communications. 2006; 13 (4):104-119
• 20. Rosen KH. Handbook of Discrete and Combinatorial Mathematics. Boca Raton, London, New York, Washington, DC: CRC Press; 2017
• 21. Graham RL, Hell P. On the history of the minimum spanning tree problem. Annals of the History of Computing. 1985; 7 (1):43-57
• 22. Deo N, Yoo YB. Parallel Algorithms for the Minimun Spanning Tree Problem. Computer Science Department: Washington State University; 1981
• 23. Gonina E, KalÃl’ LV. Parallel PrimâĂŹs Algorithm on Dense Graphs with a Novel Extension. 2007
• 24. LonÄŅar V, Åăkrbic S. Parallel implementation of minimum spanning tree algorithms using MPI. In: 2012 IEEE 13th International Symposium on Computational Intelligence and Informatics (CINTI). IEEE; 2012. pp. 35-38

© 2019 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Continue reading from the same book

Published: 29 April 2020

By Na-Young Ahn and Dong Hoon Lee

839 downloads

By Kian Hamedani, Zhou Zhou, Kangjun Bai and Lingjia ...

1031 downloads

By Kaung Htet Myint

773 downloads

We've detected unusual activity from your computer network

To continue, please click the box below to let us know you're not a robot.

Why did this happen?

Please make sure your browser supports JavaScript and cookies and that you are not blocking them from loading. For more information you can review our Terms of Service and Cookie Policy .

For inquiries related to this message please contact our support team and provide the reference ID below.

Data-Driven Traffic Assignment: A Novel Approach for Learning Traffic Flow Patterns Using Graph Convolutional Neural Network

• Published: 24 July 2023
• Volume 5 , article number  11 , ( 2023 )

Cite this article

• Rezaur Rahman 1 &
• Samiul Hasan 1  

434 Accesses

3 Citations

Explore all metrics

We present a novel data-driven approach of learning traffic flow patterns of a transportation network given that many instances of origin to destination (OD) travel demand and link flows of the network are available. Instead of estimating traffic flow patterns assuming certain user behavior (e.g., user equilibrium or system optimal), here we explore the idea of learning those flow patterns directly from the data. To implement this idea, we have formulated the traditional traffic assignment problem (from the field of transportation science) as a data-driven learning problem and developed a neural network-based framework known as Graph Convolutional Neural Network (GCNN) to solve it. The proposed framework represents the transportation network and OD demand in an efficient way and utilizes the diffusion process of multiple OD demands from nodes to links. We validate the solutions of the model against analytical solutions generated from running static user equilibrium-based traffic assignments over Sioux Falls and East Massachusetts networks. The validation results show that the implemented GCNN model can learn the flow patterns very well with less than 2% mean absolute difference between the actual and estimated link flows for both networks under varying congested conditions. When the training of the model is complete, it can instantly determine the traffic flows of a large-scale network. Hence, this approach can overcome the challenges of deploying traffic assignment models over large-scale networks and open new directions of research in data-driven network modeling.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Modeling Urban Traffic Data Through Graph-Based Neural Networks

Predicting Taxi Hotspots in Dynamic Conditions Using Graph Neural Network

MTGCN: A Multitask Deep Learning Model for Traffic Flow Prediction

Data availability.

The data that support the findings of this study are available from the corresponding author, [[email protected]], upon reasonable request.

Abdelfatah AS, Mahmassani HS (2002) A simulation-based signal optimization algorithm within a dynamic traffic assignment framework 428–433. https://doi.org/10.1109/itsc.2001.948695

Alexander L, Jiang S, Murga M, González MC (2015) Origin-destination trips by purpose and time of day inferred from mobile phone data. Transp Res Part C Emerg Technol 58:240–250. https://doi.org/10.1016/j.trc.2015.02.018

Article   Google Scholar  

Atwood J, Towsley D (2015) Diffusion-convolutional neural networks. Adv Neural Inf Process Syst. https://doi.org/10.5555/3157096.3157320

Ban XJ, Liu HX, Ferris MC, Ran B (2008) A link-node complementarity model and solution algorithm for dynamic user equilibria with exact flow propagations. Transp Res Part B Methodol 42:823–842. https://doi.org/10.1016/j.trb.2008.01.006

Bar-Gera H (2002) Origin-based algorithm for the traffic assignment problem. Transp Sci 36:398–417. https://doi.org/10.1287/trsc.36.4.398.549

Article   MATH   Google Scholar  

Barthélemy J, Carletti T (2017) A dynamic behavioural traffic assignment model with strategic agents. Transp Res Part C Emerg Technol 85:23–46. https://doi.org/10.1016/j.trc.2017.09.004

Ben-Akiva ME, Gao S, Wei Z, Wen Y (2012) A dynamic traffic assignment model for highly congested urban networks. Transp Res Part C Emerg Technol 24:62–82. https://doi.org/10.1016/j.trc.2012.02.006

Billings D, Jiann-Shiou Y (2006) Application of the ARIMA Models to Urban Roadway Travel Time Prediction-A Case Study. Systems, Man and Cybernetics, 2006. SMC’06. IEEE International Conference on 2529–2534

Boyles S, Ukkusuri SV, Waller ST, Kockelman KM (2006) A comparison of static and dynamic traffic assignment under tolls: a study of the dallas-fort worth network. 85th Annual Meeting of 14

Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25:163–177. https://doi.org/10.1080/0022250X.2001.9990249

Cai P, Wang Y, Lu G, Chen P, Ding C, Sun J (2016) A spatiotemporal correlative k-nearest neighbor model for short-term traffic multistep forecasting. Transp Res Part C Emerg Technol 62:21–34. https://doi.org/10.1016/j.trc.2015.11.002

Chien SI-J, Kuchipudi CM (2003) Dynamic travel time prediction with real-time and historic data. J Transp Eng 129:608–616. https://doi.org/10.1061/(ASCE)0733-947X(2003)129:6(608)

Cui Z, Henrickson K, Ke R, Wang Y (2018a) Traffic graph convolutional recurrent neural network: a deep learning framework for network-scale traffic learning and forecasting. IEEE Trans Intell Transp Syst. https://doi.org/10.1109/TITS.2019.2950416

Cui Z, Ke R, Pu Z, Wang Y (2018b) Deep bidirectional and unidirectional LSTM recurrent neural network for network-wide traffic speed prediction. International Workshop on Urban Computing (UrbComp) 2017

Cui Z, Lin L, Pu Z, Wang Y (2020) Graph Markov network for traffic forecasting with missing data. Transp Res Part C Emerg Technol 117:102671. https://doi.org/10.1016/j.trc.2020.102671

Defferrard M, Bresson X, Vandergheynst P (2016) Convolutional neural networks on graphs with fast localized spectral filtering. Adv Neural Inf Process Syst 3844–3852

Deshpande M, Bajaj PR (2016) Performance analysis of support vector machine for traffic flow prediction. 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC) 126–129. https://doi.org/10.1109/ICGTSPICC.2016.7955283

Elhenawy M, Chen H, Rakha HA (2014) Dynamic travel time prediction using data clustering and genetic programming. Transp Res Part C Emerg Technol 42:82–98. https://doi.org/10.1016/j.trc.2014.02.016

Foytik P, Jordan C, Robinson RM (2017) Exploring simulation based dynamic traffic assignment with large scale microscopic traffic simulation model

Friesz TL, Luque J, Tobin RL, Wie BW (1989) Dynamic network traffic assignment considered as a continuous time optimal control problem. Oper Res 37:893–901. https://doi.org/10.2307/171471

Article   MathSciNet   MATH   Google Scholar  

Gundlegård D, Rydergren C, Breyer N, Rajna B (2016) Travel demand estimation and network assignment based on cellular network data. Comput Commun 95:29–42. https://doi.org/10.1016/j.comcom.2016.04.015

Guo S, Lin Y, Feng N, Song C, Wan H (2019) Attention based spatial-temporal graph convolutional networks for traffic flow forecasting. Proceed AAAI Conf Artif Intell 33:922–929. https://doi.org/10.1609/aaai.v33i01.3301922

Guo K, Hu Y, Qian Z, Sun Y, Gao J, Yin B (2020) Dynamic graph convolution network for traffic forecasting based on latent network of Laplace matrix estimation. IEEE Trans Intell Transp Syst 23:1009–1018. https://doi.org/10.1109/tits.2020.3019497

Guo K, Hu Y, Qian Z, Liu H, Zhang K, Sun Y, Gao J, Yin B (2021) Optimized graph convolution recurrent neural network for traffic prediction. IEEE Trans Intell Transp Syst 22:1138–1149. https://doi.org/10.1109/TITS.2019.2963722

Hammond DK, Vandergheynst P, Gribonval R (2011) Wavelets on graphs via spectral graph theory. Appl Comput Harmon Anal 30:129–150. https://doi.org/10.1016/j.acha.2010.04.005

He X, Guo X, Liu HX (2010) A link-based day-to-day traffic assignment model. Transp Res Part B 44:597–608. https://doi.org/10.1016/j.trb.2009.10.001

Huang Y, Kockelman KM (2019) Electric vehicle charging station locations: elastic demand, station congestion, and network equilibrium. Transp Res D Transp Environ. https://doi.org/10.1016/j.trd.2019.11.008

Innamaa S (2005) Short-term prediction of travel time using neural networks on an interurban highway. Transportation (amst) 32:649–669. https://doi.org/10.1007/s11116-005-0219-y

Jafari E, Pandey V, Boyles SD (2017) A decomposition approach to the static traffic assignment problem. Transp Res Part b Methodol 105:270–296. https://doi.org/10.1016/j.trb.2017.09.011

Janson BN (1989) Dynamic traffic assignment for urban road networks. Transp Res Part B Methodol 25:143–161

Ji X, Shao C, Wang B (2016) Stochastic dynamic traffic assignment model under emergent incidents. Procedia Eng 137:620–629. https://doi.org/10.1016/j.proeng.2016.01.299

Jiang Y, Wong SC, Ho HW, Zhang P, Liu R, Sumalee A (2011) A dynamic traffic assignment model for a continuum transportation system. Transp Res Part b Methodol 45:343–363. https://doi.org/10.1016/j.trb.2010.07.003

Kim H, Oh JS, Jayakrishnan R (2009) Effects of user equilibrium assumptions on network traffic pattern. KSCE J Civ Eng 13:117–127. https://doi.org/10.1007/s12205-009-0117-5

Kim TS, Lee WK, Sohn SY (2019) Graph convolutional network approach applied to predict hourly bike-sharing demands considering spatial, temporal, and global effects. PLoS ONE 14:e0220782. https://doi.org/10.1371/journal.pone.0220782

Kipf TN, Welling M (2016) Semi-supervised classification with graph convolutional networks. 5th International Conference on Learning Representations, ICLR 2017- Conference Track Proceedings

LeBlanc LJ, Morlok EK, Pierskalla WP (1975) An efficient approach to solving the road network equilibrium traffic assignment problem. Transp Res 9:309–318. https://doi.org/10.1016/0041-1647(75)90030-1

Lee YLY (2009) Freeway travel time forecast using artifical neural networks with cluster method. 2009 12th International Conference on Information Fusion 1331–1338

Leon-Garcia A, Tizghadam A (2009) A graph theoretical approach to traffic engineering and network control problem. 21st International Teletraffic Congress, ITC 21: Traffic and Performance Issues in Networks of the Future-Final Programme

Leurent F, Chandakas E, Poulhès A (2011) User and service equilibrium in a structural model of traffic assignment to a transit network. Procedia Soc Behav Sci 20:495–505. https://doi.org/10.1016/j.sbspro.2011.08.056

Li Y, Yu R, Shahabi C, Liu Y (2018) Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. 6th International Conference on Learning Representations, ICLR 2018-Conference Track Proceedings 1–16

Li G, Knoop VL, van Lint H (2021) Multistep traffic forecasting by dynamic graph convolution: interpretations of real-time spatial correlations. Transp Res Part C Emerg Technol 128:103185. https://doi.org/10.1016/j.trc.2021.103185

Lin L, He Z, Peeta S (2018) Predicting station-level hourly demand in a large-scale bike-sharing network: a graph convolutional neural network approach. Transp Res Part C 97:258–276. https://doi.org/10.1016/j.trc.2018.10.011

Liu HX, Ban X, Ran B, Mirchandani P (2007) Analytical dynamic traffic assignment model with probabilistic travel times and perceptions. Transp Res Record 1783:125–133. https://doi.org/10.3141/1783-16

Liu Y, Zheng H, Feng X, Chen Z (2017) Short-term traffic flow prediction with Conv-LSTM. 2017 9th International Conference on Wireless Communications and Signal Processing, WCSP 2017-Proceedings. https://doi.org/10.1109/WCSP.2017.8171119

Lo HK, Szeto WY (2002) A cell-based variational inequality formulation of the dynamic user optimal assignment problem. Transp Res Part b Methodol 36:421–443. https://doi.org/10.1016/S0191-2615(01)00011-X

Luo X, Li D, Yang Y, Zhang S (2019) Spatiotemporal traffic flow prediction with KNN and LSTM. J Adv Transp. https://doi.org/10.1155/2019/4145353

Ma X, Tao Z, Wang Y, Yu H, Wang Y (2015) Long short-term memory neural network for traffic speed prediction using remote microwave sensor data. Transp Res Part C Emerg Technol 54:187–197. https://doi.org/10.1016/j.trc.2015.03.014

Ma X, Dai Z, He Z, Ma J, Wang Y, Wang Y (2017) Learning traffic as images: a deep convolutional neural network for large-scale transportation network speed prediction. Sensors 17:818. https://doi.org/10.3390/s17040818

Mahmassani HaniS (2001) Dynamic network traffic assignment and simulation methodology for advanced system management applications. Netw Spat Econ 1:267–292. https://doi.org/10.1023/A:1012831808926

Merchant DK, Nemhauser GL (1978) A model and an algorithm for the dynamic traffic assignment problems. Transp Sci 12:183–199. https://doi.org/10.1287/trsc.12.3.183

Mitradjieva M, Lindberg PO (2013) The stiff is moving—conjugate direction Frank-Wolfe methods with applications to traffic assignment * . Transp Sci 47:280–293. https://doi.org/10.1287/trsc.1120.0409

Myung J, Kim D-K, Kho S-Y, Park C-H (2011) Travel time prediction using k nearest neighbor method with combined data from vehicle detector system and automatic toll collection system. Transp Res Record 2256:51–59. https://doi.org/10.3141/2256-07

Nie YM, Zhang HM (2010) Solving the dynamic user optimal assignment problem considering queue spillback. Netw Spat Econ 10:49–71. https://doi.org/10.1007/s11067-007-9022-y

Peeta S, Mahmassani HS (1995) System optimal and user equilibrium time-dependent traffic assignment in congested networks. Ann Oper Res. https://doi.org/10.1007/BF02031941

Peeta S, Ziliaskopoulos AK (2001) Foundations of dynamic traffic assignment: the past, the present and the future. Netw Spat Econ 1:233–265

Peng H, Wang H, Du B, Bhuiyan MZA, Ma H, Liu J, Wang L, Yang Z, Du L, Wang S, Yu PS (2020) Spatial temporal incidence dynamic graph neural networks for traffic flow forecasting. Inf Sci (n y) 521:277–290. https://doi.org/10.1016/j.ins.2020.01.043

Peng H, Du B, Liu M, Liu M, Ji S, Wang S, Zhang X, He L (2021) Dynamic graph convolutional network for long-term traffic flow prediction with reinforcement learning. Inf Sci (n y) 578:401–416. https://doi.org/10.1016/j.ins.2021.07.007

Article   MathSciNet   Google Scholar  

Polson NG, Sokolov VO (2017) Deep learning for short-term traffic flow prediction. Transp Res Part C Emerg Technol 79:1–17. https://doi.org/10.1016/j.trc.2017.02.024

Primer A (2011) Dynamic traffic assignment. Transportation Network Modeling Committee 1–39. https://doi.org/10.1016/j.trd.2016.06.003

PyTorch [WWW document], 2016. URL https://pytorch.org/ . Accessed 10 Jun 2020

Rahman R, Hasan S (2018). Short-term traffic speed prediction for freeways during hurricane evacuation: a deep learning approach 1291–1296. https://doi.org/10.1109/ITSC.2018.8569443

Ran BIN, Boyce DE, Leblanc LJ (1993) A new class of instantaneous dynamic user-optimal traffic assignment models. Oper Res 41:192–202

Sanchez-Gonzalez A, Godwin J, Pfaff T, Ying R, Leskovec J, Battaglia PW (2020) Learning to simulate complex physics with graph networks. 37th International Conference on Machine Learning, ICML 2020 PartF16814, 8428–8437

Shafiei S, Gu Z, Saberi M (2018) Calibration and validation of a simulation-based dynamic traffic assignment model for a large-scale congested network. Simul Model Pract Theory 86:169–186. https://doi.org/10.1016/j.simpat.2018.04.006

Sheffi Y (1985) Urban transportation networks. Prentice-Hall Inc., Englewood Cliffs. https://doi.org/10.1016/0191-2607(86)90023-3

Book   Google Scholar  

Tang C, Sun J, Sun Y, Peng M, Gan N (2020) A General traffic flow prediction approach based on spatial-temporal graph attention. IEEE Access 8:153731–153741. https://doi.org/10.1109/ACCESS.2020.3018452

Teng SH (2016) Scalable algorithms for data and network analysis. Found Trends Theor Comput Sci 12:1–274. https://doi.org/10.1561/0400000051

Tizghadam A, Leon-garcia A (2007) A robust routing plan to optimize throughput in core networks 117–128

Transportation Networks for Research Core Team (2016) Transportation Networks for Research [WWW Document]. 2016. URL https://github.com/bstabler/TransportationNetworks (Accessed 8 Jul 2018)

Ukkusuri SV, Han L, Doan K (2012) Dynamic user equilibrium with a path based cell transmission model for general traffic networks. Transp Res Part b Methodol 46:1657–1684. https://doi.org/10.1016/j.trb.2012.07.010

Waller ST, Fajardo D, Duell M, Dixit V (2013) Linear programming formulation for strategic dynamic traffic assignment. Netw Spat Econ 13:427–443. https://doi.org/10.1007/s11067-013-9187-5

Wang HW, Peng ZR, Wang D, Meng Y, Wu T, Sun W, Lu QC (2020) Evaluation and prediction of transportation resilience under extreme weather events: a diffusion graph convolutional approach. Transp Res Part C Emerg Technol 115:102619. https://doi.org/10.1016/j.trc.2020.102619

Wardrop J (1952) Some theoretical aspects of road traffic research. Proc Inst Civil Eng Part II 1:325–378. https://doi.org/10.1680/ipeds.1952.11362

Watling D, Hazelton ML (2003) The dynamics and equilibria of day-to-day assignment models. Netw Spat Econ. https://doi.org/10.1023/A:1025398302560

Wu CH, Ho JM, Lee DT (2004) Travel-time prediction with support vector regression. IEEE Trans Intell Transp Syst 5:276–281. https://doi.org/10.1109/TITS.2004.837813

Yasdi R (1999) Prediction of road traffic using a neural network approach. Neural Comput Appl 8:135–142. https://doi.org/10.1007/s005210050015

Yu B, Song X, Guan F, Yang Z, Yao B (2016) k-nearest neighbor model for multiple-time-step prediction of short-term traffic condition. J Transp Eng 142:4016018. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000816

Yu B, Yin H, Zhu Z (2018) Spatio-temporal graph convolutional networks: a deep learning framework for traffic forecasting, in: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, California pp. 3634–3640. https://doi.org/10.24963/ijcai.2018/505

Zhang Y, Haghani A (2015) A gradient boosting method to improve travel time prediction. Transp Res Part C Emerg Technol 58:308–324. https://doi.org/10.1016/j.trc.2015.02.019

Zhang S, Tong H, Xu J, Maciejewski R (2019) Graph convolutional networks: a comprehensive review. Comput Soc Netw. https://doi.org/10.1186/s40649-019-0069-y

Zhao L, Song Y, Zhang C, Liu Y, Wang P, Lin T, Deng M, Li H (2020) T-GCN: a temporal graph convolutional network for traffic prediction. IEEE Trans Intell Transp Syst 21:3848–3858. https://doi.org/10.1109/TITS.2019.2935152

Zhou J, Cui G, Zhang Z, Yang C, Liu Z, Wang L, Li C, Sun M (2020) Graph neural networks: a review of methods and applications. AI Open.  https://doi.org/10.1016/j.aiopen.2021.01.001

Download references

This study was supported by the U.S. National Science Foundation through the grant CMMI #1917019. However, the authors are solely responsible for the facts and accuracy of the information presented in the paper.

Author information

Authors and affiliations.

Department of Civil, Environmental, and Construction Engineering, University of Central Florida, Orlando, FL, USA

Rezaur Rahman & Samiul Hasan

You can also search for this author in PubMed   Google Scholar

Contributions

The authors confirm their contribution to the paper as follows: study conception and design: RR, SH; analysis and interpretation of results: RR, SH; draft manuscript preparation: RR, SH. All authors reviewed the results and approved the final version of the manuscript.

Corresponding author

Correspondence to Rezaur Rahman .

Ethics declarations

Conflict of interest.

The authors declare that they have no conflict of interest.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A: modeling traffic flows using spectral graph convolution

In spectral graph convolution, a spectral convolutional filter is used to learn traffic flow patterns inside a transportation network in response to travel demand variations. The spectral filter is derived from spectrum of the Laplacian matrix, which consists of eigenvalues of the Laplacian matrix. So to construct the spectrum, we must calculate the eigenvalues of` the Laplacian matrix. For a symmetric graph, we can compute the eigenvalues using Eigen decomposition of the Laplacian matrix. In this problem, we consider the transportation network as a symmetric-directed graph, same number of links getting out and getting inside a node, which means the in-degree and out-degree matrices of the graph are similar. Thus, the Laplacian matrix of this graph is diagonalizable as follows using Eigen decomposition

where \(\boldsymbol{\Lambda }\) is a diagonal matrix with eigenvalues, \({\lambda }_{0},{\lambda }_{1},{\lambda }_{2}, . . . ,{\lambda }_{N}\) and \({\varvec{U}}\) indicates the eigen vectors, \({u}_{0},{u}_{1},{u}_{2}, . . . ,{u}_{N}\) . Eigen values represent characteristics of transportation network in terms of strength of a particular node based on its position, distance between adjacent nodes, and dimension of the network. The spectral graph convolution filter can be defined as follows:

where \(\theta\) is the parameter for the convolution filter shared by all the nodes of the network and \(K\) is the size of the convolution filter. Now the spectral graph convolution over the graph signal ( \({\varvec{X}})\) is defined as follows:

According to spectral graph theory, the shortest path distance i.e., minimum number of links connecting nodes \(i\) and \(j\) is longer than \(K\) , such that \({L}^{K}\left(i, j\right) = 0\) (Hammond et al. 2011 ). Consequently, for a given pair of origin ( \(i\) ) and destination ( \(j)\) nodes, a spectral graph filter of size K has access to all the nodes on the shortest path of the graph. It means that the spectral graph convolution filter of size \(K\) captures flow propagation through each node on the shortest path. So the spectral graph convolution operation can model the interdependency between a link and its \(i\) th order adjacent nodes on the shortest paths, given that 0 ≤  i  ≤  K .

The computational complexity of calculating \({{\varvec{L}}}_{{\varvec{w}}}^{{\varvec{k}}}\) is high due to K times multiplication of \({L}_{w}\) . A way to overcome this challenge is to approximate the spectral filter \({g}_{\theta }\) with Chebyshev polynomials up to ( \(K-1\) )th order (Hammond et al. 2011 ). Defferrard et al. (Defferrard et al. 2016 ) applied this approach to build a K -localized ChebNet, where the convolution is defined as

in which \(\overline{{\varvec{L}} }=2{{\varvec{L}}}_{{\varvec{s}}{\varvec{y}}{\varvec{m}}}/{{\varvec{\uplambda}}}_{{\varvec{m}}{\varvec{a}}{\varvec{x}}}-{\varvec{I}}\) . \(\overline{{\varvec{L}} }\) represents a scaling of graph Laplacian that maps the eigenvalues from [0, \({\uplambda }_{max}\) ] to [-1,1]. \({{\varvec{L}}}_{{\varvec{s}}{\varvec{y}}{\varvec{m}}}\) is defined as symmetric normalization of the Laplacian matrix \({{{\varvec{D}}}_{{\varvec{w}}}}^{-1/2}{{\varvec{L}}}_{{\varvec{w}}}{{\boldsymbol{ }{\varvec{D}}}_{{\varvec{w}}}}^{-1/2}.\) \({T}_{k}\) and θ denote the Chebyshev polynomials and Chebyshev coefficients. The Chebyshev polynomials are defined recursively by \({T}_{k}\left(\overline{{\varvec{L}} }\right)=2x{T}_{k-1}\left(\overline{{\varvec{L}} }\right)-{T}_{k-2}\left(\overline{{\varvec{L}} }\right)\) with \({T}_{0}\left(\overline{{\varvec{L}} }\right)=1\) and \({T}_{1}\left(\overline{{\varvec{L}} }\right)=\overline{{\varvec{L}} }\) . These are the basis of Chebyshev polynomials. Kipf and Welling (Kipf and Welling 2016 ) simplified this model by approximating the largest eigenvalue \({\lambda }_{max}\) of \(\overline{L }\) as 2. In this way, the convolution becomes

where Chebyshev coefficient, \(\theta ={\theta }_{0}=-{\theta }_{1}\) , All the details about the assumptions and their implications of Chebyshev polynomial can be found in (Hammond et al. 2011 ). Now the simplified graph convolution can be written as follows:

Since \({\varvec{I}}+{{{\varvec{D}}}_{{\varvec{w}}}}^{-1/2}{{\varvec{A}}}_{{\varvec{w}}}{{\boldsymbol{ }{\varvec{D}}}_{{\varvec{w}}}}^{-1/2}\) has eigenvalues in the range [0, 2], it may lead to exploding or vanishing gradients when used in a deep neural network model. To alleviate this problem, Kipf et al. (Kipf and Welling 2016 ) use a renormalization trick by replacing the term \({\varvec{I}}+{{{\varvec{D}}}_{{\varvec{w}}}}^{-1/2}{{\varvec{A}}}_{{\varvec{w}}}{{\boldsymbol{ }{\varvec{D}}}_{{\varvec{w}}}}^{-1/2}\) with \({{\overline{{\varvec{D}}} }_{{\varvec{w}}}\boldsymbol{ }\boldsymbol{ }}^{-1/2}{\overline{{\varvec{A}}} }_{{\varvec{w}}}{{\boldsymbol{ }\overline{{\varvec{D}}} }_{{\varvec{w}}}}^{-1/2}\) , with \({\overline{{\varvec{A}}} }_{{\varvec{w}}}={{\varvec{A}}}_{{\varvec{w}}}+{\varvec{I}}\) , similar to adding a self-loop. Now, we can simplify the spectral graph convolution as follows:

where \({\varvec{\Theta}}\in {{\varvec{R}}}^{{\varvec{N}}\times {\varvec{N}}}\) indicates the parameters of the convolution filter to be learnt during training process. From Eq. 21 , we can observe that spectral graph convolution is a special case of diffusion convolution (Li et al. 2018 ), but the only difference is that in spectral convolution, we symmetrically normalized the adjacency matrix.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Rahman, R., Hasan, S. Data-Driven Traffic Assignment: A Novel Approach for Learning Traffic Flow Patterns Using Graph Convolutional Neural Network. Data Sci. Transp. 5 , 11 (2023). https://doi.org/10.1007/s42421-023-00073-y

Download citation

Received : 21 May 2023

Revised : 09 June 2023

Accepted : 13 June 2023

Published : 24 July 2023

DOI : https://doi.org/10.1007/s42421-023-00073-y

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Traffic assignment problem
• Data-driven method
• Deep learning
• Graph convolutional neural network
• Find a journal
• Publish with us
• Track your research

• Skip to main content
• Keyboard shortcuts for audio player

NBC fired Ronna McDaniel. But TV news has a bigger pundit problem

David Folkenflik

Former RNC Chairwoman Ronna McDaniel, shown at last November's Republican presidential primary debate on NBC. The network hired her and then fired her in the course of a week after a newsroom revolt. Joe Raedle/Getty Images hide caption

Former RNC Chairwoman Ronna McDaniel, shown at last November's Republican presidential primary debate on NBC. The network hired her and then fired her in the course of a week after a newsroom revolt.

Thanks to a newsroom revolt, Republican National Committee chair Ronna McDaniel's tenure at NBC News didn't even last a full Scaramucci .

Critics have seized on the debacle to argue that the network doesn't know how to handle conservatives in the age of Donald Trump.

Open the aperture a bit more, and another question comes into focus: Why should American TV news networks pay leading politicians at all?

NBC's journalists and anchors objected not because she was a conservative, or even a Trump ally, but because she had played an active role in trying to overturn the results of the 2020 presidential race and had repeatedly and publicly trashed the press.

Former RNC Chair Ronna McDaniel dropped as an NBC contributor following outcry

Rupert Murdoch and new 'Washington Post' CEO accused of cover-up in hacking scandal

Still, McDaniel was - at least for a hot minute - just the latest among a string of political figures from both major political parties hired by television networks to join their news shows as commentators offering expertise.

As NBCUniversal News chief Cesar Conde put it in a memo Wednesday evening, the network is seeking "a widely diverse set of viewpoints and experience, particularly during these consequential times."

ABC, CBS, CNN...they all have paid pundits on air

In hiring McDaniel, NBC's Conde and his leadership team figured they were traveling a well-worn path with the reported $300,000 contract for McDaniel.

After all, ABC recently hired former RNC chair and Trump Chief of Staff Reince Priebus. CBS had hired former Trump White House Chief of Staff Mick Mulvaney . He is now on board at the fledgling network NewsNation.

And for years, CNN kept Donna Brazile on the payroll - even though she was the deputy chair of the Democratic National Committee at the time.

Tucker Carlson, the fired Fox News star, makes bid for relevance with Putin interview

Her case throws the tensions into stark relief. Brazile resigned from CNN in fall 2016 after it was revealed she had fed planned questions from a CNN town hall during that year's primaries to Hillary Clinton's top campaign aides. That was an obvious line crossed.

She was later hired by Fox and now is a paid pundit for ABC News.

Networks seek to lock in voices from both parties who are exclusive to their shows

The reasons propelling such hires are self-evident.

The networks - not just NBC - want to be able to rely on a stable of people to show up and be lively and informed on the air, often with little notice. They want to make sure they have voices reflecting an array of views from both parties. And they want exclusivity, which means they want to prevent the same high-profile figures from appearing on their competitors' shows.

The hiring of McDaniel made conventional sense under this rubric.

We do not live in conventional times.

Middle East crisis — explained

Newsroom at 'new york times' fractures over story on hamas attacks.

McDaniel had attacked crucial journalism norms - crossing bright lines in the eyes of many working journalism without finding her way back.

She frequently attacked the legitimacy of the press - and NBC, for that matter - in her rhetorical mimicry of then President Trump. In 2019, for example, she urged the dismissal of NBC's Richard Engel . Last spring, she called MSNBC's primetime hosts "propagandists."

Even more notably, McDaniel had participated with Trump, in her home state of Michigan, in pressuring local election officials not to certify Joe Biden's win in the absence of any evidence of meaningful irregularities in the vote. It took until this past Sunday's Meet the Press appearance for her to offer a grudging acknowledgment that Biden won.

And only at the same interivew did McDaniel reject the violence of the January 6 2021 siege of the U.S. Capitol.

Where do the loyalties of pundits lie?

That sequence set off NBC's chief political analyst, Chuck Todd, opening the door to a day of lambasting from the stars at its sister channel MSNBC –morning (Joe Scarborough and Mika Brzezinski), afternoon (Nicolle Wallace) and night (Joy Reid, Rachel Maddow and Lawrence O'Donnell).

The channel of course is still stocked with many paid partisan commentators, both with Democrat and Republican ties, all rigorously anti-Trump.

The fundamental question about the entire practice remains.

McDaniel said she felt she had to "kind of take one for the team" in failing to disagree publicly with Trump's promise to free people who were convicted of crimes related to January 6th. Which team does she represent now?

More broadly, to whom do the loyalties of these partisan figures lie? They should rest with the newsrooms that employ them and the viewers they serve. And yet the pundits often act as surrogates for the parties that made them. It's not clear they always believe what they're saying. And sometimes, they appear to be auditioning for future jobs.

Her reported $300,000 annual pay – not denied by the network – rankled a lot of the rank-and file-too. "So many talented reporters laid off this year," NBC News senior reporter Brandy Zadrozny tweeted on Sunday . "Workers who provided the content, won the awards, built the credibility of their shops, and worked for a yearly salary at a fraction of what big name contributors get in fancy contracts to fill pundit boxes on TV."

Cheaper to mint talking heads than hire reporting teams

And yet it is fundamentally cheaper to hire pundits than to send reporters, producers and videographers into the field to bring back reported stories.

It is certainly possible for political professionals to shift into a new phase of professional career. George Stephanopoulos left the Clinton White House, became a commentator for ABC News, and ultimately devoted himself to broadcast journalism full-time. So did former Nixon White House aide Diane Sawyer, first at CBS, then at ABC.

MSNBC made stars out of George W. Bush communications director Nicolle Wallace and Jen Psaki, the former press secretary for President Biden. Fox has done the same with Trump spokeswoman Kayleigh McEnaney. Wallace appears to be out of the political game. Are the others?

All this summons to mind what then Crossfire host Paul Begala – a former Bill Clinton aide – told me. He said CNN was paying him to be biased and said he approached it as a drunk person looks at a lamppost: providing more support than illumination.

In his memo to staffers Wednesday evening in which he announced he had reversed his decision to hire McDaniel, Conde said he heard the objections and would continue to seek ways to "redouble our efforts to seek voices that represent different parts of the political spectrum."

Many political figures would wither without public attention on TV. Those out of office feel the need to audition for potential voters, donors, employers, book publishers and the like.

There are more than 330 million Americans and thousands of political professionals. Why pay for the right to interview them? Does anyone think Newt Gingrich will boycott television appearances if he's not paid?

Part of the appeal of bringing McDaniel into the fold was to convey to Republicans, and particularly pro-Trump Republicans, that they are understood and their perspectives reflected on NBC's broadcasts.

McDaniel was a flawed vessel for that ambition, as she was not seen as loyal enough by Trump, who forced her out. By saying she had to "take one for the team," McDaniel also dispensed with her potential appeal to MAGA voters.

This whirlwind maneuver may leave NBC in a worse place than before.

Given the headlines, more Republicans may distrust NBC now than if its executives had not tried to bring McDaniel aboard at all.

Former CNN journalist Michael Socolow, now a media historian at the University of Maine, posted on X (formerly Twitter) last night about the internal debate that roiled CBS News after the election of President Richard Nixon and Vice President Spiro Agnew: What if they were right about the "silent majority" of Americans?

"So [CBS] sent Charles Kuralt 'On the Road' to find it in response," wrote Socolow, the son of Walter Cronkite's former executive producer on the CBS Evening News. "They didn't hire a Republican flack."

• Ronna McDaniel

• International edition
• Australia edition
• Europe edition

Network Rail to spend £2.8bn to cope with effects of climate crisis

Funding for drains, embankments and other measures is part £45.4bn five-year investment plan

• Business live – latest updates

Network Rail is to spend nearly £3bn to protect the railway from the effects of the climate crisis and extreme weather, as it warned that the country’s network was having to contend with hotter summers and more winter floods.

As part of its new £45.4bn five-year investment plan, the body in charge of Great Britain’s rail network will spend £2.8bn over the next five years on activities and technology to help it cope with the impact of climate change.

Network Rail said millions would be spent on looking after thousands of miles of drains, cuttings and embankments to make them more resilient to issues such as flooding or landslips .

The taxpayer-funded body plans to send key operational staff to its new “weather academy” to make them “amateur meteorologists”, allowing them to interpret forecasts and make better operational decisions.

The rail network has been battered by extreme weather recently, with more than 14 named storms in the past 12 months, which have led to widespread disruption for passengers.

The most high-profile delays took place over Christmas when severe weather and heavy flooding led to delays and cancellations, including on the Eurostar .

The new investment will also go into building or rebuilding more than 600,000 metres of drains and recruiting more than 400 extra drainage engineers, who will boost the amount of maintenance done of drains so they can handle heavier rainfall.

More than 20,000 cuttings and embankments have been targeted for repair work, with more than 300 miles being strengthened.

The investment marks a major increase from the £1bn that Network Rail had initially earmarked for spending on climate change during the five-year period to April 2029, and is nearly six times the £500m in the investment plan that ran from 2019 to 2024.

The £45bn set aside for the latest investment period, known as control period 7, will be an increase of £3bn on the previous period. However, at current prices and factoring in inflation, it equates to a real-terms cut to £42.8bn, down from £43bn in the previous period.

Martin Frobisher, Network Rail’s group safety and engineering director, told Today on BBC Radio 4: “Climate change is happening right now. It’s affecting the railway with flooding in winter and hotter summers than we’ve ever seen before.”

Andrew Haines, the Network Rail chief executive, said: “We can never completely weatherproof our railway but we can be better prepared and mitigate the worst that Mother Nature throws at us, now and into the future, to keep passengers and services safe and moving.”

Network Rail plans to spend £19.3bn on replacing old assets, as well as investing in other projects such as digital signalling.

after newsletter promotion

It will spend £12.6bn on maintenance, £5.3bn on support functions such as timetabling and IT, £4.4bn on operations such as signalling, and £1.8bn will be put in a “risk fund” to be used for unforeseen events.

About 70% of Network Rail’s funding comes from the taxpayer, with 25% coming from the rail operators to use the lines, and 5% from property income.

The majority of Network Rail’s income – nearly £30bn – will come via grants from the UK and Scottish governments. It will receive £13.8bn in track access charges from train operators and £1.7bn in commercial income, such as from retail and property.

Network Rail has set a number of targets to improve train performance and reduce track failures, including replacing and maintaining 5,000km of track and 3,000 sets of points – the part of the rail that moves, allowing trains to switch tracks.

It has also committed to £4bn of efficiencies in operations and maintenance over the five-year programme, including changing the way it manages external contracts and simplifying its technical standards.

• Network Rail
• Rail industry
• Rail transport
• Travel & leisure

More on this story

New train services between London and Scotland get go-ahead

Siemens to invest £100m in Chippenham rail factory site in Wiltshire

UK ministers look to install highly paid boss to spearhead rail reform plan

£140m rail plan to tackle Elizabeth line and Great Western problems

Draft rail reform bill published ‘fittingly late’, Labour says

Profits of UK’s private train-leasing firms treble in a year

LNER simpler fares trial adds more than £100 to some train journeys

‘Polar express’: passengers hit out at cold conditions on Scottish train line

Most viewed.