An extended coordinate descent method for distributed anticipatory network traffic control
Marco Rinaldi (corresponding author)
Research Assistant
KU Leuven
Leuven Mobility Research Centre
Celestijnenlaan 300, B-3001 Heverlee, Belgium
Phone: +32 (0)16 32 27 80
Chris M.J. Tampère, Ph.D.
Assistant Professor
KU Leuven
Leuven Mobility Research Centre
Celestijnenlaan 300, B-3001 Heverlee, Belgium
Abstract
Anticipatory optimal network control can be defined as the practice of determining the set of control actions that minimizes a network-wide objective function, so that the consequences of this action are taken in consideration not only locally, on the propagation of flows, but globally, taking into account the user’s routing behaviour. Such an objective function is, in general, defined and optimized in a centralized setting, as knowledge regarding the whole network is needed in order to correctly compute it.This is a strong theoretical framework but, in practice, reaching a level of centralization sufficient to achieve said optimality is very challenging. Furthermore, even if centralization was possible, it would exhibit several shortcomings, with concerns such as computational speed (centralized optimization of a huge control set with a highly nonlinear objective function), reliability and communication overhead arising.
The main aim of this work is to develop adecomposed heuristic descent algorithm that, demanding the different control entities to share the same information set, attains network-wide optimality through separate control actions.
Keywords:Anticipatory Network Traffic Control, Control Distribution, Distributed Optimization
1.Introduction
Road networks have been facing ever-increasing demand, a trend that pushed, in the last30 years, researchers worldwide in investing considerable efforts in the attempt of addressing the issues of network trafficcongestion.The characteristics of network supply pose a tight constraint on the maximum achievable level of service, but it is widely recognized that congestion and/or other traffic externalities can be reduced throughintelligent traffic controlstrategies,efficiently managing demand.
Traffic control applications originated as early as in the 1950s, their focus beingthat of determining locally optimal settings for single traffic light controlled intersections(Webster, 1958). Over the years, thanks to the increase in computational power, traffic control policies have evolved more and more towards coordination, recognizing the impactthat separated intersections in the network might have onto each other, and the importance of taking these effects into account(Wallace et al., 1984). The late 80s and 90s witnessed a new trend in which, additionally to coordination, also on-line responsiveness to traffic conditions gained importance, together with research and development now including traffic control policies tailored to motorways, rather than mainly focusing on urban intersections(Hunt et al., 1981)(Lowrie, 1990). Finally, in the last decade, coordinated control policies integrating both urban and motorway have been researched.
In the field of coordinated traffic control, a specific subset is that of anticipatory traffic control policies. These approaches follow from theoretical works developed in the 70s(Allsop, 1974), and the key contribution with respect to other control strategies is the fact that the road users’ reactions to changes in traffic control conditions are taken explicitly into account when determining the control law. This property yields considerable benefits to the traffic controller, as it can now place itself in the leading role of a Stackelberg interaction with the road users, allowing for greater efficiency.A major drawback of all coordinated approaches, anticipatory or not, is the fact that in order to achieve maximal performance the entire set of controllers on the network should be coordinated simultaneously.
Model-based coordinated traffic control policies are, indeed, of considerable computational complexity, due to the possibly very high dimensionality (number of controllers being simultaneously coordinated) and the ever-growing size of the underlying road network. This complexity becomes even steeper when considering the anticipatory control subset, where sensitivity information over the whole road network is necessary to correctly anticipate the users’ behaviour, no matter which and how many controllers are taken into account.
In order to tackle problems of increasing size and complexity,several decomposition, distribution and decentralization schemes have been developed for the coordinated traffic control problem in the last decade. These three words, which might sound very similar, warrant formal definitions, however in literature no widespread consensus is achieved on their meaning, and thus different works adopt different notions, e.g. (Katwijk, 2008)(Balaji and Srinivasan, 2010)
We therefore specify our chosen definitions for the three words, so to avoid misunderstanding:
-Decomposition schemes: frameworks that aim at subdividing a centralized, global problem into more tractable sub-problems, while still performing centralized computation and retaining globally valid dynamics of the original problem;
-Distribution schemes: frameworks that subdivide a centralized, global problem into simpler sub-problems, and solve them separately, employing, if necessary, some central mechanism to ensure that the global dynamics of the original problems are retained;
-Decentralization schemes: frameworks that subdivide a centralized, global problem into simpler sub-problems, and solve them fully separately. Unlike the distributed approaches, no explicit guarantee that the global dynamics of the original problem are retained, although they might emerge from the decentralized behaviour;
As we detail in the next section, so far while several researchers have been dealing with developing simplifications for the coordinated traffic control problem, little effort hasbeen done towards applying the same ideas to the anticipatory traffic control domain.
In this work, our main objective is indeed to fill this gap, and begin investigating if and how the anticipatory traffic control problem could be separated into simpler, smaller, eventually distributable problems. In order to do so, we develop a decomposition scheme, and study under which conditions this scheme is still able to retain globally valid dynamics and, therefore, yield the same level of optimality as a fully centralized anticipatory traffic control formulation.In order to ensure computational feasibility and ease of understanding, we perform this approach within the static time domain, although our focus for future research is that of extending these findings to the field of within-day dynamics.
The of this paper is organized as follows: in Section 2 we present an extensive literature review; in Section 3 we detail our methodology; Section 4 will feature the implementation we developed to test our algorithm, together with a simple proof of concept scenario to show its convergence properties. In Section 5 we present numerical tests of this algorithm on different size networks, ranging from simple examples towards bigger instances aiming to real-life, discussing the scalability of our approach and comparing it with general purpose optimization algorithms. Finally, in Section 6, we gather conclusions and give insights towards future research topics.
2.Literature Review
For the purposes of this work, we split the traffic control literature in two main categories, and focusmainly on reviewing the second: local traffic control strategies and coordinated traffic control strategies.
Local strategies, such as the Webster formula (Webster, 1958) for urban intersections or, considering motorway control, the ALINEA ramp metering strategy (Papageorgiou et al., 1991) are based on locally measured data (either for online or offline purposes) and disregard any interaction with other controllers deployed on the network.
Coordinated traffic control strategies, instead, take multiple controllers into account simultaneously, and try to obtain an optimal set ofsolutions for the resulting combined problem. Several coordinated strategies have been developed over the years, starting from fixed time area based strategies such as the MAXBAND (Little et al., 1981) and TRANSYT-7F (Wallace et al., 1984) control policies, and then evolving so to include responsiveness to online traffic states, such as in the SCATS (Lowrie, 1990), SCOOT (Hunt et al., 1981) and UTOPIA/SPOT (Mauro and Taranto, 1990) control policies.
Advances in the field of trafficmodeling enabled in the 80s and 90s the development of simple model based coordinated traffic control policies, such as the OPAC(Gartner, 1983), PRODYN(Henry et al., 1984) and RHODES(Sen and Head, 1997) systems.More recently, thanks to the latest improvements and developments yieldingmore detailed, faster and computationally more efficient traffic flow models, coordinated control strategies based on the Model Predictive Control (MPC) framework were researched in several works, such as (Hegyi et al., 2005), (Dotoli et al., 2006), (Van Den Berg et al., 2007) and (Aboudolas et al., 2009).
Anticipatory traffic control policies are a subset of the coordinated control policies,which not only employ a model to predict the future conditions of the network but also explicitly consider the user’s route choice reactions. These policies have received considerable attention from researchers especially in terms of analytical optimality and properties. Approaches as early as that of Allsop (1974) have been exploring the conditions of existence and uniqueness of solutions to this problem in the static domain. The impact of anticipatory control policies in static scenarios has been explored by several authors, dealingwith both road pricing (Yang and Bell, 1997)(Yan and Lam, 1996)and signalized intersection control (Smith and Ghali, 1990), (Cantarella et al., 1991), (Yang and Yagar, 1995).
In recent years, this concept has then been extended to the Dynamic Traffic Assignment (DTA) field byTaale, (2008) , Taale and Hoogendoorn(2012) and Taale and Hoogendoorn(2013). In their papers, the authors outlined this approach in a generic computational framework, through a bi-level formulation, discussing the implications of anticipatory control theory and its computational feasibility when expanding the problem to the time variant domain. More recently, (Ukkusuri et al., 2013) proposed an algorithmic model to solve the combined dynamic equilibrium based traffic signal control problem, which is expressed both as Nash-Cournot and Nash-Stackelberg games, based on an Iterative Assignment Optimization (IAO) procedure, and assessed the solutions’ quality in terms of optimality.
As we discuss in the introduction, all coordinated control strategies, anticipatory or not, share a common difficulty to be tackled, being the considerable complexity arising from the need to align several controllers simultaneously into one optimization problem. Moreover, in practice traffic controllers are separated, geographically and/or hierarchically, with local influence to only subsets of the whole network. Indeed, the effort necessary to develop an architecture whose centralization level would be sufficient to attain full global optimality is often impractical, with robustness, communication and computational complexity being only some of the problems such a centralized system would face.
In this respect, several decomposition and distribution schemes have been developed for the coordinated traffic control problem; some works have focused on subdividing the problem by reducing the size of the underlying network, subdividing it into more tractable subnetwork, such as in the approaches of (Papageorgiou and Mayr, 1982), (Gartner et al., 2001), (Mirchandani and Head, 2001), (Kotsialos and Papageorgiou, 2004), (Wongpiromsarn et al., 2012) and (Boillot et al., 2006).
Other authors have been focusing on reformulating the coordinated control problem in mathematical structures enabling the authors to exploit very fast and efficient optimization algorithms to determine the problem’s solution. Such works include, for example, the TUC control policy (Diakaki et al., 2002), the works of (Aboudolas et al., 2009), (Aboudolas et al., 2010), who employ a store-and-forward traffic flow model formulation to compute optimal green split and offsets in a network-wide scenario, exploiting the Rolling Horizon principle for online purposes and, finally,the approaches of(Lin et al., 2012),(Lin et al., 2011), and (Hajiahmadi et al., 2015) where a Model Predictive Control based problem is also redefined as a Mixed Integer Linear Programming problem, allowing for fast optimization.
Other authors have been decomposing the problem by exploiting computer scientific programming frameworks, such as agent-based modeling. Such papers include the store-and-forward model based approach of (de Oliveira and Camponogara, 2010) and the works of (Wang, 2005), (Katwijk, 2008), (Balaji and Srinivasan, 2010) and (Du et al., 2014).
In all of these coordinated traffic control decomposition strategies, though, no explicit modeling is included to take the users’ routing response into account, and therefore, while a few strategies can achieve, e.g. based on some area-aggregate measure, a redistribution of traffic and queues over the available capacity of the network, such as in the approaches of (Geroliminis et al., 2013) and (Haddad et al., 2013), no full-fledged anticipation is considered. A few studies dealt with decomposing User Equilibrium formulations, such as in the works of (Suwansirikul et al., 1987) and, more recently, the algorithms developed by (Dial, 2006), (Gentile et al., 2004) and (Bar-Gera, 2010); other focused, instead, on developing centralized algorithms to solve the road pricing problem efficiently (Dial, 1999), (Bar-Gera et al., 2013).
As a first step towards developing decomposition and, ultimately, distribution schemes for the anticipatory traffic control problem, in (Rinaldi et al., 2013) weemployed a Bi-Level formulation and an algorithmic solution, also based on the Model Predictive Control framework, and introduced a controller-wise decomposition scheme; while recognizing the importance of decomposing the problem within the time domain, through the Rolling Horizon technique, we wanted to explicitly consider the fact that controllers are, in real-life, pertaining to separate, distributed entities.
Following the empirical results we obtained in thatwork, in this paperwe explore the convergence properties of the controller-wise decomposition strategy in-depth, through simpler static scenarios, from a theoretical, analytic and algorithmic point of view; we once againexpresstheanticipatory control problem as a Bi-level optimization formulation, in which the upper level problem is that of selecting optimal control values for either traffic light controlled intersections or pricing on a subset of the network’s links, while the lower level problem isStatic, Deterministic User Equilibrium.
The main aim of this work is establishing the conditions under which anticipatory network-wide control would maintain global optimalitywhiledecomposed. Ourlong term objective is to obtain a solid methodology for real-life deployable anticipatory traffic control, determiningshortcomings(if any) in terms of optimalitywith respect to a fully centralized approach.
3.Methodology
This section outlines the methodology with which we tackle the problem of decomposing anticipatory optimal control. It is divided into subsections:we first dealwith how the information gathering process can be performed by separated entities, thanks to a sensitivity-wise objective function reformulation;we then detailthe decomposition of the optimization problem into different controlling unitsand how we obtain the necessary sensitivity approximations. Finally, we develop an optimization algorithm tailored to our problem and discuss its convergence properties and implications.
3.1Objective function reformulation
When dealing with anticipatory control, in order to determine the optimal control law we exploit the availability of some measures (be it traffic lights, pricing, ramp metering, variable speed limits, … ) to meet a network-wide goal, usually expressed in the form of an objective function. “Optimality” is to be understood in a broad sense; it could for example be related to emission levels, environmental constraints(Lin et al., 2014), more desirable distributions of traffic over the network’s hierarchy, etc.
In this paper we focus on maximizing the usage of the network’s capacity.This objective can be formulated, in a static setting, asthe minimization of the Total Cost function.
For ageneric network composed of a set of arcs and a set of nodes,this function is defined as follows:
(1)
where and are, respectively, the flow and cost functions for each link, and is the control inputs vector. Flow and cost functions are recursively dependentdue to the users’ equilibrium response.Following Wardrop’s 1st principle, this interdependency can be modeled through the following Variational Inequality (VI):
(2)
where is the set of all feasible link flows.
Under interior point existence assumptions (Verhoef, 2002), the anticipatory traffic control problem (1) can be formulated as the following optimization problem:
(3)
and its solution can be obtained by solving the following equation:
(4)
In order to solve the problem (3), one would need to determine the objective function’s gradient for all controllers. The necessarysensitivity information would need tobe collected from a fully centralized perspective though, while in this work our objective is that of assessing if and how the anticipatory control problem can be decomposed in a controller-wise fashion.
We therefore devise a scheme that allows us to separate the sensitivity retrieval process so that part of it can indeed be performed controller-wise, while a simple and independent monitoring system can be employed to estimate the remaining portion.
Following the sensitivity analysis algorithm proposed in(Yan and Lam, 1996), we apply a simple chain rule derivative formula to our problem, thus rewriting the1st order derivative of the original objective function (1), explicitly separating three different sensitivity terms:
(5)
where is the link flow vector, the Jacobian matrixis the sensitivity of equilibrium flows to the control actions and the gradientis the sensitivity of the objective function (in this case Total Cost, but this can be generalized to any cost function) to changes in the network flows. Finally, represents the sensitivity of link costs to control, having nonzero values only when a controllerhas direct influence on the link cost function, as, for example,in case of traffic light control.