An integrated assignment routing and speed model for roadway mobility and transportation with environmental eciency and service goals

2025-04-27 0 0 1.28MB 29 页 10玖币

侵权投诉

An integrated assignment, routing, and speed model

for roadway mobility and transportation

with environmental, eﬃciency, and service goals

T. Giovannelli∗L. N. Vicente†

October 10, 2022

Abstract

Managing all the mobility and transportation services with autonomous vehicles for users

of a smart city requires determining the assignment of the vehicles to the users and their

routing in conjunction with their speed. Such decisions must ensure low emission, eﬃciency,

and high service quality by also considering the impact on traﬃc congestion caused by other

vehicles in the transportation network.

In this paper, we ﬁrst propose an abstract trilevel multi-objective formulation architec-

ture to model all vehicle routing problems with assignment, routing, and speed decision

variables and conﬂicting objective functions. Such an architecture guides the development

of subproblems, relaxations, and solution methods. We also propose a way of integrating

the various urban transportation services by introducing a constraint on the speed variables

that takes into account the traﬃc volume caused across the diﬀerent services. Based on the

formulation architecture, we introduce a (bilevel) problem where assignment and routing are

at the upper level and speed is at the lower level. To address the challenge of dealing with

routing problems on urban road networks, we develop an algorithm that alternates between

the assignment-routing problem on an auxiliary complete graph and the speed optimization

problem on the original non-complete graph. The computational experiments show the ef-

fectiveness of the proposed approach in determining approximate Pareto fronts among the

conﬂicting objectives.

1 Introduction

In this paper, we propose an innovative integrated transportation model for the management

of possibly all vehicles traveling on the streets and roads of a city, which are assumed to have

diﬀerent levels of autonomy (with or without a driver). Our main goal is to provide an optimiza-

tion model that can be used to eﬀectively manage mobility and transportation within a city by

adopting a green logistics perspective and pursuing eﬃciency and service quality. The integrated

model introduced in this work will qualify the cities implementing the proposed transportation

network as smart.

∗Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USA

(tog220@lehigh.edu).

†Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USA

(lnv@lehigh.edu). Support for this author was partially provided by the Centre for Mathematics of the University

of Coimbra under grant FCT/MCTES UIDB/MAT/00324/2020.

arXiv:2210.03717v1 [math.OC] 7 Oct 2022

The achievement of our goal will be enabled by the recent (and future) advances in infor-

mation and location-sensitive technologies, which facilitate acquiring the necessary high-quality

(granular) data for supporting the decision-making process for vehicles traveling on the streets

and roads of a smart city. Several deﬁnitions of smart city have been proposed in the literature

(see, e.g., Nam and Pardo (2011), Bronstein (2009), and Wenge et al. (2014)) and a universal

characterization cannot be provided since smart cities involve diﬀerent types of features that

vary based on the speciﬁc context considered (Karvonen et al. (2018)). In general, the phrase

smart city refers to cities provided with technological infrastructure based on advanced data pro-

cessing that pursue several goals, such as a more eﬃcient city governance, a better life quality for

citizens, increasing economic success for businesses, and a more sustainable environment (Yin

et al. (2015)).

In our paper, we focus on smart cities with intelligent transportation systems (see Xiong

et al. (2012) for a survey). In particular, all the smart cities provided with technologies for

real-time transportation data acquisition ﬁt within the scope of our work. However, we point

out that the process leading to the acquisition of such technologies, which requires a multitude of

social, political, and economic factors involving public-private partnerships and local authorities,

is omitted from this paper. The importance of the role played by mobility and transportation

in smart cities is highlighted in many works (Yin et al. (2015)). For instance, in Tang et al.

(2019), four diﬀerent groups of smart cities are identiﬁed based on a cluster analysis of cities

around the world, and one of them gathers cities adopting smart transportation systems. The

goal of such systems is to control traﬃc congestion by public transportation, car sharing, and

