4 présentations

• 
  10h30 - 10h55

  Anytime Optimization Approaches for Real-Time Ride-Sharing Systems

  • Elahe Amiri, prés., Polytechnique Montréal
  • Antoine Legrain, Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  Ridesharing is an on-demand transportation service that offers cost-effective and convenient options for a wide range of users. The emergence of commercial ride-sourcing companies has highlighted the need for advanced optimization techniques to handle vast numbers of ride requests efficiently in real-time. This paper introduces an anytime optimization approach for the online Dial-a-Ride Problem in the context of a large-scale real-time ride-sharing system. Unlike traditional algorithms that utilize fixed time epochs for batching requests, our proposed method employs a rolling-horizon strategy with flexible time epochs, combining the strengths of optimization batch methods and smaller batch sizes to provide a fast and efficient solution. Two primal-based algorithms within a column generation framework is introduced and evaluated against a traditional column generation method. The evaluation has been conducted on instances derived from historic taxi trips in New York City involving up to 30,000 requests per hour.

• 
  10h55 - 11h20

  Synchronisation des systèmes de transport à la demande avec les horaires des trains au niveau de plusieurs gares

  • El-Mehdi Mehiri, prés., Polytechnique Montréal
  • Antoine Legrain, Polytechnique Montréal
  • Quentin Cappart, Cirrelt

  Un système de transport a été développé par la SNCF combinant les avantages du ferroviaire et la flexibilité du mode routier, ce dernier étant un système de transport à la demande (TAD) censé servir les voyageurs dans les gares en transportant chacun vers un lieu déterminé, et amener les passagers chacun de son emplacement à la gare, tout en satisfaisant les préférences de chaque passager, telles que la durée maximale du trajet et l'heure de début du service au plus tôt. Pour optimiser ce système, nous présentons une méthode de génération de colonnes qui conçoit les itinéraires optimaux pour desservir tous les passagers, où les gares, les demandes et les véhicules sont hétérogènes, tout en respectant les contraintes de ressources, notamment la capacité des véhicules, la durée maximale de trajet, et les fenêtres du temps.

• 
  11h20 - 11h45

  An Efficient Real-time Multi-modal Single-leg Transportation System

  • Ali Akbar Sadat Asl, prés., Polytechnique Montreal
  • Antoine Legrain, Polytechnique Montréal

  Ridesharing has emerged as a promising solution to tackle urban mobility challenges, offering affordability and convenience while potentially alleviating congestion and environmental impact. This study investigates the use of a transportation hub, which serves as both the origin and destination of rideshare trips. The proposed system integrates personal vehicles with carpooling options and shuttle services as dynamic transit solutions to serve ride requests. Our study encompasses the needs and goals of users, operators, emissions reduction, and the overarching system efficiency. Employing a multifaceted approach, we solve the system optimization problem using column generation, ensuring that our investigation captures the diverse interests and priorities within the realm of urban mobility. Through this lens, we provide a holistic assessment of the proposed approach under various scenarios, illuminating its efficacy in addressing the complex challenges of large-scale urban mobility.

• 
  11h45 - 12h10

  Hub Transportation Problem with Chance Constrained Due Dates

  • Öykü Naz Attila, prés., Polytechnique Montreal
  • Antoine Legrain, Polytechnique Montréal
  • Quentin Cappart, Cirrelt

  Traditional public transportation systems provide efficient mass transportation solutions between designated stations. Despite its advantages, public transportation systems suffer from being restricted to serve a fixed area. This reduces its accessibility considerably, particularly in remote areas. Hub transportation systems overcome this problem by offering shuttle services to serve passengers who face such restrictions. These systems are highly time sensitive, as shuttles are required to return to their station by a due time to ensure that all passengers are served on time. From a decision making perspective, it is essential that the routing decisions made for shuttles are reliable against changes in travel times. To achieve this, we propose a chance constrained programming approach within a column generation framework that guarantees that the final solution remains feasible (with respect to meeting the due time) for at least a given probability of travel time scenarios. We introduce a sampling-based approach to reduce the size of the problem, and introduce procedures that maintain chance constraint feasibility under this framework. Computational experiments reveal that our approach yields routing decisions that remain immune against travel time uncertainty.