An accurate solution to the cardinality-based punctuality problem
| Autor: | Wei Chen, Zhiguang Cao, Le Zhang, Felix Klanner, Akshay Rao, Yaoxin Wu, Hongliang Guo, Stefan Erschen |
|---|---|
| Přispěvatelé: | School of Computer Science and Engineering, Energy Research Institute @ NTU (ERI@N) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
Punctuality Computer science media_common.quotation_subject 02 engineering and technology Stochastic Shortest Path 0203 mechanical engineering 0502 economics and business Integer programming media_common 050210 logistics & transportation business.industry Stochastic process Mechanical Engineering 05 social sciences 020302 automobile design & engineering Automation Computer Science Applications Travel time Norm (mathematics) Automotive Engineering Shortest path problem Computer science and engineering [Engineering] Minification business |
| Popis: | 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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|