Journées de l'optimisation 2016

HEC Montréal, Québec, Canada, 2 — 4 mai 2016

Horaire Auteurs Mon horaire

MB10 Vehicle Routing II

2 mai 2016 15h30 – 17h10

Salle: TD Assurance Meloche Monnex

Présidée par Juan Jose Salazar Gonzalez

4 présentations

  • 15h30 - 15h55

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

    • Khalid Amghar, prés., 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.

  • 15h55 - 16h20

    Undirected multi-depot rural postman problem

    • Jessica Rodríguez Pereira, prés., 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.

  • 16h20 - 16h45

    Goods distribution with electric vehicles: Integrating battery behaviour into routing

    • Samuel Pelletier, prés., 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.

  • 16h45 - 17h10

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

    • Adam Letchford, Lancaster University
    • Juan Jose Salazar Gonzalez, prés., 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