4 Presentations

• 
  10:30 AM - 10:55 AM

  Constructive Heuristic for a Synchronized Arc Routing Problem (SyARP)

  • María Angélica Salazar-Aguilar, presenter, HEC Montréal
  • André Langevin, Polytechnique Montréal
  • Gilbert Laporte, HEC Montréal

  We propose a constructive heuristic for the SyARP. It consists of determining a set of routes for snow plowing operations. All streets, some of which have multiple lanes, must be plowed by using synchronized vehicles, and the objective is to minimize the time of the longest route.

• 
  10:55 AM - 11:20 AM

  A Branch-Price-and-Cut Algorithm for the Min-Max k-Vehicles Windy Rural Postman Problem

  • Guy Desaulniers, presenter, GERAD - Polytechnique Montréal
  • François Lessard, GERAD
  • Angel Corberan, Universidad de Valencia
  • Enrique Benavent, Universidad de Valencia
  • Isaac Plana, Universidad de Valencia
  • José M. Sanchis, Universidad Politécnica de València

  We present a branch-and-price algorithm for this arc routing problem that relies on ng-paths, three families of cutting planes and a dichotomic lower bounding procedure.

• 
  11:20 AM - 11:45 AM

  Improved Lower Bounds for the Capacitated Arc Routing Problem

  • Enrico Bartolini, presenter, HEC Montréal
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
  • Gilbert Laporte, HEC Montréal

  We present a cut-and-column generation bounding method for the CARP that is based on a set partitioning formulation, and uses a new dynamic programming method for generating elementary CARP routes. Extensive computational results show that the new bounds are tight, and permit to solve several open instances from the literature.

• 
  11:45 AM - 12:10 PM

  A General Variable Neighborhood Search for the One-Commodity Pickup-and-Delivery Travelling Salesman Problem

  • Nenad Mladenovic, presenter, Mathematical Institute SANU
  • Said Hanafi, Universite de Valenciennes et du Hainaut-Cambrésis
  • Aleksandar Ilic, University of Nis, Serbia
  • Dragan Urosevic, Mathematical Institute SANU

  We present Variable Neighborhood Search (VNS) approach for the one-commodity pickup-and-delivery traveling salesman problem. We adapt a collection of neighborhood structures usually used for solving classical TSP and efficiently update the data structures for feasibility checking in these neighborhoods. We improved all best-known objective values for the benchmark instances.