Enhancing General-Purpose Simulation-Based Optimization Algorithms Via Mixed Integer Linear Programming: A Case Study in Autonomous Ridesharing
Claudia Bongiovanni – HEC Montréal, Canada
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
Campus de l'Université de Montréal
2920, chemin de la Tour
Montréal Québec H3T 1J4