A Global Constrained Optimization Method for Designing Road Networks with Small Diameters

1 Introduction

Nowadays, the urban traffic is becoming more and more congested with the traffic demand growing greatly. The congestion can be alleviated by designing more reasonable road networks. This designing is the so-called Network Design Problem (NDP). The Network Design Problem mainly focuses on making the optimal decision on the expansion of the road network in response to an increasing demand for travel [Yang and Bell, 1998]. Designing road network is often a hard task since various aspects have to be taken into account, such as:

∗This work is partially supported by the Chinese National Program on Key Basic Research Project (973 Program, grant no. 2013CB329301) and Natural Science Foundation of China (grants no. 61070044 and 61272265).

1) different objectives; 2) different stakeholders involved; 3) interdependencies between choice and investment; 4) short term versus long term; 5) long term uncertainties in demand; 6) short term uncertainties; and so on [Snelder, 2010].

Traditionally, we can divide the network design problem into two classes: the Discrete Network Design Problem (DNDP) and the Continuous Network Design Problem (CNDP). The difference between these two problems is the value area of decision variables. The decision variables of DNDP are either 0 or 1, while the decision variables of CNDP can change continuously in an interval. To be specific, the DNDP concerns about the additions of road segments to an existing transport network, and the CNDP mainly concerns about the improvements of road segments to an existing transport network. However, the Network Design Problem may be a mixed form, and its decision variables can be both discrete and continuous. This means that the road network designer should consider improving and adding the roads simultaneously rather than separately. This question can be named as the Mixed Network Design Problem (MNDP) [Yang and Bell, 1998]. In this paper, we focus on the general MNDP.

The designer needs to set up an objective in advance of designing the road network. There are several objective functions that have been used for this purpose. A lot of researchers assume that the travel demand between each origindestination pair on the network is given. However, the travel demand varies in the short term as a result of accidents, road work, bad weather conditions, events, seasonality, and so on. Meanwhile, the long term demand is uncertain. What's more, if we add capacity in the network, the travel times change, and hence the choices of the travelers change as well. The choices made by travelers contain: location choice, trip departure choice, destination choice, mode choice, departure time choice and route choice [Snelder, 2010]. In some cases, the uncertain demands and changeable travelers choices make it unimpressive and inappropriate to use a given demand from each origin to each destination to design road network.

In this paper, we propose the method that designs the road network in a macro perspective irrelevant to the pair-wise demands. To this end, the minimization of network travel time diameter, with respect to certain constrains, becomes our main objective for road network designing. We define the travel time diameter of the road network as below:

Definition 1.1 the travel time diameter D of a road network is defined as the maximum among all shortest travel time between any possible origin-destination pairs (O-D pairs).

In Definition (1.1), the diameter is defined with respect to the travel time, which is different to the common definition with respect to the hop number. Obviously, when the travel time diameter of the road network gets smaller, the connectivity, measured by time, of road network becomes closer, then the residents can travel in the network much more conveniently. Hence the smaller travel time diameter is a reasonable universal goal of road network design problem. However, it is difficult to solve this problem directly. In this paper, we convert the problem from minimizing the travel time diameter to maximizing the algebraic connectivity in spectral graph theory, which can be solved globally by semi-definite program.

The rest of this paper is presented as follows. We first briefly introduce several related works in the field of road network design in Section 2. In Section 3, the fundamentals of spectral graph theory relevant to our purpose are listed, then we prove the relationship between the travel time diameter and the algebraic connectivity of the network. We also describe a principled way to increase the algebraic connectivity. In Section 4, we propose the models to solve the road network design problem with respect to some scenarios. We present the experimental results of our models in Section 5 and conclude in Section 6.

2 RelatedWork

The road network design problem has been studied extensively in decades. Researchers have proposed many models on designing road network with several different objectives. [Antunes et al., 2003] designed a road network with maximal accessibility, where accessibility can be generically defined as the potential of opportunities for interaction between cities of regions [Hansen, 1959]; [Feng and Wu, 2003] used the equity to be the objective function to design road network, and covered equity of accessibility or travel cost for cities as well as the equity of budget allocation among the cities; [Snelder, 2010] focused on designing robust road network; In [Meng and Yang, 2002], they mainly considered about the benefit distribution and equity problem in designing road network.

