2018 Optimization Days

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

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

MA8 Node and arc routing

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

Location: Metro inc. (72)

Chaired by Frédéric Semet

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:30 AM - 10:55 AM

    The clustered target-visitation arc-routing problem

    • Jessica Rodríguez Pereira, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:55 AM - 11:20 AM

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

    • Hani Zbib, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:20 AM - 11:45 AM

    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, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:45 AM - 12:10 PM

    An adaptive large neighborhood search for multicommodity VRP

    • Frédéric Semet, presenter, É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.