Séminaire “Un chercheur du GERAD vous parle!”

Enhancing General-Purpose Simulation-Based Optimization Algorithms Via Mixed Integer Linear Programming: A Case Study in Autonomous Ridesharing

12 octobre 2022 de 11h00 à 12h00

Claudia Bongiovanni – HEC Montréal, Canada

Séminaire en format hybride au local 4488 du GERAD ou Zoom.

Simulation-based optimization (SO) is a class of optimization techniques commonly used to address problems that occur within complex stochastic dynamics and for which the objective function and/or constraints cannot be evaluated analytically. One SO approach involves dynamically partitioning the search space into subspaces on which to focus simulation efforts. These subspaces are typically defined through generic partitioning rules, which have limited computational efficiency when dealing with large-scale discrete optimization problems. In this paper, we aim to improve the computational efficiency of generic SO algorithms by employing problem-specific partitioning rules from the mixed integer linear programming (MILP) literature. We illustrate our approach on an autonomous ridesharing problem in which service level costs (e.g., number of requests served, excess user travel time, maximum travel time, and time window violation costs) are directly affected by unpredictable changes in the environment (e.g., traffic congestion, demand, fleet size).

*co-authored with Carolina Osorio and Jean-François Cordeau