Model and methods to address urban road network problems with disruptions

• Published date: 01 November 2020
• Date: 01 November 2020
• Author: Andréa Cynthia Santos,Yipeng Huang,Christophe Duhamel
• DOI: http://doi.org/10.1111/itor.12641

Intl. Trans. in Op. Res. 27 (2020) 2715–2739

DOI: 10.1111/itor.12641

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Model and methods to address urban road network problems

with disruptions

Yipeng Huanga, Andr´

ea Cynthia Santosa,∗and Christophe Duhamelb

aICD-LOSI, Universit´

e de Technologie de Troyes, Troyes, France

bUniversit´

e Clermont Auvergne, CNRS, LIMOS, F-63000 Clermont-Ferrand,France

E-mail: yipeng.huang@utt.fr [Huang]; andrea.duhamel@utt.fr [Santos]; christophe.duhamel@isima.fr [Duhamel]

Received 11 June2018; received in revised form 29 January 2019; accepted 29 January 2019

Abstract

Disruptions in urban road networks can quickly and significantly reduce the quality of the whole trans-

portation network, and impact urban mobility for light vehicles, public transportation, etc. In this study, we

consider both unidirectional and multidirectional road network problems with disruptions and connecting

requirements. These problems aim at reconfiguring the urban network in terms of road direction in order

to maintain a path among all points of the network (strong connectivity). The former is defined on simple

graphs, mainly modeling part of a city such as historical centers, while the latter relies on multigraphs, mod-

eling more general networks. Restoring the network (strong connectivity) after some disruptions may require

the modification of the orientation of some streets,that is, arc reversals. Such actions can disturb users’ driving

habits.Thus, two objectives are considered separately:minimizing the total travel distance and minimizing the

number of arc reversals. Wedefine formally both problems and propose two metaheuristics, a biased random

key genetic algorithm and an iterated local search. Numerical experiments have been performed on a set of

generated instances and on the urban network of Troyes (France).

Keywords:network design; metaheuristics; biased random key genetic algorithm; iterated local search; smart mobility

1. Introduction

Due to the growing concentration of population in urban areas, the management of urban road

networks has become a major concern around the world. According to the World Urbanization

Prospects of the United Nations in 2014, the urban populationwill increase to about 6.3 billion over

9.5 billion of people by 2050 (nearly 66%). Unless major and radical changes in transportationhabits

happen, this implicitly leads to a sharp growthof traffic flows in urban areas, which mayincrease the

traffic congestion on the roadnetworks in metropolitan areas from medium to large cities.Extending

road networks infrastructures(adding new lanes or even brand new streets) can be a partial solution

∗Corresponding author.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

2716 Y. Huang et al. / Intl. Trans. in Op. Res.27 (2020) 2715–2739

Fig. 1. Example of strong connectivity restoration througharc reversal.

to this issue, even if it is expensive and time-consuming. However, it cannot always be performed

because urban sprawl and its urban network cannot be extended indefinitely. The situation becomes

more complicated when a disruption, either predictable (planned road work, social event, etc.)

or not (accident, bad weather condition, etc.), happens on road networks. It strongly impacts

urban mobility, particularly for light vehicles, public transportation, etc. since it reduces the traffic

capacity in the area, causes congestion, and possibly breaks travel paths between some locations

(loss of strong connectivity). Therefore, adapted strategies should be studied to manage urban road

networks properly, especially under such disruptions, as an essential requirement of smart mobility.

An urban network has a physical layer (infrastructure) as well as a logical layer over the infra-

structure that is made up of lane directions to carry the flow of vehicles. This work focuses on

the logical layer, especially on the road network problems with disruptions (RND) and connecting

requirements.According to the target zone in the logical urban network, the problem can be defined

as unidirectional RND (URND) or multidirectional RND (MRND). The formeroften corresponds

to road networks in historical city centers, where streets are almost one way and the network can

hence be modeled as a simple digraph. The latter addresses more general road networks using a

loopless directed multigraph model, where streets can be bidirectional and have multiple lanes in

each direction.

Forthe sake of clarity, it is important to mention the relation between the situationin practice and

modeling the logical layer. For instance, a road network can be modeled as a graph and must have

a path allowing the access to any point of the networks. In graph theory, this characteristic relates

to the so-called connectedness property for undirected graphs and the strong connectivity property

for directed graphs. Moreover, changing the orientation of a lane corresponds to modifying the

orientation of the corresponding arc, referred here as arc reversal. One may note that arc reversals

are likely to disturb users’ driving habits. As a consequence, few modifications should be done on

the network such that the strong connectivity is guaranteed. Last but not least, a disruption on the

road network is defined as an edge that becomes unavailable in undirected graphs, respectively, an

arc that becomes unavailable on digraphs.

An example of a disruption impact is given in Fig. 1. An initial road network with 6 nodes and

11 arcs is presented in Fig. 1(a). As seen in Fig. 1(b), a disruption happens on arc (5,2) and it is

now unavailable for carrying traffic (dashed line). The resulting digraph is not strongly connected

anymore since no pathis possible between each pair of nodes. Forinstance, node 2 cannot be reached

from anyother node. Reversing the orientation of arc (2,5) restoresthe strong connectivity, as shown

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies