2018 Optimization Days

HEC Montréal, Québec, Canada, 7 — 9 May 2018

Schedule Authors My Schedule

TA8 Facility location

May 8, 2018 10:30 AM – 12:10 PM

Location: Metro inc. (72)

Chaired by Claudio Contardo

4 Presentations

  • 10:30 AM - 10:55 AM

    A scalable exact algorithm for the vertex p-center problem

    • Claudio Contardo, presenter, GERAD - ESG UQÀM
    • Raphael Kramer, Università degli studi di Modena e Reggio Emilia (UNIMORE - Italy)
    • Manuel Iori, Università degli Studi di Modena e Reggio Emilia

    We present a scalable relaxation algorithm for the vertex p-center problem. Our algorithm can handle to proven optimality problems derived from the TSP library containing up to 1 million nodes, this is roughly 200 times larger than the state-of-the-art solvers for this problem

  • 10:55 AM - 11:20 AM

    Revenue management in hub location problems

    • Gita Taherkhani, presenter, University of Waterloo
    • Sibel Alumur Alev, University of Waterloo
    • Seyed Mojtaba Hosseini, University of California Irvine

    We consider one of the basic and classical revenue management model known as capacity-control discount fares within the hub location problem and develop a deterministic formulation of this problem. We further extend this model considering uncertainty associated with demand and revenues and develop a stochastic minmax regret formulation. Two exact algorithms based on a Benders reformulation are proposed to solve large-size instances of the problem.

  • 11:20 AM - 11:45 AM

    Hub location problem under the risk of interdiction

    • Prasanna Ramamoorthy, presenter, Indian Institute of Management Ahmedabad
    • Sachin Jayaswal, Indian Institute of Management Ahmedabad
    • Ankur Sinha, Indian Institute of Management Ahmedabad
    • Navneet Vidyarthi, Concordia University

    In this paper, we study hub location problem under the risk of interdiction (HLPI). We present several formulations of the problem and compare them theoretically and computationally.
    We further develop an efficient cutting plane algorithm to solve the problem.

  • 11:45 AM - 12:10 PM

    Dynamic facility location problems with stochastic demands and congestion

    • Masoud Madani, presenter, Concordia university
    • Ivan Contreras, Concordia University
    • Navneet Vidyarthi, Concordia University

    In this thesis, we study a multi-periodic facility location problem with stochastic demand to determine the optimal location, capacity selection and demands allocation of facilities within distinct time periods, while, each facility contains a server with a limited capacity. It causes facilities to experience a period of congestion, when not all arriving demands can be served immediately. Customers that arrive in this period might await service in a queue. This thesis perspective incorporates customers waiting costs as part of the objective. In this case, facilities do not utilize whole of the established capacity to ensure a maximum waiting time of the allocated customers. Firstly, a mathematical model is presented for a dynamic facility location problem with stochastic demand and congestion. The problem is setup as a network of spatially distributed queues and formulated as a nonlinear mixed integer program (MINLP). To transform the nonlinear congestion function to a piecewise linear, a linearization method is adapted. This method adds a set of inequalities to the model. We show that lifting this set of inequalities, with keeping generality of the method, reduces CPU times up to 3.5 times, on average. Moreover, a decent heuristic is proposed to solve the problem. Computational experiments indicate that the heuristic results in less costly solutions than them obtained by CPLEX algorithms, in 58% of relatively-difficult test problems.