15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

Horaire Auteurs Mon horaire

Bilevel optimization II

12 juil. 2017 11h30 – 12h45

Salle: PWC

Présidée par Patrice Marcotte

3 présentations

  • 11h30 - 11h55

    Fare Evasion in Transit Networks

    • Tobias Harks, prés., Augsburg University

    Fare evasion in public transit systems causes significant losses to society. In order to decrease evasion rates and minimize these losses, transportation companies conduct on-board inspections to check traveling passengers for a valid ticket. In this talk, we will discuss several variants of a new model for optimizing the distribution of fare inspections within the network.

    The model is based on a bilevel program, where in the first level, the leader (the network operator) determines probabilities for inspecting passengers at different locations, while in the second level, the followers (the fare-evading passengers) respond by optimizing their routes for given inspection probabilities and travel times. We present exact, approximate, and heuristic algorithms for the followers' and the leader's problem. We also prove a tight bound on the ratio of the optimal cost between an adaptive and a non-adaptive version of the followers' behavior. Finally, we present the results of an extensive computational study on instances of the Dutch railway and the Amsterdam subway network, showing that our solutions are within 95% of upper bounds derived from an LP relaxation.

    This is joint work with José R. Correa, Vincent J.C. Kreuzen and Jannik Matuschke.

  • 11h55 - 12h20

    A Two-Level Optimization Model for Improved Energy Conservation Decision-Making

    • Steven A. Gabriel, prés., Department of Civil and Environmental Engineering, University of Maryland
    • Bill Champion, University of Maryland/EMG

    We present a recent two-level optimization problem related to more efficient implementation of energy conservation measures. At the top level is the government agency that must decide on which energy projects it must do on its own. At the bottom level is the set of competing energy conservation outsourcing companies. We present a novel formulation and numerical results to show the value added in this approach.

  • 12h20 - 12h45

    A bilevel location model involving competition and queueing

    • Patrice Marcotte, prés., Université de Montréal
    • Teodora Dan, DIRO, Université de Montréal

    We consider a competitive environment in which users patronize the facility minimizing the sum of travel time, queueing delay, and a random term. This situation can be modeled as a bilevel program that involves discrete and continuous variables, as well as linear and nonlinear functions. We design for its solution an approximation algorithm that provides asymptotically optimal solutions, as well as heuristics that exploit the very structure of the problem.