An accurate solution to the cardinality-based punctuality problem

This paper focuses on a specific stochastic shortest path (SSP) problem, namely the punctuality problem. It aims to determine a path that maximizes the probability of arriving at the destination before a specified deadline. The popular solution to this problem always formulates it as a cardinality m...

Full description

Saved in:
Bibliographic Details
Main Authors: Cao, Zhiguang, Wu, Yaoxin, Rao, Akshay, Klanner, Felix, Erschen, Stefan, Chen, Wei, Zhang, Le, Guo, Hongliang
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2020
Subjects:
Online Access:https://hdl.handle.net/10356/144359
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-144359
record_format dspace
spelling sg-ntu-dr.10356-1443592020-10-31T20:11:53Z An accurate solution to the cardinality-based punctuality problem Cao, Zhiguang Wu, Yaoxin Rao, Akshay Klanner, Felix Erschen, Stefan Chen, Wei Zhang, Le Guo, Hongliang School of Computer Science and Engineering Energy Research Institute @NTU Engineering::Computer science and engineering Punctuality Stochastic Shortest Path This paper focuses on a specific stochastic shortest path (SSP) problem, namely the punctuality problem. It aims to determine a path that maximizes the probability of arriving at the destination before a specified deadline. The popular solution to this problem always formulates it as a cardinality minimization problem by considering its data-driven nature, which is approximately solved by the`1-norm relaxation. To address this problem accurately, we consider the special character in the cardinality-based punctuality problem and reformulate it by introducing additional variables and constraints, which guarantees an accurate solution. The reformulated punctuality problem can be further transformed into the standard form of integer linear programming (ILP), thus, can be efficiently solved by using the existing ILP solvers. To evaluate the performance of the proposed solution, we provide both theoretical proof of the accuracy, and experimental analysis against the baselines. Particularly, the experimental results show that in the following two scenarios, 1) artificial road network with simulated travel time, 2) real road network with real travel time, our accurate solution works better than others regarding the accuracy and computational efficiency. Furthermore, three ILP solvers, i.e., CBC, GLPK and CPLEX, are tested and compared for the proposed accurate solution. The result shows that CPLEX has obvious advantage over others. Accepted version 2020-10-30T08:13:08Z 2020-10-30T08:13:08Z 2018 Journal Article Cao, Z., Wu, Y., Rao, A., Klanner, F., Erschen, S., Chen, W., . . . Guo, H. (2020). An accurate solution to the cardinality-based punctuality problem. IEEE Intelligent Transportation Systems Magazine, 12(4), 78-91. doi:10.1109/MITS.2018.2880260 1939-1390 https://hdl.handle.net/10356/144359 10.1109/MITS.2018.2880260 2-s2.0-85057430619 4 12 78 91 en IEEE Intelligent Transportation Systems Magazine © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.1109/MITS.2018.2880260. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Engineering::Computer science and engineering
Punctuality
Stochastic Shortest Path
spellingShingle Engineering::Computer science and engineering
Punctuality
Stochastic Shortest Path
Cao, Zhiguang
Wu, Yaoxin
Rao, Akshay
Klanner, Felix
Erschen, Stefan
Chen, Wei
Zhang, Le
Guo, Hongliang
An accurate solution to the cardinality-based punctuality problem
description This paper focuses on a specific stochastic shortest path (SSP) problem, namely the punctuality problem. It aims to determine a path that maximizes the probability of arriving at the destination before a specified deadline. The popular solution to this problem always formulates it as a cardinality minimization problem by considering its data-driven nature, which is approximately solved by the`1-norm relaxation. To address this problem accurately, we consider the special character in the cardinality-based punctuality problem and reformulate it by introducing additional variables and constraints, which guarantees an accurate solution. The reformulated punctuality problem can be further transformed into the standard form of integer linear programming (ILP), thus, can be efficiently solved by using the existing ILP solvers. To evaluate the performance of the proposed solution, we provide both theoretical proof of the accuracy, and experimental analysis against the baselines. Particularly, the experimental results show that in the following two scenarios, 1) artificial road network with simulated travel time, 2) real road network with real travel time, our accurate solution works better than others regarding the accuracy and computational efficiency. Furthermore, three ILP solvers, i.e., CBC, GLPK and CPLEX, are tested and compared for the proposed accurate solution. The result shows that CPLEX has obvious advantage over others.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Cao, Zhiguang
Wu, Yaoxin
Rao, Akshay
Klanner, Felix
Erschen, Stefan
Chen, Wei
Zhang, Le
Guo, Hongliang
format Article
author Cao, Zhiguang
Wu, Yaoxin
Rao, Akshay
Klanner, Felix
Erschen, Stefan
Chen, Wei
Zhang, Le
Guo, Hongliang
author_sort Cao, Zhiguang
title An accurate solution to the cardinality-based punctuality problem
title_short An accurate solution to the cardinality-based punctuality problem
title_full An accurate solution to the cardinality-based punctuality problem
title_fullStr An accurate solution to the cardinality-based punctuality problem
title_full_unstemmed An accurate solution to the cardinality-based punctuality problem
title_sort accurate solution to the cardinality-based punctuality problem
publishDate 2020
url https://hdl.handle.net/10356/144359
_version_ 1683494329794953216