self-driving cars. In Arroub et al. (2016), the urban congestion is seen as a challenge arising

from the persistent need of citizens to use their private cars. A solution proposed to alleviate

such a problem requires smart control of the traﬃc in the existing road infrastructure to ensure

a sustainable transportation, which is exactly the goal of our paper.

A crucial tool for managing transportation in smart cities is the concept of urban artiﬁcial

intelligence (AI) (Cugurullo (2020)). Among the examples of urban AI, self-driving cars and city

brains represent two important categories. In particular, the author points out that the number

of cities where autonomous cars are allowed to drive is increasing (see also Acheampong and

Cugurullo (2019)), and these also include cars with the highest level of autonomy, when no human

input or supervision are required. A city brain is a digital platform applied to the management

of a city, including urban transportation, where the goal is to control traﬃc lights and ﬂows

of vehicles by using advanced data collected throughout the city. In this paper, we assume

that our integrated model is used by a city brain for the urban transportation management of

autonomous vehicles. However, the development of the features of such a platform is left for

future work.

The presence of autonomous vehicles in a transportation network allows for the determination

of the assignment of vehicles to users and their routing in conjunction with their speed, thus

increasing the complexity of the decision-making process, which is naturally formulated as a

hierarchy of three levels (assignment, routing, and speed). Transportation and mobility solutions

should be determined with low environmental impact but, at the same time, with high eﬃciency

for service providers and high service quality for users, leading to conﬂicting goals which need

to be optimized simultaneously. Moreover, decisions unilaterally made in one component or

part of the network can have a strong impact on the overall system. Consequently, the optimal

solutions of the single components considered separately are diﬀerent from the solutions obtained

when such interaction is taken into account, thus requiring a proper integration of the network

components. Finally, the current modeling techniques for assignment-routing problems are based

on assumptions that are not satisﬁed on urban road networks and, therefore, require innovative

solution methodologies. We aim at developing a future-oriented integrated assignment, routing,

and speed system for roadway mobility and transportation with environmental, eﬃciency, and

service goals, and this paper represents an instrumental building block towards this main goal

and where we make the following three main contributions.

A trilevel multi-objective formulation architecture for vehicle routing prob-

lems with speed optimization

We propose an innovative formulation architecture to decompose every Vehicle Routing Prob-

lem (VRP) with speed optimization into three levels, each addressing one of the following vehicle-

related decisions: assignment to users, routing to accommodate all the requests, and speed along

each segment of the route∗. In particular, our paper extends the bilevel formulation developed

by Marinakis et al. (2007) to propose a trilevel multi-objective formulation for a VRP with speed

optimization (referred to as a VRP/speed problem). Such an architecture allows a comprehen-

sive understanding of the overall problem complexity, guides the development of subproblems,

relaxations, and solution methods, and provides new insights into VRP/speed problems. In this

paper, we use the trilevel multi-objective architecture to formulate a (bilevel) VRP/speed prob-

lem (where upper level is assignment-routing and lower level is speed), develop a corresponding

optimization method, and identify and report the trade-oﬀs among the three considered goals.

Integration among all the diﬀerent transportation problem components in a

smart city

The transportation services arising in an urban transportation network can be modeled through

a proper VRP variant. All the frameworks, models, and methods proposed in the literature

address the diﬀerent transportation services arising in a city independently, without any attempt

to consider such services as parts of the same system. Several studies in the literature considered

modeling a general framework accounting for as many transportation services as possible. For

example, Vidal et al. (2014) proposed a uniﬁed model capable of separately describing diﬀerent

transportation problem components (later referred to as components). However, the goal of Vidal

et al. (2014) was to propose a general-purpose optimization algorithm that can quickly provide

eﬃcient solutions to diﬀerent problems, each related to a transportation service. In contrast, our

paper aims to develop a new general model, where diﬀerent transportation components (such as

personal trips, freight transportation, ride-sharing, car-pooling, dial-a-ride, and vehicle sharing)