Moreover, the prevailing objective function can be the total travel cost, which has been used by many articles. A general framework for this problem is bi-level: the upper-level is the investment decision-making behavior of the transport planners and designers; the lower-level represents the users' route choice behavior responding to the controls. However, this framework is a nonconvex programming problem, and most of the methods based on bi-level framework failed to find the global optimum. [Suwansirikul et al., 1987] proposed an alternative heuristic method called the equilibrium decomposed optimization algorithm to solve the problem. [Zhang et al., 2008] proposed a method based on the genetic algorithm. Unlike traditional methods, this algorithm can get a global solution to the problem. Recently, some methods reformulated the bi-level framework as a single level problem. [Li et al., 2012] transferred the network design problems into a sequence of single level concave programs, to which we can get the global solution.

3 Theoretical Justifications

3.1 Notations and Definitions

Each road in the network has a capacity, which may be determined by its speed limit, geometric design, number of lanes, number of traffic lights and other road characteristics. As the majority of roads are two-way and the road characteristics of two reverse direction street in a road are quite similar, we can model the road network by an undirected graph G = (V, E). We use the following notation to facilitate our discussion:

n = |V |: the number of the nodes in the graph.

m= |E|: the number of the edges in the graph.

we > 0: the weight on the eth edge e ∈ {1, 2, . . . ,m}. A weight can also be indexed by node pairs as the following.

wij ≥ 0: the weight on the edge between node i and node j where i, j ∈ {1, 2, ..., n} (if no edge connects node i and j, wij = 0).

te > 0: the travel time of the eth edge e ∈ {1, 2, . . . ,m}. vi: the ith node of the network.

The nodes in the graph represent the intersections of the road network, and the edges represent the road; The nonnegative weights represent the capacity of the roads, and a larger weight indicates a higher capacity. We hypothesize that the travel time on each road is proportional to the road length and the inverse of road capacity. Hence the travel time function is given by travel time = road length road capacity .

3.2 Fundamentals of Spectral Graph Theory

In this section, we review some fundamentals of spectral graph theory, which is the basis of our method. Spectral graph theory has a long history and a lot of articles concerning about it [Fiedler, 1973][Chung, 1997] [Boyd, 2006].

The Graph G can be described by its Laplacian matrix. The weighted Laplacian (matrix) is the n×n matrix L defined as:

We denote the eigenvalues of the Laplacian matrix L as:

The second smallest eigenvalue λ2 of the Laplacian matrix L is the algebraic connectivity, which can measure how wellconnected the graph is. The corresponding normalized eigenvector (w.r.t, λ2) is called the Fiedler vector f.

Next we list several basic properties of L as below:

1. λ1 = 0;
2. L is positive semidefinite;
3. 1 is the eigenvector corresponding to λ1, where 1 is the vector with all components be one;

3.3 An Intuitive Illustration on the Meaning of Algebraic Connectivity λ2

In order to illustrate the meaning of algebraic connectivity λ2, three toy road networks are shown in Table 1. R1 represents the original road network, where the weight of each edge represents the capacity of the road. R2 and R3 represent two different modified networks for R1. The length of each road is assumed to be one. The travel time diameter D and algebraic connectivity λ2 of each graph are shown in Table 1.

From Table 1, we can see that:

• By increasing the capacity of the bottleneck road between node C and D, R2's travel time diameter D drops from 3 to 2.5, meanwhile, its algebraic connectivity λ2 increases from 0.4384 to 0.6277
• R3 increases the capacity of the local road between node A and B. However, both the travel time diameter D and algebraic connectivity λ2 of R3 are unchanged.

As illuminated by the above examples, the algebraic connectivity λ2 is a measure of the whole connectivity of a graph. In the next section, we will theoretically justify this issue by developing the quantitative relationship between travel time diameter D and algebraic connectivity λ2.

3.4 The Quantitative Relationship between Travel Time Diameter and Algebraic Connectivity λ2

As defined in Definition (1.1), the travel time diameter of the road network is given by the maximum among all shortest travel time between any possible origin-destination pairs. We give two lemmas about the relationship between travel time diameter D and algebraic connectivity λ2:

Lemma 3.1 For a road network with travel time diameter D, and λ2 be the algebraic connectivity of its Laplacian matrix L, then

where wmin = min{w1, ..., wm}, tmin = min{t1, . . . , tm}.

Proof Let vmax denote the node with |f(vmax)| = maxi |f(vi)|, where f(vi) = fi.

So there exists a node u satisfying

Let P denote the shortest path in the road network joining u and vmax.

Since L is real symmetric, we can express the algebraic connectivity λ2 in terms of Rayleigh quotient [Horn and Johnson, 1985] of L:

where the 3rd inequality is obtained by Cauchy-Schwarz inequality [Dragomir, 2003]. Then the lemma follows.

Based on Lemma (3.1), we can see that a larger λ2 entails a smaller lower bound of D.

Lemma 3.2 For a road network with travel time diameter D, algebraic connectivity λ2, and k = wmax wmin = max{w1,...,wm} min{w1,...,wm} . Assume that the travel time diameter D consists of l edges, and the corresponding edge lengths are length1, length2, · · · , lengthl. The travel time of each edge is calculated by travel time = road length road capacity . Then we have:

where e = k · (length1 + length2 + · · · + lengthl).

Proof According to the Definition (1.1), the travel time diameter D can be expressed as this:

Then

Since L is real symmetric, we can present the algebraic connectivity λ2 in terms of Rayleigh quotient of L.

where e = k · (length1 + length2 + · · · + lengthl).

Based on Lemma (3.2), we can see that a larger λ2 implies a relatively smaller upper bound of D. With Lemma (3.1) and (3.2), we could conclude the relationship between the travel time diameter D and the algebraic connectivity λ2 as follows: an increment in λ2 often leads to a decreasing in both the upper bound and lower bound of travel time diameter D simultaneously; A large λ2 indicates a relatively tight bound on travel time diameter. Hence a larger algebraic connectivity λ2 indicates a better designed road network (i.e., with smaller travel time diameter). It turns out that we could convert our objective from the minimization of the travel time diameter to the maximization of the algebraic connectivity λ2, under certain constraints (e.g., limited budget).

3.5 Increasing the Algebraic Connectivity λ2

In this section, we describe how to increase the algebraic connectivity λ2. And we make some definitions first.

Definition 3.3 Assume G = (V,E) is an undirected graph with nonnegative weights. Then the augmentation operation for graph can be defined as an operation that increases a weight with ∆ > 0 or adds a new positive weighted edge on the graph.

Definition 3.4 Graph G′ is the augmented graph for G if G′ can be obtained by iteratively performing augmentation operations fromG.

Lemma 3.5 Assume G = (V, E) is an undirected graph with nonnegative weights. G′ is an augmented graph for G. And their Laplacian matrices are L′ and L respectively. Then

Proof Let G0 = G′ -G, and L0 be the Laplacian matrix of G0. By the definition of Laplacian matrix (Eq. (1)), we have the following equation: L′ = L+L0. Let X = {x|xT 1 = 0, |x| = 1}. Then the algebraic connectivity λ2 of the augmented graph G′ is:

Since λ2(L0) ≥ 0 always holds, we complete the proof.

Lemma 3.6 Let G = (V,E) be an undirected graph with nonnegative weights and L be the corresponding Laplacian matrix. The algebraic connectivity of G is λ2(L), and the corresponding Fiedler vector is f . And f(vi) denotes the ith element of f . Then we have the following two propositions:

1. If (f(vi)-f(vj))2 = 0, then an increment of wij admits an invariant λ2(L);
2. If (f(vi)-f(vj))2 > 0, then an increment of wij implies a strict increment of λ2(L).

Proof For an edge l connecting nodes vi and vj, we define the edge vector al ∈ Rn as ali = 1, alj = -1 and all other entries 0. Then L′ can be calculated as below:

where the ∆ij > 0 is the increment of the weight on edge l. The partial derivative of λ2(L′ ) with respect to ∆ij can be

expressed as below:∂

Based on Eq. (4), we have

Combining Eq. (5) and (6), we have

According to the monotonicity w.r.t. the first derivatives, we complete the proof.

Based on Lemma (3.5) and (3.6), we can get the relationship between the weight wij and the algebraic connectivity λ2 of the network. After augmenting a road network, we could guarantee its algebraic connectivity λ2 would not decrease (but it will not increase for sure). Moreover, we could optimize the algebraic connectivity λ2 by adjusting the weights selectively (e.g., increase the weights with nonzero partial derivatives). Note that Lemma (3.6) also admits a nice geometric interpreting: recall that the Fiedler vector can be considered as the geometric embedding of a graph. It turns out that the algebraic connectivity is insensitive to the weight changes between two points near to each other in the embedding. This observation meets the intuition that the short-cut paths can far significantly improve the global connectivity of road networks.

4 Designing the Road Network

