Data-Driven Optimization for Dynamic Shortest Path Problem Considering Traffic Safety

Shan Jiang; Yilun Zhang; Ran Liu; Mohsen Jafari; Mohamed Kharbeche

doi:https://doi.org/10.1109/TITS.2022.3165757

Data-Driven Optimization for Dynamic Shortest Path Problem Considering Traffic Safety

Shan Jiang, Yilun Zhang, Ran Liu, Mohsen Jafari, Mohamed Kharbeche

School of Engineering, Industrial Engineering

Rutgers, The State University

Research output: Contribution to journal › Article › peer-review

Abstract

Traffic congestion is an inescapable problem that frustrates drivers in megacities. Although there is hardly a way to eliminate the congestion, it is possible to mitigate the impact through predictive methods. This paper develops a data-driven optimization approach for the dynamic shortest path problems (DSPP), considering traffic safety for urban navigations. The dynamic risk scores and travel times at different times and locations are estimated by the Safe Route Mapping (SRM) methodology and Long Short-Term Memory (LSTM) with Autoencoder, respectively, where possible variations in the future are considered. The DSPP is formulated as a mixed-integer linear programming problem under risk constraints to minimize the total travel cost, defined as the weighted sum of distance and travel time. To improve the efficiency of the DSPP, we design an improved tabu search with alternative initial-solution algorithms to accommodate various problem scales. Moreover, subgraph and self-adaptive insertion techniques are adopted as acceleration strategies to enhance computational efficiency further. Numerical experiments investigate the computational performance and the solution quality of our algorithm. The result shows satisfactory solution quality and computational efficiency with the proposed acceleration strategies compared to the CPLEX solver, a label-setting algorithm, and a state-of-the-art algorithm. Our algorithm can also compete with Google Maps regarding the travel cost in a real network in Manhattan, NY, USA, which is promising for Urban Navigations.

Original language	American English
Pages (from-to)	18237-18252
Number of pages	16
Journal	IEEE Transactions on Intelligent Transportation Systems
Volume	23
Issue number	10
DOIs	https://doi.org/10.1109/TITS.2022.3165757
State	Published - Oct 1 2022

ASJC Scopus subject areas

Mechanical Engineering
Automotive Engineering
Computer Science Applications

Keywords

Data-driven optimization
dynamic shortest path problem
risk prediction
tabu search
travel time prediction
urban navigation

Access to Document

https://doi.org/10.1109/TITS.2022.3165757

Cite this

@article{1426365f8cb8412887e9be5efd7dfb35,

title = "Data-Driven Optimization for Dynamic Shortest Path Problem Considering Traffic Safety",

abstract = "Traffic congestion is an inescapable problem that frustrates drivers in megacities. Although there is hardly a way to eliminate the congestion, it is possible to mitigate the impact through predictive methods. This paper develops a data-driven optimization approach for the dynamic shortest path problems (DSPP), considering traffic safety for urban navigations. The dynamic risk scores and travel times at different times and locations are estimated by the Safe Route Mapping (SRM) methodology and Long Short-Term Memory (LSTM) with Autoencoder, respectively, where possible variations in the future are considered. The DSPP is formulated as a mixed-integer linear programming problem under risk constraints to minimize the total travel cost, defined as the weighted sum of distance and travel time. To improve the efficiency of the DSPP, we design an improved tabu search with alternative initial-solution algorithms to accommodate various problem scales. Moreover, subgraph and self-adaptive insertion techniques are adopted as acceleration strategies to enhance computational efficiency further. Numerical experiments investigate the computational performance and the solution quality of our algorithm. The result shows satisfactory solution quality and computational efficiency with the proposed acceleration strategies compared to the CPLEX solver, a label-setting algorithm, and a state-of-the-art algorithm. Our algorithm can also compete with Google Maps regarding the travel cost in a real network in Manhattan, NY, USA, which is promising for Urban Navigations.",

keywords = "Data-driven optimization, dynamic shortest path problem, risk prediction, tabu search, travel time prediction, urban navigation",

author = "Shan Jiang and Yilun Zhang and Ran Liu and Mohsen Jafari and Mohamed Kharbeche",

note = "Funding Information: This work was supported by the Research Grant from the National Natural Science Foundation of China under Grant 71972133 and Grant 71672112. Publisher Copyright: {\textcopyright} 2000-2011 IEEE.",

year = "2022",

month = oct,

day = "1",

doi = "https://doi.org/10.1109/TITS.2022.3165757",

language = "American English",

volume = "23",

pages = "18237--18252",

journal = "IEEE Transactions on Intelligent Transportation Systems",

issn = "1524-9050",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "10",

}