can be integrated into a comprehensive optimization framework. In this regard, we propose

a VRP/speed formulation for a speciﬁc problem component, which is suﬃcient to fully address

the integration among all the components. In particular, in such a formulation, an innovative

constraint on the speed variables is used to model the impact of the traﬃc congestion caused

by routing decisions (made in other components) on the component under consideration.

∗Note that although controlling the speed in roadway transportation is considered an impractical task (see,

e.g., Vidal et al. (2020)), considering smart and autonomous vehicles allows one to take into account speed

decisions.

Use of non-complete graphs for vehicle routing problems with speed optimiza-

tion

Using non-complete graphs is essential to address a VRP/speed problem on urban road networks.

However, to ﬁnd the value of the speed variables for each edge in the network, we cannot directly

resort to commonly used approaches for non-complete graphs (which build a complete graph

by combining the edges in the shortest path between two customer nodes into a single edge).

Therefore, we propose an approach that computes an approximate solution to the assignment-

routing (upper level) problem on the road network by ﬁrst solving such a problem on an auxiliary

complete graph. This mechanism allows one to use existing VRP methods for complete graphs,

without the need to formulate the assignment-routing problem on the non-complete graph,

where some of the classical VRP constraints are most likely infeasible. Then, considering the

approximate assignment-routing solution as a parameter, we develop a formulation for the speed

optimization (lower level) problem on a non-complete graph. It is important to remark that VRP

with green-oriented objectives and speed optimization is well-known in the literature (Bektas

and Laporte (2011)). However, considering such a problem on a road network represents, to the

best of our knowledge, a novel contribution, thus requiring a new solution methodology.

1.1 Organization of this paper

This paper is organized as follows. Section 2 provides a general overview of the main opti-

mization models adopted to solve transportation problems on complete graphs and road net-

works. The trilevel multi-objective formulation architecture is described in Section 3. Section 4

presents an innovative constraint to model the integration among all the diﬀerent transporta-

tion components. In Section 5, the trilevel multi-objective architecture is used to formulate a

(bilevel) VRP/speed problem on a non-complete graph and an optimization method is developed

to solve such a problem. The computational experiments are described in Section 6. Finally, in

Section 7 we draw some concluding remarks and we outline several ideas for future work.

2 Literature review

2.1 Optimization models for transportation on complete graphs

Transportation services across a city have been widely studied within the ﬁeld of Operations

Research (see, e.g., Kim et al. (2015) and Cattaruzza et al. (2017)). Optimization problems

related to such services are variants of the basic VRP, where a ﬂeet of vehicles is used to deliver

goods to a set of customer nodes. Two important decisions are considered: assigning groups of

customers to each vehicle and deﬁning the corresponding route.

The Pickup and Delivery Problem (PDP) is a VRP variant where people or objects need

to be transported from an origin to a destination (examples of PDPs are ride-sharing, carpool

problem, dial-a-ride problem, and vehicle-sharing). Classical VRPs and PDPs can be combined

in the so-called people and freight integrating transportation problems, which deal with the

integration of passenger and freight transportation. Their objective is to increase the occupancy

rate by letting the spare seats in the vehicles be used to transport goods (see, e.g., Beirigo et al.

(2018), Chen et al. (2018), Li (2016), and Ghilas et al. (2013)). In this way, each vehicle can

carry passengers, goods, or both of them.

The pollution-routing problem, introduced by Bektas and Laporte (2011), extends the classi-

cal VRP by taking into account not only the traveled distance between origin and destination,

but also the fuel consumed and the emissions generated by the vehicles. The aim is to ﬁnd a

proper route and speed for each vehicle, allowing customers’ requests to be met, by minimizing

the overall operational and environmental cost, while respecting time windows and capacity con-