In section 3.4, we have shown that the problem of minimization of travel time diameter could be converted to the maximization of the algebraic connectivity λ2 under certain constraints (e.g., limited budget). More specifically, we can add weights selectively to the road network according to Lemma 3.6 to maximize λ2. In this section, we propose several approaches that can decide which roads need to be upgraded and the corresponding increments of their capacities in the convex optimization framework. In practice, there are usually various constraints when designing a road network, e.g., the prohibition of the road capacity enhancement of certain road, the limitation of the total budget and so on. In this paper, without loss of generality, we adopt the budget constraints in our optimization problems. In order to assess the amount of costs for modifying the road network, we define the cost coefficient matrix C, where each element cij represents the per-unit cost to increase capacity on the corresponding road. In practice, it may be difficult to construct a new road, i.e., to give a weight increment to a zero-weight edge. This fact can be naturally modeled by assigning a large cost coefficient to a zero-weight edge. Note that various constraints, e.g., the prohibition of the road capacity enhancement of certain road, can also be formulated by this scheme.

Based on spectral graph theory, the road network design problem is to optimize the road network by selecting paths to improve or adding paths in the existing road network, i.e., maximize algebraic connectivity λ2 as well as minimize the modifying costs, under the budget constraint (less than B). In Section 4.1, this optimization problem is reformulated into several variants of semi-definite programming (SDP) problems with different objective functions.

4.1 Convex OptimizationMethod

Let the original road network be G, and the weight for each edge (vi, vj) be wij. Similarly, G′ is the designed road network and its corresponding weights are denoted as w′ij , i, j ∈ {1, . . . , n}. Also assume that the total budget is B, and cost coefficient matrix is C. Then the road network design problem to maximize the algebraic connectivity constrained by limited budget, can be defined as below:

where ⪰ denotes the matrix inequality, and ≥ or ≤ denotes the element-wise inequality. We denote the problemof Eq. (7) as OPTλ2 .

This problem can be reformulated to a semi-definite program(SDP). To see this, consider about this inequality:

The eigenvalues of the Laplacian Matrix L′ are:

And the eigenvector corresponding to λ1(L′ ) is 1. Note that the eigenvectors corresponding to all the other eigenvalues (λ2(L′ ) · · · λn(L′ )) are orthogonal to 1. It is easy to see that the eigenvalues of the matrix L′ + s · (11T /n) are:

Hence, Inequality (8) implies min{s, λ2(L′ )} ≥ s, which is equivalent to s ≤ λ2(L′ ). It turns out that the problem can be reformulated to the semi-definite program (SDP) as below:

Any standard SDP solver 1 could be used to solve the above SDP problem (Eq. (9)). Note that the optimized variables are the elements of L′ (e.g., all wi,j ′ ) and s.

1 In this paper, we adopt the 'SeDuMi' solver in CVX, which is an open-source toolbox for convex optimization.

However, in many cases, the road network design problem also needs considering the limitation of the budget, instead of only optimizing the algebraic connectivity in OPTλ2 . Therefore, we introduce another two variants of the road network design problems, which can also be formulated as SDP and hence solved globally by the SDP solvers.

Minimizing the budget: In some cases, we want to design the road network with the minimal budget under the constraint that λ2 is not less than some pre-determined threshold λ0. We denote this problem as OPTbudget. It can be formulated as below:

Eq. (10) can be reformulated to the semi-definite program (SDP) problem below:

Multi-objective optimization: In some cases, we would like to optimize the algebraic connectivity and budget simultaneously . More specifically, we incorporate the budget constraint into the objective function of OPTλ2 using a parameter α, so that the difference between the algebraic connectivity λ2 and expenditure for improvements is maximized. We denote this problem as OPTmulti:

It is usually necessary to solve the OPTmulti with several different values of α in order to obtain a satisfying solution.

And this question can be reformulated to the semi-definite program (SDP) problem below:

5 Experimental Results and Analysis

In this section, we investigate the effectiveness of all aforementioned models, namely OPTλ2 , OPTbudget and OPTmulti, on simulated datasets. We also systematically compare our method OPTλ2 with an existing method based on a genetic algorithm [Zhang et al., 2008] [Yin, 2000] in terms of travel cost, algebraic connectivity and travel time diameter of the designed road network in different travel demands settings.

Experimental setup: First, we randomly generate a small world network as the road network [Sienkiewicz and Holyst, 2005] by utilizing Watts-Strogatz mechanism [Watts and Strogat, 1998], which has 50 nodes and each node only connects to 4 nearby nodes. The capacity for each road is a random positive value, and the length of each road is set to one. Recall that the travel time function is defined as: travel time = road length road capacity . Without loss of generality, we set all roads' cost coefficient to one.

