Please use this identifier to cite or link to this item:
Title: An accurate solution to the cardinality-based punctuality problem
Authors: Cao, Zhiguang
Wu, Yaoxin
Rao, Akshay
Klanner, Felix
Erschen, Stefan
Chen, Wei
Zhang, Le
Guo, Hongliang
Keywords: Engineering::Computer science and engineering
Issue Date: 2018
Source: 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
Journal: IEEE Intelligent Transportation Systems Magazine 
Abstract: 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.
ISSN: 1939-1390
DOI: 10.1109/MITS.2018.2880260
Rights: © 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:
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:ERI@N Journal Articles

Files in This Item:
File Description SizeFormat 
An Accurate Solution to the Cardinality-Based Punctuality Problem.pdf4.06 MBAdobe PDFThumbnail

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.