Journées de l'optimisation 2018

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

Horaire Auteurs Mon horaire

MA8 Node and arc routing

7 mai 2018 10h30 – 12h10

Salle: Metro inc. (72)

Présidée par Frédéric Semet

4 présentations

  • 10h30 - 10h55

    The clustered target-visitation arc-routing problem

    • Jessica Rodríguez Pereira, prés., HEC Montréal
    • Elena Fernandez, Universitat Politècnica de Catalunya
    • Gilbert Laporte, HEC Montréal
    • Gerhard Reinelt, Universität Heidelberg

    Target Visitation problems combine Linear Ordering and Vehicle Routing. There exist profits (targets) associated with the order of demand service, as well as costs on routes. We study the case of demand located at some edges and it is imposed that all demand edges in a component are served consecutively.

  • 10h55 - 11h20

    Clustering techniques for very-large scale arc routing problems in curbside waste collection

    • Hani Zbib, prés., Cluster for Operations Research and logistics, Department of Economics and Business Economics, Aarhus University
    • Sanne Wøhlk, Cluster for Operations Research and logistics, Department of Economics and Business Economics, Aarhus University

    We present novel clustering techniques for very-large scale real-life instances of multi-compartment capacitated arc routing problems in curbside waste collection. The aim of the clustering is to reduce the graph sizes considerably to sizes that are computationally tractable, and subsequently solve them using the Multi-Move Chain Descent algorithm.

  • 11h20 - 11h45

    The open vehicle routing problem with decoupling points

    • Reza Atefi, Ferdowsi University of Mashhad, Iran
    • Majid Salari, Ferdowsi University of Mashhad, Iran
    • Leandro C. Coelho, Université Laval
    • Jacques Renaud, prés., Université Laval, CIRRELT

    This practical problem is faced by companies dealing with carriers to ship their goods over large territories. In this case it may be profitable to use more than one carrier to perform a specific expedition: the first one leaves the depot and performs part of the deliveries, drops off all remaining load, and the second carrier continues from that point onwards. We model this problem using a realistic multi-drop less-than-truckload cost function composed of a non-linear transportation cost, a detour cost and a drop cost. We have developed a tailored Iterated Local Search (ILS) algorithm which handles the special features of the problem. The efficiency of the ILS was demonstrated by obtaining all best known solutions on a set of classical OVRP instances and improving it for one instance. Then, using real orders and transportation costs obtained from industrial partners, we clearly show the benefit of using decoupling points to optimize transportation costs.

  • 11h45 - 12h10

    An adaptive large neighborhood search for multicommodity VRP

    • Frédéric Semet, prés., École Centrale de Lille
    • Diego Cattaruzza, Centrale Lille - CRIStAL
    • Wenjuan Gu, Centrale Lille - CRIStAL
    • Maxime Ogier, Centrale Lille - CRIStAL

    In this work we study a vehicle routing problem where customers request multiple commodities. We allow to split the delivery to a customer but force each commodity to be delivered at once. We propose an adaptive large neighborhood search to solve this problem. Problem-defined local search operators based on the resolution of MIPs are developped. Results show that the method is able to obtain near optimal solutions for large instances.