straints (see, e.g., Kramer et al. (2014), Qian and Eglese (2014), Fukasawa et al. (2018), Nasri

et al. (2018), and Sung and Nielsen (2020)). More challenging problems arise when the stochas-

tic (Ritzinger et al. (2016), Oyola et al. (2016a), Oyola et al. (2016b), Eshtehadi et al. (2017)),

dynamic (Pillac et al. (2013), Berbeglia et al. (2010)), and multi-objective (Garc´ıa N´ajera and

Bullinaria (2009), Ghoseiri and Ghannadpour (2010), Demir et al. (2014a), Kumar et al. (2016))

versions are taken into account. When route is considered ﬁxed and the only variable is the ve-

hicle speed, the problem is called the speed optimization problem (see Fagerholt et al. (2010)).

The problem considered in our paper can be included in the class of pollution-routing problems

because the environmental-impact objective is considered together with speed optimization.

In the literature, few works address a VRP (on a complete graph) by adopting a multi-level

formulation, and all of them propose a bilevel problem (see, e.g., Gupta et al. (2015), Marinakis

et al. (2007), Marinakis and Marinaki (2008), and Ma and Xu (2014)). In particular, in Gupta

et al. (2015) and Marinakis et al. (2007), the authors use an assignment-routing formulation to

solve a classical VRP. Similarly, Marinakis and Marinaki (2008) propose two nested optimization

levels to deal with a VRP integrated with a facility location problem but, in contrast with

Gupta et al. (2015) and Marinakis et al. (2007), the objective functions involved in each level

are conﬂicting with each other. In our paper, we take advantage of the hierarchical structure

at stake by proposing an optimization method that alternates between the assignment-routing

problem and the speed optimization problem until a satisfactory solution is returned. Diﬀerently

from the bilevel approach of Gupta et al. (2015), which extends the work of Marinakis et al.

(2007) to the bi-objective case by considering eﬃciency and service quality in each level, we also

account for the environmental impact as a third objective.

2.2 Optimization models for transportation on road networks

When considering road networks and, consequently, non-complete graphs (i.e., graphs that do

not contain an edge for every pair of nodes), routing problems face additional challenges be-

cause key assumptions are not satisﬁed (see, e.g., Fleischmann (1985), Cornu´ejols et al. (1985),

Ben Ticha et al. (2018), Ben Ticha et al. (2021b)). In particular, only a subset of nodes are

customers since most of the nodes are associated with cross-roads, which do not have a demand

to meet. Therefore, only some nodes need to be visited by the vehicles involved in the problem,

which is in contrast with the traditional VRP formulations considering each node in the graph

as a customer. Moreover, it may not be possible to ﬁnd a route that visits nodes and edges

only once, thus leading to problems with an empty feasible set. Recently, exact approaches to

solve routing problems on a subset of nodes have been proposed in Raeesi and Zografos (2019)

and Boyacı et al. (2021) for VRP, Rodr´ıguez-Pereira et al. (2019) for the traveling salesman

problem (TSP), and Ben Ticha et al. (2021a) for the shortest path problem. Such papers belong

to the stream of works focusing on the so-called Steiner TSP, which was addressed for the ﬁrst

time by Fleischmann (1985) and Cornu´ejols et al. (1985).

On road networks, arcs may be associated with several attributes (distance, cost, time, etc.),

and this implies that the shortest path does not coincide with the cheapest or quickest path.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Anintegratedassignment,routing,andspeedmodelforroadwaymobilityandtransportationwithenvironmental,eciency,andservicegoalsT.Giovannelli*L.N.VicenteOctober10,2022AbstractManagingallthemobilityandtransportationserviceswithautonomousvehiclesforusersofasmartcityrequiresdeterminingtheassignmentofthevehic...

展开>> 收起<<

An integrated assignment routing and speed model for roadway mobility and transportation with environmental eciency and service goals.pdf

共29页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

An integrated assignment routing and speed model for roadway mobility and transportation with environmental eciency and service goals

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: