4 Presentations

• 
  10:30 AM - 10:55 AM

  Resource-Based Cycle Elimination Applied to the Vehicle Routing Problem

  • Claudio Contardo, presenter, GERAD - ESG UQÀM
  • Rafael Martinelli, Universidade Federal de Ouro Preto
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  In this talk we present a novel route relaxation for vehicle routing problems. It relies on the monotone consumption of a given resource along the edges used by a route, so as to forbid all cycles that are short according to the consumption of this resource. Preliminary computational experiments are presented to assess the performance of the new relaxation.

• 
  10:55 AM - 11:20 AM

  A Branch-and-Cut Algorithm for the Capacitated Single Allocation Hub Location-Routing Problem

  • Ha Minh Hoang, presenter, Polytechnique Montreal
  • Mi Zhang, École Centrale de Nantes
  • Nathalie Bostel, Université de Nantes
  • Pierre Dejax, École des Mines de Nantes

  The hub location-routing problem (HLRP) with less-than-truckload (LTL) shipments considers the location of hub facilities concentrating flows and through which flows are routed from origins to destinations, together with the design of both collection and delivery routes associated to each hub.The state of the art includes only very few works directly addressing the HLRP, and they mainly focus on particular cases as postal services. In this research, we address the HLRP with distinct collections and deliveries tours, as it is practiced by general goods freight carriers. We propose a new mathematical model for the capacitated single allocation hub location-routing problem (CASHLRP) and a branch-and-cut algorithm to solve exactly the problem.

• 
  11:20 AM - 11:45 AM

  Classification, Models and Exact Algorithms for Multi-Compartment Delivery Problems

  • Leandro C. Coelho, presenter, Université Laval
  • Gilbert Laporte, HEC Montréal

  The distribution of products using compartmentalized vehicles involves many decisions such as the allocation of products to vehicle compartments, vehicle routing and inventory control. These decisions often span several periods, yielding a difficult optimization problem. In this paper we define and compare four main categories of the Multi-Compartment Delivery Problem (MCDP). We propose two mixed-integer linear programming formulations for each case, as well as specialized models for particular versions of the problem. Known and new valid inequalities are introduced in all models.

• 
  11:45 AM - 12:10 PM

  Modeling and Solving the One-to-One Multi-Commodity Pickup and Delivery Traveling Salesman Problem

  • Luis Gouveia, presenter, University of Lisbon
  • Mario Ruthmair, Vienna University of Technology

  We address a traveling salesman problem variant with pickup and delivery aspects and propose several mixed integer programming models based on another equivalent problem formulation. Our branch-and-cut algorithms perform well on tightly constrained instances and solve several open TSPLIB instances for the sequential ordering problem.