Analysis of the Braess paradox under various assignments from shipping units to carriers

Content

1. Introduction

2. Literature review

3. Model formulation
3.1 Notation
3.2 MIP-formulation

4. Numerical results
4.1 Description of the case
4.2 Data for the example
4.3 Results

5. Discussion

6. Conclusion and research outlook

References

Analysis of the Braess paradox under various assignments from shipping units to carriers

Weber, Marc-André / Koch, Florian

Abstract

The Braess paradox, introduced by D. Braess in 1968, describes the situation in which the total time spent in a system for at least two vehicles travelling from one node to another within a network of several nodes may increase if an additional path is added. This effect is due to non-cooperative behavior of the subjects involved and the fact that time consumption on the paths depends on their respective congestion. In this Game Theoretical paradox, full information is given to all vehicles about the theoretically shortest path for one vehicle, measured in time units, disregarding any congestion, which leads to a routing decision of individual rationality. This paper analyzes the Braess paradox if several shipping units have to be transported by multiple vehicles and load weight influences traffic congestion. A mixed integer linear programming formulation is used to model the problem. We introduce the model in detail, give numerical examples and analyze the results. A brief literature review on previous publications dealing with the Braess paradox is given as well.

Key words

Braess Paradox, Mixed Integer Linear Programming, Game Theory, Truck Assignment

1. Introduction

Traffic flows can be modeled using a network consisting of several nodes which are connected via arcs. From a single start node to a single sink node, one or more paths can provide the opportunity to travel from origin to destination via different available directed arcs. Braess stated that adding a path to a network may increase its optimal total traffic flow time. The idea behind this is that each vehicle, obtaining all information about the theoretical time required from a source node to a sink node, takes the path that looks most preferable to it, neglecting the decisions of other vehicle drivers and therefore neglecting any congestion influences. The resulting total time spent for all vehicles in the whole system need not be minimal as the duration of travelling on a specific path depends on the congestion on the arcs that are used by the vehicles and that are part of the respective path. Extensions of an existing network may cause a redistribution of flows that can result in longer individual running times [1], [2]. Therefore, the Braess paradox occurs in a graph if the traffic flow is not Pareto-optimal [3]. The linear mixed integer programming formulation (MIP) presented in this paper aims at minimizing the total latency occurring in the system, respectively the maximum time amongst all paths that connect start and sink nodes and that are used by at least one vehicle. We make the assumption that each vehicle takes an individual choice of its path, neglecting any path congestions that may arise due to the decisions of other vehicles. This can be modeled by forcing at least one vehicle to use the theoretically shortest path of all available paths, measured in time units. We use the original traffic network as provided in [1], but make an extension that shipping units have to be carried from origin to destination, which can be operated by several vehicles. However, the amount of load causes the vehicles to slow down speed based on a load-based latency function. Therefore it is analyzed how the assignment of shipping units to transportation carriers causes the Braess paradox and how the load-latency costs influence the time functions.

2. Literature review

The Braess effect found great interest in the literature since its discovery, not only for traffic networks, but also for engineering applications (see e. g. [4], [5]). A brief survey of the literature regarding the Braess paradox is given in the following. [6] introduced a non-linear programming formulation to determine an optimal subset from a set of proposed additional arcs for a network that will result in smaller total time needed for all vehicles. [7] introduced stochastic traffic assignments which may lead to the paradox effect. [8] gave a mathematical characterization for linear costs including an analysis of critical cost ranges. An investigation on changes in travel demand for several origin-destination pairs as well as changes in the network structure was conducted by [9]. [10] introduced a linear complementarity problem formulation to an enlarged network showing Braess effects. [11] analyzed the Braess paradox in stochastic loss networks. It was proven by [12] that the occurrence of the effect is highly dependent on the arc congestion function parameters and the demand of travel. A sensitivity analysis for the network equilibrium problem with elastic demand was provided by [13]. [14] studied a simulation of the Braess paradox with an iterative algorithm to determine the dynamic user equilibrium.

[15] provided research on dynamic flows in networks with one start and many destination nodes as well as for the reverse network. An algorithm capable to avoid the Braess effect based on artificial intelligence was presented by [16]. A non-linear programming formulation was given in [17]. Approximation methods for efficiently designing networks are studied in [18]. [19] studied optimal flow control problems of multiple-server (M/M/n) queuing systems, reporting that grouping together separated systems into a single one might degrade a system’s power. Experimental results on peoples’ behavior in route choosing were examined by [20] as well as [21]. [3] studied ways of finding optimal sub-networks within given networks and [22] gave upper and lower bounds on the worst-case severity of the paradox with respect to the maximum latency objective.

In the last two decades, the Braess paradox was also studied for data and communication networks (see e. g. [23], [24], [25] and [26]). Furthermore the effect was proven to occur in practical situations as in the streets of Stuttgart [27], [28] and New York [29] during road works. An overview of literature that is related to the Braess paradox can be found in [30].

This paper analyzes the assignment of shipping units to trucks under the assumption of load-dependent travel times per vehicle. The occurrence of the Braess paradox is studied using the original network provided by [1] with extensions to the latency functions per arc. We use a new Mixed Integer Programming formulation (MIP) to model the problem. To the best of the authors’ knowledge, there is on the one hand no such MIP formulation to this paradox and there is on the other hand no research on the respective assignment problem presented in the literature so far.

The proceeding of the paper is as follows: Section 3 introduces the MIP in detail. Section 4 describes the numerical tests, which results are discussed in Section 5. Finally, Section 6 gives a conclusion and a research outlook.

3. Model formulation

For the model formulation as described below, we assume the following: a network consisting of several nodes serves as the basis for representing the path structure. We refer to nodes as positions for starting or ending a route as well as for intersection points along the paths. Nodes may be connected via directed arcs, each with a linear flow-dependent congestion cost function. A predefined sequence of nodes is called a path. For an intended route from origin to destination, several paths can be chosen. Paths are allowed to be partly overlapping if some arcs belong to two or more paths.

It is known in advance how many vehicles are in the system and how much time it ideally takes them from the origin node to the destination node if no congestion due to other vehicles appears on the arcs. The effective time spent on one arc per vehicle is a linear function of the number of vehicles using that arc simultaneously, therefore a function of the arc’s congestion. The model aims at finding the lowest possible time amongst all paths that are used by at least one vehicle by assigning vehicles to specific arcs, assuming that the vehicles choose their paths individually based on rational behavior. This makes the model approach difficult as normally the MIP formulation finds a Pareto-optimal solution and is not taking into account the rational behavior of individuals which may result in a Nash-equilibrium. A modeling formulation therefore has to force at least one vehicle to use the theoretically shortest path.

To give the reader a fundamental understanding of our wording, we give the following example: Figure 1 describes the denotation for an exemplification of four nodes that are connected by five arcs resulting in three possible paths for a single route from node 1 to node 4. The figure shows the same layout as in the well-known example of the original Braess paradox presented in [1]:

illustration not visible in this excerpt

Figure 1: Denotation for nodes, arcs and paths

3.1 Notation

We use the following notation:

Indices

illustration not visible in this excerpt

Input parameters

illustration not visible in this excerpt

[...]