TY - JOUR

T1 - Data-Driven Optimization for Dynamic Shortest Path Problem Considering Traffic Safety

AU - Jiang, Shan

AU - Zhang, Yilun

AU - Liu, Ran

AU - Jafari, Mohsen

AU - Kharbeche, Mohamed

N1 - Funding Information: This work was supported by the Research Grant from the National Natural Science Foundation of China under Grant 71972133 and Grant 71672112. Publisher Copyright: © 2000-2011 IEEE.

PY - 2022/10/1

Y1 - 2022/10/1

N2 - Traffic congestion is an inescapable problem that frustrates drivers in megacities. Although there is hardly a way to eliminate the congestion, it is possible to mitigate the impact through predictive methods. This paper develops a data-driven optimization approach for the dynamic shortest path problems (DSPP), considering traffic safety for urban navigations. The dynamic risk scores and travel times at different times and locations are estimated by the Safe Route Mapping (SRM) methodology and Long Short-Term Memory (LSTM) with Autoencoder, respectively, where possible variations in the future are considered. The DSPP is formulated as a mixed-integer linear programming problem under risk constraints to minimize the total travel cost, defined as the weighted sum of distance and travel time. To improve the efficiency of the DSPP, we design an improved tabu search with alternative initial-solution algorithms to accommodate various problem scales. Moreover, subgraph and self-adaptive insertion techniques are adopted as acceleration strategies to enhance computational efficiency further. Numerical experiments investigate the computational performance and the solution quality of our algorithm. The result shows satisfactory solution quality and computational efficiency with the proposed acceleration strategies compared to the CPLEX solver, a label-setting algorithm, and a state-of-the-art algorithm. Our algorithm can also compete with Google Maps regarding the travel cost in a real network in Manhattan, NY, USA, which is promising for Urban Navigations.

AB - Traffic congestion is an inescapable problem that frustrates drivers in megacities. Although there is hardly a way to eliminate the congestion, it is possible to mitigate the impact through predictive methods. This paper develops a data-driven optimization approach for the dynamic shortest path problems (DSPP), considering traffic safety for urban navigations. The dynamic risk scores and travel times at different times and locations are estimated by the Safe Route Mapping (SRM) methodology and Long Short-Term Memory (LSTM) with Autoencoder, respectively, where possible variations in the future are considered. The DSPP is formulated as a mixed-integer linear programming problem under risk constraints to minimize the total travel cost, defined as the weighted sum of distance and travel time. To improve the efficiency of the DSPP, we design an improved tabu search with alternative initial-solution algorithms to accommodate various problem scales. Moreover, subgraph and self-adaptive insertion techniques are adopted as acceleration strategies to enhance computational efficiency further. Numerical experiments investigate the computational performance and the solution quality of our algorithm. The result shows satisfactory solution quality and computational efficiency with the proposed acceleration strategies compared to the CPLEX solver, a label-setting algorithm, and a state-of-the-art algorithm. Our algorithm can also compete with Google Maps regarding the travel cost in a real network in Manhattan, NY, USA, which is promising for Urban Navigations.

KW - Data-driven optimization

KW - dynamic shortest path problem

KW - risk prediction

KW - tabu search

KW - travel time prediction

KW - urban navigation

UR - http://www.scopus.com/inward/record.url?scp=85128671882&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85128671882&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/TITS.2022.3165757

DO - https://doi.org/10.1109/TITS.2022.3165757

M3 - Article

SN - 1524-9050

VL - 23

SP - 18237

EP - 18252

JO - IEEE Transactions on Intelligent Transportation Systems

JF - IEEE Transactions on Intelligent Transportation Systems

IS - 10

ER -

Data-Driven Optimization for Dynamic Shortest Path Problem Considering Traffic Safety

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this