Journées de l'optimisation 2014

                             Incluant une Journée industrielle de l'optimisation

                                              HEC Montréal, 5 - 7 mai 2014


HEC Montréal, 5 — 7 mai 2014

Horaire Auteurs Mon horaire

TD3 Tournées de véhicules 4 / Vehicle Routing 4

6 mai 2014 15h30 – 17h10

Salle: Gérard-Parizeau

Présidée par Gunes Erdogan

4 présentations

  • 15h30 - 15h55

    A Tabu Search Algorithm for the Fleet Size and Mix Inventory Routing problem

    • Haihong Xiao, prés., HEC-Paris
    • Soumia Ichoua, Embry-Riddle Aeronautical University
    • Laoucine Kerbache, HEC-Paris

    A heuristic algorithm based on tabu search has been proposed to solve the fleet size and mix IRP, consisting of define the frequency and quantity of delivery to each customer, the number of vehicles, and the routing of each vehicle. Satisfactory results have been produced for a set of test problems used in the literature

  • 15h55 - 16h20

    A Heuristic for the Cyclic Inventory Routing Problem

    • Masoud Chitsaz, prés., University of Leuven
    • Ali Divsalar, University of Leuven
    • Pieter Vansteenwegen, University of Leuven

    The Cyclic Inventory Routing Problem (CIRP) is concerned with finding a cyclic schedule for the distribution of a single product to a number of sales-points. The problem involves multiple vehicles that can be dispatched several times during their shift. Each sales-point has a local inventory capacity, a constant consumption rate and stock-outs are not allowed. The goal is to compose multiple trips which serve all sales-points and minimize the combination of transportation, inventory and vehicle costs, in a cyclic distribution pattern. Each trip can have a different frequency in the vehicle schedule. This is an important aspect that makes this so called Cyclic Inventory Routing Problem (CIRP) more complex than other Inventory Routing Problems.

    Our solution approach decomposes the problem into two different but related sub-problems. For each sub-problem, we propose a new heuristic. Our first heuristic composes trips based on cost estimations for node transfers between trips. The second algorithm tries to combine these trips in an acceptable cyclic schedule. In order to search the feasible area efficiently, three diversification moves are designed. Also a new type of “hash function” is used to prevent searching the same part of the solution space repeatedly. The proposed algorithm is capable of finding high quality solutions in a reasonable time, especially for large instances. Applying the algorithm on 320 available benchmark instances, for more than half of them, the best known solution is improved. The results show, on average, a 2.5% improvement in the objective function value compare to the best known results in the literature.

  • 16h20 - 16h45

    An Adaptive Large Neighborhood Search for a Two Echelon Vehicle Routing Problem Arising in City Logistics

    • Philippe Grangier, prés., JDA Software
    • Michel Gendreau, Polytechnique Montréal
    • Louis-Martin Rousseau, Polytechnique Montréal
    • Fabien Lehuédé, École des Mines de Nantes

    We consider a Two Echelon Vehicle Routing Problem (2E-VRP) which integrates constraints arising in City Logistics such as: time windows, synchronization, and multiple trips for some vehicles. We have developped an ALNS that benefits both from custom ruin and recreate heuristics and an efficient feasibility check.

  • 16h45 - 17h10

    An Exact Algorithm for the One Commodity Pickup and Delivery Traveling Salesman Problem with Multiple Visits

    • Gunes Erdogan, prés., University of Southampton
    • Maria Battarra, University of Southampton
    • Roberto Wolfler Calvo, Université Paris 13

    Shared Bicycle Systems are becoming increasingly popular. The problem of rebalancing stations is of particular interest. Although the Static Rebalancing Problem with Multiple Visits has been studied (Chemla, Meunier, Wolfler Calvo 2013), no exact solution algorithms have been proposed. This paper provides the first exact solution algorithm for the Static Bicycle Rebalancing Problem with Multiple Visits. The algorithm is based on solving a relaxed formulation of the problem, checking for feasibility of incumbents through an implicit enumeration scheme, and adding combinatorial Benders cuts to rule out infeasible solutions. Computational results for benchmark instances are provided.