Journées de l'optimisation 2018

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

Horaire Auteurs Mon horaire

MB8 Location and routing

7 mai 2018 15h30 – 17h10

Salle: Metro inc. (72)

Présidée par Luis Gouveia

4 présentations

  • 15h30 - 15h55

    Modeling a multi-attribute two-echelon location-routing problem with facility synchronization

    • David Escobar Vargas, prés., CIRRELT
    • Claudio Contardo, GERAD - ESG UQÀM
    • Teodor Gabriel Crainic, Université du Québec à Montréal

    We study a multi-attribute two-echelon location-routing problem with synchronization constraints. Overall, the problem definition involves both strategic and tactical planning to minimize distribution-related costs in urban logistics. We propose a decomposition scheme to decouple echelons and discretize time constraints while maintaining the link of the demand flow between each echelon.

  • 15h55 - 16h20

    Flexible two-echelon location routing

    • Maryam Darvish, prés., Université Laval
    • Claudia Archetti, University of Brescia
    • Leandro C. Coelho, Université Laval
    • Grazia Speranza, University of Brescia

    In this talk, we consider an integrated routing problem in which a supplier delivers a commodity to its customers through a two-echelon supply network. Before being sent to the final customers, the commodities are first to be sent to a set of available of distribution centers (DCs). We consider a limited planning horizon over which the total cost consisting of the sum of the shipping costs from the depot to the DCs, the traveling costs from DCs to customers, the location costs, and the penalty costs for any unmet demand, needs to be minimized. On top of this basic setting, we study two sources of flexibility: flexibility in due dates and flexibility in the network design. The former establishes an interval within which the customer requests can be satisfied while the latter is related to the possibility of deciding which DCs are convenient to be rented at each period of the planning horizon. We present a mathematical formulation of the problem together with different classes of valid inequalities. We solve the problem with both exact and approximate methods. Extensive computational tests are made on randomly generated instances to show the value of the two kinds of flexibility. We will also discuss computational and business insights.

  • 16h20 - 16h45

    Median and covering location problems with interconnected facilities

    • Marilène Cherkesly, prés., ESG UQÀM
    • Gilbert Laporte, HEC Montréal
    • Mercedes Landete, Universidad Miguel Hernández de Elche

    We introduce two classes of location problems with interconnected facilities, i.e., facilities must be located within a prescribed distance of each other. The problems are modeled through several formulations.
    A greedy randomized adaptive search procedure (GRASP) is developed. Extensive tests are performed to assess the performance of the GRASP.

  • 16h45 - 17h10

    A new formulation for the Hamiltonian p-median problem

    • Luis Gouveia, prés., University of Lisbon
    • Tolga Bektas, University of Southampton
    • Daniel Santos, University of Lisboa, DEIO, CMAFCIO

    This talk concerns the Hamiltonian p-median problem defined on a directed graph, which consists of finding p mutually disjoint circuits of minimum total cost, such that each node of the graph is included in one of the circuits. Earlier formulations are based on viewing the problem as resulting from the intersection of two subproblems. The first subproblem states that at most p circuits are required, that are usually modeled by using subtour elimination constraints known from the traveling salesman problem. The second subproblem states that at least p circuits are required, for which this paper makes an explicit connection to the so-called path elimination constraints that arise in multi-depot/location-routing problems. A new extended formulation is proposed that builds on this connection, that allows the derivation of a stronger set of subtour elimination constraints for the first subproblem, and implies a stronger set of path elimination constraints for the second subproblem. The paper describes separation routines for the two sets of constraints that are used in a branch-and-cut algorithm to solve asymmetric instances with up to 150 nodes and symmetric instances with up to 100 nodes using the new formulation.