Robust prediction and decision making for transportation networks

• Main Author: Prokhorchuk, Anatolii
• Other Authors: Justin Dauwels
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Computer science and engineering; Engineering::Electrical and electronic engineering
• Online Access: https://hdl.handle.net/10356/146430
• Institution: Nanyang Technological University

Travel time uncertainty can have a significant impact on the performance of Intelligent Transportation Systems. Various applications such as routing or pricing can benefit from accurate estimations of travel times. In this thesis, we propose an approach that can estimate travel time distributions for any path in the road network using GPS data. We focus on situations when only sparse data is available: we consider a dataset that contains GPS trajectories from probe vehicles sampled on average with 1-minute intervals. We propose employing a novel Bayesian network inference algorithm and combining it with the Gaussian copula model. This allows us to estimate the marginal distributions and the covariance structure separately. We compare the performance of the proposed framework with some of the commonly applied methods such as graphical lasso. Our framework achieves superior performance in terms of the Kullback-Leibler divergence and the Hellinger distance based on the real-world dataset. Next, we consider a routing problem that can benefit from considering the uncertainty of travel times. Namely, we formulate the dynamic pricing for same-day delivery routing with stochastic travel times problem. The goal of this problem is to maximize the revenue of a delivery company that offers same-day delivery services by jointly optimizing routing and pricing decisions. We employ a Markov decision process to model this problem. To overcome the curse of dimensionality, we utilize a value function approximation technique that is then employed to compute the opportunity costs. We perform a thorough computational study to understand how incorporating travel time distribution information affects the model performance with respect to various metrics. We also investigate how simulation parameters such as the number of orders and the fleet size influence this effect. Additionally, we consider situations where travel time distributions are not fully known. Next, we investigate how estimating travel time distributions via copula-based model can influence the overall model performance. Last, we consider an extension of this problem that can model some of the most recent real-world challenges. In this problem, in addition to the company fleet, the deliveries can be made by a pool of private part-time drivers. Here, the goal is to dynamically provide compensation to these drivers while, at the same time, providing pricing decisions to customers. To solve the problem of matching customer delivery requests with available private drivers we combine machine learning methods that predict expected revenue with mixed-integer programming. In an extensive computation study, we investigate how dynamic compensation for crowdsourced drivers affects both the company's profits and the drivers' welfare. The results show that the proposed approach outperforms the baseline policies.