Smart Reservation and Sketch Timetabling Based on ADMM: A Dual-Decomposition Algorithm Application

Abstract

In order to mitigate congestion of urban transportation network, this paper propose a reservation scheme. Given users’ preferred departure time, arrival time and flexible time windows at both origins and destinations, the centralized reserving and scheduling system determines agents’ departure times, routes and trajectories with appropriate resolution, which aims to minimize the total traveling disutility involving travel times, waiting times queues and delays. After dividing traffic condition into various modes such as free flow, congestion, hyper-congestion and so on, the reservation model is built on a high-dimensional discretized space-time-mode network. This reservation and sketching timetabling problem can be formulated as a multi-commodity flow optimization problem with additional side constraints, such as capacity constraints under different operating mode. The multi-commodity flow problem (i.e. the master problem) is divided into two sub-problems. One is knapsack problem which determine the sequence of activated space-time-mode arcs. The other is agents’ shortest path problem. We further use Alternative Direction Method of Multiplier (ADMM) to solve the shortest path problem above based on dual decomposition methodology. Finally numerical cases are used to show the benefits of reservation timetabling.

Keywords

• Reservation timetabling
• multiple traffic modes
• space-time-mode network
• ADMM