4 Presentations

• 
  03:30 PM - 03:55 PM

  The mixed capacitated general routing problem with time-dependent demands

  • Chahid Ahabchane, presenter, Polytechnique Montréal
  • Martin Trépanier, Polytechnique Montréal, CIRRELT
  • André Langevin, Polytechnique Montréal

  The Mixed Capacitated General Routing Problem (MCGRP) is defined over a mixed graph, for which some nodes, arcs and edges must be serviced. The problem consists of determining a minimum cost solution that satisfies the demand. Some problems like snow plowing or salt spreading have a time-dependent demand which was ignored in previous studies. This variation of demand is due to weather or traffic conditions. We present two models without graph transformation and another with graph transformation to node routing. We used CPLEX to solve small instances and we developed a Slack Induction by String Removal metaheuristic for large instances. The proposed model and metaheuristic were tested on problems derived from a set of classical instances of the MCGRP and CARP with some modifications.
• 
  03:55 PM - 04:20 PM

  The edge of time-dependent shortest path optimization in capacitated arc routing problems

  • Rafael Martinelli, presenter, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
  • Tuan Anh Pham, University of Engineering and Technology, Vietnam National University
  • Thibaut Vidal, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
  • Augusto Baffa, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
  • Minh Hoàng Hà, University of Engineering and Technology, National University Vietnam
  • Xuan Hoai Nguyen, IT R&D Center, Hanoi University

  We study time-dependent capacitated arc routing problems, and propose exact and heuristic solution methods. Our approaches use continuous quickest paths, calculated from historical traffic models at the network level. Through experiments on artificial and real datasets from Rio de Janeiro, we evaluate the benefits of time-dependent optimization in arc routing.
• 
  04:20 PM - 04:45 PM

  Ship routing with joint speed optimization

  • Gabriel Homsi, presenter, CIRRELT, University of Montreal
  • Rafael Martinelli, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
  • Thibaut Vidal, Pontifícia Universidade Católica do Rio de Janeiro

  We study a maritime pickup-and-delivery problem with joint ship speed optimization. We discuss techniques to reduce the computational effort required to optimize speed (a convex optimization problem). We use these techniques to efficiently optimize speed on every local search move evaluation of a metaheuristic. Our experiments show the methodology efficiency.

  KEYWORDS: Ship routing, speed optimization, metaheuristics
• 
  04:45 PM - 05:10 PM

  Mining frequent patterns to drive the exploration of high-order neighborhoods

  • Thibaut Vidal, presenter, Pontifical Catholic University of Rio de Janeiro
  • Florian Arnold, University of Antwerp
  • Ítalo Gomes Santana, Pontifical Catholic University of Rio de Janeiro
  • Kenneth Sörensen, University of Antwerp

  We use pattern mining to explore high-order neighborhoods in a local search. Each pattern, extracted from elite solutions, defines one move in which incompatible edges are disconnected, the pattern is inserted and the remaining route fragments are optimally reconnected. We report computational experiments and analyses on the capacitated vehicle routing problem.