3 Presentations

• 
  03:30 PM - 03:55 PM

  Dynamic Relocations in Car-Sharing Networks

  • Mahsa Hosseini, presenter,
  • Gonzalo Romero,
  • Joseph Milner,

  We propose a novel dynamic car relocation policy for a car-sharing network with centralized control and uncertain, unbalanced demand. The policy is derived from a reformulation of the linear programming fluid model approximation of the dynamic problem. We project the full-dimensional fluid approximation onto the lower-dimensional space of relocation decisions only. This projection results in a characterization of the problem as n+1 linear programs, where n is the number of nodes in the network. The reformulation uncovers structural properties that are interpretable using absorbing Markov chain concepts and allows us to write the gradient with respect to the relocation decisions in closed form. Our policy exploits these gradients to make dynamic car relocation decisions. We provide extensive numerical results on hundreds of random networks where our dynamic car relocation policy consistently outperforms the standard static policy. Our policy reduces the optimality gap in steady-state by more than 23% on average. Also, in a short-term, time-varying setting, the lookahead version of our dynamic policy outperforms the static lookahead policy on average to a greater degree than that observed in the time-homogeneous tests.
• 
  03:55 PM - 04:20 PM

  Accelerating the resolution of the MDEVSP by column generation using dual inequalities predicted by machine learning

  • Louis Popovic, presenter, Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Quentin Cappart, CIRRELT - Polytechnique Montréal

  The multi depot electric vehicle scheduling problem (MDEVSP) is an NP-hard combinatorial optimization problem that involves assigning trips and visits to charging stations, if necessary, to electric buses. The problem is particularly challenging due to the limited range of electric buses, long charging times and sparsity of charging stations. Column generation is often used to solve this type of problem. However, even with the use of perturbation techniques, instances can suffer from degeneracy, which leads to long computational times. To address this issue, we propose an approach that uses dual inequalities to speed up the resolution of MDEVSP instances. Our method involves training a graph neural network based machine learning model to predict the direction of inequalities between pair of dual variables, which we then use to extract tight dual inequalities. We compare the times to solve the linear relaxation, i.e., the master problem (MP), with and without the use of dual inequalities. Our results show that the proposed method has the potential to significantly accelerate the resolution of the MP instances suffering from high degeneracy. However, there are some instances where these dual inequalities are insufficient to speed up the resolution.
• 
  04:20 PM - 04:45 PM

  Deep Learning-Based Travel Time Estimation for Intelligent Transportation Systems

  • Zahra Ejabati Emanab, presenter, Department of Supply Chain Management, Asper School of Business, University of Manitoba
  • Yuvraj Gajpal, Department of Supply Chain Management, Asper School of Business, University of Manitoba
  • Srimantoorao Appadoo, Department of Supply Chain Management, Asper School of Business, University of Manitoba

  In this paper, we propose a novel approach to accurately estimate travel time using deep learning algorithms. The importance of accurate travel time estimation lies in its application in various domains such as intelligent transportation systems, routing, ridesharing, traffic management, and urban planning, among others, enabling effective decision-making and efficient use of transportation resources. The proposed method utilizes a combination of convolutional neural networks (CNN), long short-term memory neural networks (LSTM), and temporal convolutional networks (TCN) to capture the complex spatial and temporal characteristics of traffic flow. Then we leverage multitask learning including fully connected neural networks and attention mechanisms to predict travel time. To validate the effectiveness of our approach, we conducted experiments using real-world taxi GPS data collected from Chengdu city. Our model outperformed traditional models and existing data-driven methods, as evidenced by the lower mean absolute percentage error (MAPE) achieved. In summary, our research presents an innovative and promising approach to travel time estimation using deep learning techniques, highlighting the potential for significant improvements in transportation efficiency.