An Accurate Solution to the Cardinality-Based Punctuality Problem

Zhiguang Cao · Yaoxin Wu · Felix Klanner · Stefan Erschen · Wei Chen · Le Zhang +1 more

17 citations0/0 files storedIEEE Intelligent Transportation Systems Magazine

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Transportation Planning and Optimization Complexity and Algorithms in Graphs Vehicle Routing Optimization Methods

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.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 17 citations exist upstream.

References

2010Understanding transportation modes based on GPS data for web applications 2000Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks 2009Shortest path problem considering on-time arrival probability 2005Arriving on Time 2002Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks 2011A tractable class of algorithms for reliable routing in stochastic networks 2017Maximizing the Probability of Arriving on Time: A Practical Q-Learning Method 2016Multiagent-Based Route Guidance for Increasing the Chance of Arrival on Time

Cited by

2021GP4: Gaussian Process Proactive Path Planning for the Stochastic on Time Arrival Problem 2020Improving the Performance of Transportation Networks: A Semi-Centralized Pricing Approach 2023GE-DDRL: Graph Embedding and Deep Distributional Reinforcement Learning for Reliable Shortest Path: A Universal and Scale Free Solution 2022Navigation With Time Limits in Transportation Networks: A Fourth Moment Approach

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.