SCRO / Journées de l'optimisation

HEC Montréal, 29-31 mai 2023


HEC Montréal, 29 — 31 mai 2023

Horaire Auteurs Mon horaire

ASDPII Applications of Sequential Decision Problems II

29 mai 2023 15h30 – 17h10

Salle: Cogeco (bleu)

4 présentations

  • 15h30 - 15h55

    Data-Driven Online Stochastic Synchronization Strategies of A Bus Line In A Transit Network

    • Laura Kolcheva, prés.,
    • Antoine Legrain, Polytechnique Montréal
    • Martin Trépanier, Polytechnique Montréal, CIRRELT

    The waiting time of passengers at transfer stations is one of the most important criteria to measure the service quality of public bus transportation. Because of the stochastic nature of traffic, scheduled transfers cannot always occur. This research develops an online control framework for a bus network using holding, skip-stop and speed change tactics. We build an arc-flow model integrating all possible tactics within an optimization horizon. The model minimizes total passenger travel times by improving, among others, transfer times and reducing deviations from the bus schedule. The methodology is tested on a case-study of the bus system of the city of Laval, Canada. A simulation framework is then developed, integrating real-time data on smart card transactions and bus locations, to verify the results of the optimization model. The number of offline optimizations which can be performed in between decisions is limited by the travel time between stops. We compare the performance of two online stochastic algorithms-Regret and Consensus.

  • 15h55 - 16h20

    Online optimization of the dial-and-ride problem with the integral primal simplex

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

    Transportation Network Companies such as Uber and Lyft have provided on-demand mobility services to cope with rising transportation demands. More recently, ridesharing has been introduced as a new option for customers using these services (e.g., UberPool, Lyft Shared) to decrease congestion, parking issues and pollution. However, these systems rarely use advanced optimization methods due to complex implementation and this limits their potential benefits. Developed algorithms for dial-and-ride problem (DARP) in dynamic mode often divide the time horizon into short periods and try to batch requests to take advantage of the static optimization. They restart the optimization for each new batch without using previous solutions. Our goal is to develop an algorithm for dynamic DARP that reuses previously computed solutions using the strengths of the integral primal simplex. In contrast to prior studies which consider fixed epochs to batch requests, we propose a re-optimization strategy which update the dispatching plan dynamically to expand the current routes with the new arrival requests. The performance of the algorithm is evaluated on large-size instances from the New York city Taxi and limousine dataset, and we compare the quality of results with prior studies in terms of the average waiting time of the passengers.

  • 16h20 - 16h45

    Stochastic and Robust Optimization of On-Demand Transport Systems Linked to Public Transport

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

    Traditional public transport systems provide efficient mass transportation solutions between fixed service points. By definition, these systems can only serve a fixed area. Consequently, passengers who request transportation services outside this region have reduced access to public transportation systems. On-demand transportation systems overcome this problem by offering shuttle services to serve passengers that face such restrictions. This study focuses on building optimization models to obtain cost-optimal solutions for on-demand transportation systems integrated with railway systems, where the fixed service point is defined as a specific train station. We develop robust solutions by ensuring a predefined level of feasibility over a scenario set that represents travel times. This can be done by implementing chance constrained programming to integrate scenario-based travel times into the model, which in return, builds robust and optimal solutions for a specific percentage of scenarios.

  • 16h45 - 17h10

    Location problems with decision-dependent demands

    • Warley Almeida Silva, prés., Université de Montréal
    • Margarida Carvalho, Université de Montréal
    • Sanjay Dominik Jena, Université du Québec à Montréal

    Location problems require decision makers to choose where to place one or more valuable resources temporarily or permanently while optimizing some performance measure. The literature typically refers to the valuable resource to be placed as “facility”, to the entity seeking service in a facility as “customer”, and to the quantity of service sought by a customer as “demand”. Several location problems of temporary facilities require taking decisions for a finite planning horizon, commonly discretized into time periods, and may present an interesting characteristic referred to as decision-dependent demand. One fundamental example is when customer demand replenishes at each time period and can only be absorbed once the customer is covered by a mobile facility, thus depending on previous decisions. This work studies location problems with this type of decision-dependent demands, which to the best of our knowledge represent a gap in the literature. In summary, we (i) show that some variants of this problem are NP-hard, (ii) propose a mixed-integer program to model relevant demand patterns over time, (iii) study the performance of the formulation through computational experiments for some sets of instances arising from practical applications, and (iv) derive insights regarding the structure of optimal solutions.