5.1 λ2 Maximization with Budget Constraint

In this case study, we compute the optimal solutions of λ2 for OPTλ2 (Eq. 7), where budget limitations varies from 2 to 100. The optimal travel time diameter and algebraic connectivity λ2 with respect to each budget limitation are shown in Fig. 1(a).

Fig. 1(a) shows that: with an increasing budget, the algebraic connectivity λ2 tends to gradually increase, while the travel time diameter of the road network would drop dramatically with relatively smaller budgets (less than 30) and then decrease steadily. This result confirms the relationship between travel time diameter and λ2 (Lemma 3.1 and 3.2).

5.2 Budget Minimization with λ2 Constraint

In this section, the OPTbudget model (Eq. 10) is tested on the simulated road network to determine the minimal budget constrained on a lower bound for λ2 (changing from the original λ2 (0.0336 in this case) to 5). The travel time diameter and budget of each optimal road network are shown in Fig. 1(b).

Fig. 1(b) shows that: as the lower bound of λ2 increases, the minimal budget for designing the road network would increase as well. However, the travel time diameter of the refined road network tends to decreases gradually. The OPTbudget model allow us to solve the global minimal budget under the constraint that λ2 is not less than a predetermined threshold.

5.3 Multi-objective Optimization

For the Multi-objective optimization model OPTmulti described in Eq. (12), we compute the optimal solutions with α varies from 0.02 to 0.035. The travel time diameter, λ2 and budget of the optimal road network w.r.t. each α are shown in Fig. 1(c).

This result shows that α allows us to make a tradeoff between the travel time diameter and budget in designing the road network, i.e., with a small α we relax the requirements of budget in return for gaining the quality of connectivity, and on the contrary, with a relatively large α the limited budget is emphasized instead of the connectivity of the road network.

5.4 Our Approach vs Genetic Algorithm

As mentioned in Section 1, unlike most existing road design models [Yang and Bell, 1998], our method does not rely on the existence of specific travel demands. In this experiment, we systematically compare our OPTλ2 with an existing method based on the genetic algorithm [Zhang et al., 2008] [Yin, 2000] in terms of travel cost, algebraic connectivity and travel time diameter of the designed road network on several demands. More specifically, we randomly generate four travel demand matrices, where each element represents the demand of traveling between the corresponding O-D pair. For each demand, we design the road network with the budget constraint varying from 2 to 100. The results are shown in the Fig. 2.

As shown Fig. 2(a)-2(d), in most cases, the travel time diameters obtained by genetic algorithm are much larger than those in our approach. Moreover, our method shows a consistent reduction in travel time diameters of the optimal road network along with an increasing budget, while the genetic algorithm has much more fluctuations. From the perspective of algebraic connectivity, Fig. 2(e)-2(h) also show that our approach achieves better λ2 than genetic algorithm with the same budget limit. In terms of travel cost, the magnified parts of Fig. 2(i)-2(l) show that: when the budget is relatively small (less than 15), genetic algorithm outperforms OPTλ2 with a smaller total travel cost. However, as the budget increases (larger than 20), our approach achieves slightly better performance than genetic algorithm. This observation implies that a global optimum can naturally meet most special travel demand if the cost constrain of global optimization is loose.

In summary, the genetic algorithm is to design a road network so as to fit certain demand, while our convex optimization method (OPTλ2 ) focus on optimizing the algebraic connectivity which is independent of any specific demand. And our convex optimization method is both efficient and universal in solving MNDP problems.

6 Conclusion

In practice, the smaller travel time diameter a road network has, the more efficient the road network will be. Inspired by this intuition, the minimization of network travel time diameter with respect to certain constraints is our main objective for designing a road network. However, it is difficult to solve this problem directly. In spectral graph theory, we theoretically prove that the diameter of the road network can be bounded by the algebraic connectivity, i.e., the upper and lower bounds of travel time diameter are proportional to the inverse of algebraic connectivity. Therefore, we could convert our objective from the minimization of the road network travel time diameter to the maximization of the algebraic connectivity under certain constraints. This reformulation leads to a semidefinite program, in which we can get its global solution easily. In the experimental part, we generate a small world network to represent the road network, and design it in several scenarios. The results confirm our theoretical justifications above. Finally, we empirically show that our method is an efficient and universal method to design road network by systematically comparing our method with an existing method based on the genetic algorithm.