Journées de l'optimisation 2022
HEC Montréal, Québec, Canada, 16 — 18 mai 2022
TA10 - Simulation
17 mai 2022 10h30 – 12h10
Salle: Banque Scotia (bleu)
Présidée par Claudia Bongiovanni
3 présentations
-
10h30 - 10h55
A Simulation Framework for Bilevel Programs Based on Advanced Discrete Choice Models
Many bilevel problems require the use of flexible discrete choice models, such as the mixed multinomial logit model, to faithfully represent the followers’ behavior. However, the resulting mathematical programs are in many cases challenging mixed-integer non-linear problems that can only be solved in reasonable time for a limited number of sampled followers, which can lead to severely suboptimal solutions.
To alleviate this issue, we present a general simulation framework in which a set of realizations of the random utility terms are sampled for each simulated follower. Our approach, which is applicable to a wide class of bilevel problems, integrates a clustering phase that reduces the number of followers at the cost of little or no loss of accuracy.
We also introduce an entropy measure that allows us to quantify the level of randomness of the follower’s behavior. We explain how this information-theoretic perspective can help to determine whether a simulation-based method has the potential to improve the state-of-the-art algorithms for a given application.
Finally, we illustrate the computational performance of our resolution framework by applying it to the competitive facility location problem. In the light of these results, we propose future uses for our entropy-based characterization of stochastic bilevel programs.
-
10h55 - 11h20
Enhancing general-purpose simulation-based optimization algorithms via mixed integer linear programming: A case study in autonomous ridesharing
We address an autonomous ridesharing problem in which a set of capacitated vehicles must provide service to a set of known demands within a planning horizon. The goal is to route and schedule vehicles in such a way that operational and service level costs are minimized. However, in this work we assume that service level costs (e.g., user excess travel time, waiting time, and time window violation costs) are directly affected by unpredictable variations in link travel times within the transportation network.
Simulation-based optimization (SO) is commonly used to address optimization problems within stochastic and intricate dynamics. However, their use for discrete problems is often limited to low-dimensional problems. In this work we aim to enhance the scalability and compute efficiency of general-purpose SO algorithms for discrete problems by embedding partitioning and local branching ideas from the analytical deterministic mixed integer linear programming (MILP) literature. We illustrate our approach using a MILP formulation for an autonomous dial-a-ride problem. -
11h20 - 11h45
Simulation-based optimization of pump scheduling for drinking water distribution systems
Efficient Water Distribution Systems (WDSs) are crucial for modern society. Their operation requires large amounts of energy with significant financial impact for the utility providers. Existing solution methods are often oversimplified and can only solve the problem for very small, schematic networks. This article studies a pumping scheduling problem for WDSs in which, besides scheduling the operation of pumps over a planning horizon, several constraints regarding hydraulic properties are considered. The goal is to provide a pumping plan of minimum cost that satisfies all demand and respects operational and hydraulic constraints. This work proposes a nonlinear and non-convex formulation as well as a high-performance heuristic. The physical hydraulic behaviour is ensured via hydraulic simulation software. The present method significantly improved the best solutions for several benchmark instances by up to 17%. The solutions also reduce the energy consumed during peak periods, when the electrical grid is most strained.