Journée du GT Transport et Logistique
Paris le 14/06/2011
à l'Institut Henri Poincaré de l'Université Paris 611 rue Pierre et Marie Curie 75231 Paris CEDEX 05
Résumés
"New route relaxation and pricing strategies for solving different variants of the vehicle routing problem."
Roberto Roberti
DEIS, University of Bologna, Italy, robeto.roberti6 at unibo.it
In this talk, we describe an effective exact method for solving both the Capacitated Vehicle Routing Problem (CVRP) and the Vehicle Routing Problem with Time Windows (VRPTW). The proposed algorithm is based on the Set Partitioning (SP) formulation of the problem. We introduce a new route relaxation, called ng-route, used by different dual ascent heuristics to find near-optimal dual solutions of the LP-relaxation of the SP model. We describe a column-and-cut generation algorithm strengthened by valid inequalities that uses a new strategy for solving the pricing problem. The new ng-route relaxation and the different dual solutions achieved allow us to generate a reduced SP problem containing all routes of any optimal solution that is finally solved by an integer programming solver. The proposed method solves 4 of the 5 open Solomon's VRPTW instances and significantly improves the running times of state-of-the-art algorithms for both VRPTW and CVRP. We describe how this solution method has been recently extended to derive exact algorithms for the Period CVRP and the Pickup and Delivery problem with time windows.
"Shift design and scheduling problems of transport activities in a hospital environment"
Virgine André
Université Blaise Pascal, Clermont-Ferrand
This study, proposed by the university hospital of Clermont-Ferrand, concerns the organization of the transports of meals, linen and drugs between production sites and consumption sites. We consider two kinds of activity: the delivery of clean container and the pick-up of dirty container. Each activity requires many resources: a container, a driver, a vehicle, a loading bay, an unloading bay, a production line or a cleaning area according to its type. Many of these resources have a timetable: the drivers, the production lines and the cleaning areas. Moreover, activities are subject to precedence constraints, release dates and due dates. The problem consists in the determination of the number of drivers and their own timetable and in the assignment and the scheduling of the activities to each driver with the objective to realize all the activities with no lateness and no overtime. To solve this problem, we propose an approach based on the combination of a mathematical model, a simulation model and a metaheuristic. We apply this proposition to real instances proposed by the hospital.
"Un algorithme génétique hybride à gestion adaptative de diversité pour le problème de tournées de véhicules et ses variantes."
Thibaut Vidal
UTT et CIRRELT
In this talk, a general algorithmic framework is presented, that successfully addresses a wide range of vehicle routing problem (VRP) variants. The proposed meta-heuristic combines the exploration capacities of population-based evolutionary search, with fast local-search based improvement procedures, and a new efficient population-diversity management scheme. This adaptive diversity management procedure impacts the very evaluation of individuals, now driven by fitness as well as innovation measures in the context of the population. Extensive computational experiments show that the method performs impressively, both in terms of computational efficiency and solution quality, on classical benchmarks for the capacitated VRP, the periodic VRP, the multi-depot VRP and their combinations, with eventual time-windows and constrained route duration.
"Règulation dynamique des systémes de transport en libre-service "
Daniel Chemla
LIPN et CERMICS
Schématiquement, un système de transport en libre service se régule en temps réel soit avec une flotte de camions qui déplacent les vélos afin de satisfaire au mieux la demande, soit avec une tarification dynamique qui incite les usagers à changer leur destination. L'objectif de cet exposé est de formaliser ces diffrents modes de régulation, de présenter un simulateur permettant de les expérimenter et de comparer leurs performances en utilisant divers indicateurs.
"Recherche locale haute performance pour la résolution d'un problème riche de tournées d'inventaires"
Frédéric Gardi
Bouygues e-lab, France
In this talk, a new practical solution approach based on randomized local search is presented for tackling a real-life inventory routing problem. Inventory routing refers to the optimization of transportation costs for the replenishment of customers' inventories: based on consumption forecasts, the vendor organizes delivery routes. Our model takes into account pickups, time windows, drivers' safety regulations, orders and many other real-life constraints. This generalization of the vehicle routing problem was often handled in two stages in the past: inventory first, routing second. On the contrary, a characteristic of our local-search approach is the absence of decomposition, made possible by a fast volume assignment algorithm. Moreover, thanks to a large variety of randomized neighborhoods, a simple first-improvement descent is used instead of tuned, complex metaheuristics. The problem being solved every day with a rolling horizon, the short-term objective needs to be carefully designed in order to ensure long-term savings. To achieve this goal we propose a new surrogate objective function for the short-term model, based on long-term lower bounds. An extensive computational study shows that our solution is effective, efficient and robust, providing long-term savings exceeding 20 % on average compared to solutions built by expert planners or even a classical urgency-based constructive algorithm. Confirming the promised gains in operations, the resulting decision support system is progressively deployed worldwide.
"Route optimization of trucks for the building sector"
Sylvain Rosembly
Univ. Nantes, Master ORO
We are dealing with a routing problem for the building sector. A fleet of trucks has to move raw material from quarries and storage platforms to building sites, and from building sites to dumps or other sites. The problem bears resemblance to the pickup-and-delivery problem, with some specific constraints: a vehicle can ship only one material type at a time, from a pickup point to a delivery point. Demands are usually greater than vehicle capacities and consequently require several visits. After having described the problem and a possible model, we will present a two-phase heuristic resolution method.
"An exact resolution of the d-dimensional Orthogonal Packing Problem with order constraints."
Djamal Mohia
CERMICS
In this work, we deal with a particular version of the d-Orthogonal Packing Problem. We recall that the OPP is the decision problem on whether a set V of d dimensional boxes fits into a d dimensional container C. In our case, we consider the situation in which boxes are neither necessarily packed at the same time (pick-up time), nor unpacked at the same time (delivery time). An instance of the considered problem in hence a collection of boxes, each one with pick-up and delivery instants. An instance of our problem is feasible if the following constraints are satisfied : 1) Every box is moved according to a unique direction, so called pick-up / delivery direction. 2) Boxes can only be moved when picked-up or delivered. Fekete and Schepers proposed a characterisation of a feasible OPP instance in terms of d particular graphs satisfying a list of properties. This aims to give an exact method for solving instances of reasonable size in a reasonable time. We show in our work that a similar characterization exits for our problem.This allows us to establish an enumeration scheme providing an exact solution to a given instance of our problem by enriching the enumeration method used by Fekete and Schepers to solve the classical OPP. This enrichment allows us to deduce some interesting necessary conditions for the feasibility of an instance of our problem.