Maximizing the probability of arriving on time : a stochastic shortest path problem

• Main Author: Cao, Zhiguang
• Other Authors: Zhang Jie
• Format: Theses and Dissertations
• Language: English
• Published: 2017
• Subjects: DRNTU::Engineering::General
• Online Access: http://hdl.handle.net/10356/69617
• Institution: Nanyang Technological University

Traffic and transportation are crucial to the sustainable development of most metropolitan cities, where the stochastic shortest path (SSP) problem for vehicle routing is a challenging topic. For this problem, optimization-based methods and multiagent-based methods are usually adopted to compute the optimal path for a single vehicle and multiple cooperative vehicles, respectively. Most of these methods take into account various uncertainties in traffic and yields route recommendations dynamically, leading to a better solution to the development of sustainable transportation systems. At the same time, various criteria for the optimal paths have been proposed for the SSP problem. Among them, the probability tail (PT) model aims to find a path that maximizes the probability of arriving on time. It is promising in that, it integrates travel time, risk (associated with the variance in the probability) and deadline. Therefore, this thesis focuses on solving this arriving on time problem, for a single vehicle and multiple cooperative vehicles. Regarding the former, an optimal path for a single vehicle is independently computed using the travel time data of the road links. Regarding the latter, the optimal paths for multiple vehicles are cooperatively computed by exploring their intentions. To circumvent the unrealistic assumptions in the current solutions to the arriving on time problem for a single vehicle, such as Gaussian distribution of travel time, independence among travel time on different road links, and relatively large deadlines, a data-driven approach is developed. More specifically, the PT model based SSP problem is first reformulated as a cardinality minimization problem by directly utilizing travel time data on each road link. Then, this minimization problem is approximately solved via relaxing the cardinality by L1-norm and its variants, and further formulating it as a mixed integer linear programming (MILP) problem. Consequently, this arriving on time problem becomes solvable via an existing MILP solver, e.g., branch and bound (B&B) method. To improve the computation efficiency of the data-driven approach, the property of total unimodularity (TU) that exists in the equality constraint of the MILP-based arriving on time problem is further explored. This nice property can guarantee integer solutions by solving the corresponding linear programming (LP) problem if there is no inequality constraint. In view of this, the partial Lagrange multiplier method is employed to relax the undesired inequality constraints in the MILP problem by shifting them to the objective function. After that, this relaxed problem is solved using the subgradient method in an iterative manner, and only LP problems need to be solved in each iteration, which saves computation cost significantly. To increase the accuracy of finding the real optimal path (i.e., considering that $\ell_{1}$-norm relaxation is an approximation to the cardinality minimization), a practical Q-learning method is developed. In particular, this Q-learning method aims to maximize the expected reward regarding whether the vehicle can arrive on time or not on a specified path. At the same time, the expected reward has the meaning of probability of arriving on time from a current location to destination. To address the issues of continuous deadlines and large-scale road networks, a practical value function approximation method is further proposed. Specifically, it adopts dynamic neural network to directly learn the optimal Q-value in each iteration, which which represents the probability of arriving at the destination on time. %Considering that the optimal Q-value represents the probability of reaching destination from current location before corresponding deadline, hence, results in more accurate solution. %to the PT model based SSP problem. To address the arriving on time problem for multiple cooperative vehicles, a decentralized multiagent-based approach is proposed. It aims to increase the chances of arriving on time for all relevant vehicles. In this approach, two types of agents are involved, i.e., vehicle agent and infrastructure agent. Each vehicle agent follows the route guidance by the local infrastructure agent, and the infrastructure agent collects intentions (i.e., destinations and preferred deadlines) from local vehicle agents. The infrastructure agent formulates the guidance as a route assignment problem, the objective of which is to minimize the cardinality of any possible delays for all local vehicle agents. At the same time, the route assignment problem for each infrastructure agent is solved by existing solvers. Additionally, the proposed route guidance approach is also improved in the aspects of travel time prediction for the assigned road link, computational efficiency of solving route assignment, and acquirement of real-time traffic condition. Extensive experiments on both artificial and real road networks are conducted to evaluate all the above proposed methods. The experimental results confirm the desirable advantages of the proposed methods over others. Therefore, the research in this thesis provides important contributions to the development of intelligent transportation systems.