Multi-Objective Predictive Taxi Dispatch via Network Flow Optimization

Abstract

In this paper, we discuss a large-scale fleet management problem in a multi-objective setting. We aim to seek a receding horizon taxi dispatch solution that serves as many ride requests as possible while minimizing the cost of relocating vehicles. To obtain the desired solution, we first convert the multi-objective taxi dispatch problem into a network flow problem, which can be solved using the classical minimum cost maximum flow (MCMF) algorithm. We show that a solution obtained using the MCMF algorithm is integer-valued; thus, it does not require any additional rounding procedure that may introduce undesirable numerical errors. Furthermore, we prove the time-greedy property of the proposed solution, which justifies the use of receding horizon optimization. For computational efficiency, we propose a linear programming method to obtain an optimal solution in near real time. The results of our simulation studies using real-world data for the metropolitan area of Seoul, South Korea indicate that the performance of the proposed predictive method is almost as good as that of the oracle that foresees the future.

28 pages, 12 figures, Published in IEEE Access

References in corpus (6)

• Safe Exploration in Continuous Action Spaces
• Multi-Agent Reinforcement Learning for Order-dispatching via Order-Vehicle Distribution Matching
• A Cooperative Multi-Agent Reinforcement Learning Framework for Resource Balancing in Complex Logistics Network
• Optimizing Online Matching for Ride-Sourcing Services with Multi-Agent Deep Reinforcement Learning
• Can Sophisticated Dispatching Strategy Acquired by Reinforcement Learning? - A Case Study in Dynamic Courier Dispatching System
• Distributed Policy Iteration for Scalable Approximation of Cooperative Multi-Agent Policies