Journées de l'optimisation 2014
Incluant une Journée industrielle de l'optimisation
HEC Montréal, 5  7 mai 2014
JOPT2014
HEC Montréal, 5 — 7 mai 2014
TD3 Tournées de véhicules 4 / Vehicle Routing 4
6 mai 2014 15h30 – 17h10
Salle: GérardParizeau
Présidée par Gunes Erdogan
4 présentations

15h30  15h55
A Tabu Search Algorithm for the Fleet Size and Mix Inventory Routing problem
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
The Cyclic Inventory Routing Problem (CIRP) is concerned with finding a cyclic schedule for the distribution of a single product to a number of salespoints. The problem involves multiple vehicles that can be dispatched several times during their shift. Each salespoint has a local inventory capacity, a constant consumption rate and stockouts are not allowed. The goal is to compose multiple trips which serve all salespoints 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 subproblems. For each subproblem, 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
We consider a Two Echelon Vehicle Routing Problem (2EVRP) 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
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.