Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

TD2 Tournées de véhicules 4 / Vehicle Routing 4

8 mai 2012 15h30 – 17h10

Salle: KPMG

Présidée par Gilbert Laporte

4 présentations

  • 15h30 - 15h55

    Consistency in Multi-Vehicle Inventory-Routing

    • Leandro C. Coelho, prés., Université Laval
    • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
    • Gilbert Laporte, HEC Montréal

    Inventory-routing problems (IRPs) arise in vendor-managed inventory systems. They require jointly solving a vehicle routing and an inventory management problem. We introduce the concept of consistency in IRP solutions, analyzing the effect of different inventory policies, routing decisions and delivery sizes, thus increasing quality of service. We evaluate their managerial and cost implications when enforcing them in IRP solutions.

  • 15h55 - 16h20

    A Branch-Price-and-Cut Algorithm for the Workover Rig Routing Problem

    • Guy Desaulniers, prés., GERAD - Polytechnique Montréal
    • Jacques Desrosiers, GERAD, HEC Montréal
    • Glaydston Ribeiro, Federal University of Espirito Santo

    In an onshore oil field, the productivity of oil wells decreases when they require maintenance. To restore full productivity at a well, it must be visited by a specially-equipped vehicle, called a workover rig. Given a set of wells needing maintenance and a heterogeneous fleet of workover rigs, the workover rig routing problem (WRRP) consists of finding rig routes that minimize the total production loss of the wells over a finite horizon. The wells have different loss rates, require various services, and may not be serviced within the horizon due to rig availability. The rigs have initial positions and do not have the same equipment. This paper presents the first exact algorithm for the WRRP, namely, a branch-price-and-cut algorithm that relies on some of the most recent techniques introduced for the vehicle routing problem with time windows. Our computational experiments show that this exact algorithm can solve practical-sized instances in reasonable computational times.

  • 16h20 - 16h45

    Formulations and Branch-and-Cut Algorithms for Multi-Vehicle Production and Inventory Routing Problems

    • Yossiri Adulyasak, prés., HEC Montréal
    • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
    • Raf Jans, HEC Montréal

    The inventory routing problem (IRP) and the production routing problem (PRP) are two difficult problems arising in the planning of integrated supply chains. In this paper, we introduce formulations, with and without a vehicle index, to solve the multi-vehicle IRP and PRP which are often neglected due to its complexity.

  • 16h45 - 17h10

    The Undirected m-Capacitated Peripatetic Salesman Problem

    • Eric Duchenne, prés., Université de Valenciennes et du Hainaut-Cambrésis
    • Gilbert Laporte, HEC Montréal
    • Frédéric Semet, École Centrale de Lille

    In the m-Capacitated Peripatetic Salesman Problem (m-CPSP) the aim is to determine m Hamiltonian cycles of minimal total cost on a graph, such that all the edges are traversed less than the value of their capacity. In this presentation, we introduce three formulations, two branch-and-cut algorithms and one branch-and-price algorithm for the m-CPSP. Tests indicate that the branch-and-price algorithm can solve instances with more than twice the size of what is achievable with the branch-and-cut algorithms.