|Séminaire conjoint CRT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport
TITRE : Trucks in Movement: Hybridization of Exact Approaches and Variable Neighborhood Search for the Delivery of Ready-Mixed Concrete
CONFÉRENCIÈRE : Verena Schmid, University of Vienna, Austria
DATE et ENDROIT : 11 février, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Michel Gendreau (514-343-7435)
RÉSUMÉ : Companies in the concrete industry are facing the following scheduling problem on a daily basis: concrete produced at several plants has to be delivered at customers’ construction sites using a heterogeneous fleet of vehicles in a timely, but cost-effective manner. As the ordered quantity of concrete typically exceeds the capacity of a single vehicle several deliveries need to be scheduled to fulfill an order. The deliveries cannot overlap and the time between consecutive deliveries has to be small. We have developed a broad range of different ways on how to solve the problem stated above. Various solution methods based on exact, heuristic, meta-heuristic and hybrid approaches have been developed. Exact methods based on a formulation the so called VRP* (a Split Delivery Multi Depot Heterogeneous Vehicle Routing Problem with Time Windows) have been implemented. The resulting problem formulation can be solved to optimality for very small instances. For real-world-sized instances however, even with a steady increase in computational power, just to ‘to MIP’ is not the way to success. Hence an algorithm, which controls the solution process of the embedded MIP-formulation, has been developed in order to tackler larger problem instances. This integrative hybrid approach is based on Local Branching (LB) which itself is guided by means of Variable Neighborhood Search (VNS). Attention has also been paid to the development of valid inequalities and cuts in order to improve the quality of lower bounds. Another approach has been developed, which is based on a multi-commodity network flow model (MCNF) formulation. Rather than having a comprehensive view on the problem only subparts are considered and solved to optimality…. So called patterns (options on how orders could be satisfied) are generated heuristically and serve as an input for the MCNF. Given on a set of input pattern it is possible to solve the problem to optimality. Moreover the entire problem can be tackled by just using VNS on its own. The best results where obtained when combining the two approaches based on MCNF and VNS. Both methods used solely are capable of solving such problems. However, only the cooperative hybrid approach enables us to combine the strengths of both techniques and to compensate for their major drawbacks. Iteratively solutions obtained by MCNF serve as input for VNS which is going to (locally) optimize it. The resulting solution (in terms of pattern) is fed back into the MCNF problem, which is going to be optimized again. It can be shown that both hybrid approaches and the embedded combination of two methods are by far more efficient then the use of any approach solely. Additionally we compare our algorithm to a software available in Austria, which is based on Simulated Annealing (SA). Our hybrid algorithms outperform results obtained by the commercial product.
Verena Schmid, University of Vienna, “Trucks in Movement: Hybridization of Exact Approaches and Variable Neighborhood Search for the Delivery of Ready-Mixed Concrete”, 11 février 2009