4 Presentations

• 
  03:30 PM - 03:55 PM

  A GVNS heuristic for the traveling salesman problem with time windows - minimizing completion time

  • Khalid Amghar, presenter, Université de Montréal
  • Bernard Gendron, Université de Montréal, CIRRELT
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT

  We use a GVNS (General Variable neighborhood search) heuristic for the traveling salesman problem with time windows where the objective is to minimize the completion time. We use efficient methods for checking the feasibility and the profitability of a movement, and for exploring the neighborhoods. The results indicate that our method is very competitive with the state-of-the-art.

• 
  03:55 PM - 04:20 PM

  Undirected multi-depot rural postman problem

  • Jessica Rodríguez Pereira, presenter, HEC Montréal
  • Elena Fernandez, Universitat Politècnica de Catalunya
  • Gilbert Laporte, HEC Montréal

  This work studies an extension of Rural Postman Problem, where there are several depots, instead of one, from which route must be satisfy the demand, located at the edges of an undirected graph. Optimality conditions of solutions are studied, two linear integer formulations are proposed and some results are presented.

• 
  04:20 PM - 04:45 PM

  Goods distribution with electric vehicles: Integrating battery behaviour into routing

  • Samuel Pelletier, presenter, HEC Montréal
  • Gilbert Laporte, HEC Montréal
  • Ola Jabali, HEC Montréal

  We introduce an electric vehicle routing problem in which a fleet of battery electric vehicles must deliver goods to a set of customers over the course of a week. The charging schedule at the depot must be determined such as to allow vehicles to complete their routes, and the battery is modeled as an equivalent electrical circuit. The objective is to minimize the sum of all energy and routing costs over the planning horizon.

• 
  04:45 PM - 05:10 PM

  Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem

  • Adam Letchford, Lancaster University
  • Juan Jose Salazar Gonzalez, presenter, Universidad de La Laguna

  The sequential ordering problem (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernandez & Salazar introduced a multi-commodity flow (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables and adding valid equations. We then use polyhedral projection, together with some known results on flows, cuts and metrics, to derive new families of strong valid inequalities for both problems. Finally, we give computational results, which show that our findings yield good lower bounds in practice. This talk is based on a recent publication in EJOR (2016) doi:10.1016/j.ejor.2015.11.001