3 Presentations

• 
  10:30 AM - 10:55 AM

  Two-stage stochastic set packing for ridesharing systems

  • Gabriel Homsi, presenter, CIRRELT, University of Montreal
  • Sanjay Dominik Jena, Université du Québec à Montréal
  • Bernard Gendron, Université de Montréal, CIRRELT

  We introduce a two-stage stochastic set packing problem for ridesharing. In this problem, drivers are booked at the first stage and riders are released on the second stage, and the release of riders is uncertain. Additionally, drivers may have different levels of booking that influence the profit and the delay tolerance of the rideshare. Our modeling framework is generic enough to represent three problem variants that cover a wide range of ridesharing operations. To approximate the second-stage value function of the two-stage model, we introduce sample average approximation and expected value formulations. We test these formulations on a set of benchmark instances and show how uncertainty is dealt with on each problem variant.

• 
  10:55 AM - 11:20 AM

  Data-driven Prioritization Strategies for Inventory Rebalancing in Bike-sharing systems

  • Maria Clara Martins Silva, presenter, Polytechnique Montréal
  • Daniel Aloise, Polytechnique Montréal
  • Sanjay Dominik Jena, Université du Québec à Montréal

  The popularity of bike-sharing systems has constantly increased throughout the last years, given their convenience for users, low usage costs, health benefits, and their contribution to environmental relief. However, satisfying all user demands remains a challenge, given that the inventory of bike-sharing stations tends to be unbalanced over time. Bike-sharing system operators therefore explicitly rebalance station inventories in order to provide both available bikes and empty docks to the commuters. In most systems, the operator manually selects the stations and amounts of bikes to be rebalanced among those that are considered unbalanced. In practice, such manual planning is likely to result in suboptimal system performance.
  In this paper, we propose three variants of a machine learning-based algorithm to select the stations that should be prioritized for rebalancing, using features such as the inventory levels in the stations and the predicted trip demand. We evaluate the performance of these prioritization strategies by simulating real-world trips using data from 2019 and 2020, each of which exhibits distinct travel patterns given the restrictive measures implemented in 2020 to prevent the spread of COVID-19. Our results reveal that our algorithms can significantly improve the system's performance, reducing the lost demand up to 17% and the required rebalancing operations up to 12%.

• 
  11:20 AM - 11:45 AM

  Dynamic Rebalancing in Bike-sharing Systems: A Modeling Framework and Empirical Comparison

  • Jiaqi Liang, presenter, Polytechnique Montréal
  • Sanjay Dominik Jena, Université du Québec à Montréal
  • Andrea Lodi, Polytechnique Montreal

  Bike-sharing systems offer a low-cost and environmentally friendly transportation alternative to private vehicles. Unfortunately, stations are often unbalanced, and therefore rental demands cannot always be satisfied. System operators employ trucks to rebalance bikes among the stations. However, planning effective rebalancing is a challenging task, which has resulted in a large body of literature on modeling rebalancing planning. While such works make different assumptions and use different modeling techniques regarding decision variables and constraints used, the impact of such assumptions on the solutions’ performance in practice is generally unexplored. We first systematically survey the literature on rebalancing problems and their modeling assumptions. We then propose a general modeling framework for multi-period dynamic rebalancing, where different components can be adapted to different assumptions. Finally, we generate detailed problem instances, inspired by real-world trip data and propose a realistic simulator to evaluate the performance of the rebalancing strategies. Extensive numerical experiments are presented, concluding the effectiveness of the various modeling assumptions.