GRASP and Multiple Neighborhood Search for real vehicle routing problem

International audienceFor a few decades vehicle routing problems have been studied and improved, it includes today many features under the common denomination of rich vehicle routing problems. In our study, multiple types of vehicles are considered, including fixed cost, variable cost, velocity and capacity. The topology of these instances includes restrictions on the graph for some types of vehicles. Instances based on real road maps take into account some specificity like asymmetric graph, triangular inequality not respected, forbidden turns depending on crossroad and congestion information that impact the solving methods. Very large scale instances with thousands of customers are solved using a GRASP and a multiple neighborhood search method to obtain high quality solutions in reasonable execution time. The GRASP is based on the so-called Clarke and Wright heuristic and the multiple neighborhood search method presents an unified view of several classical neighborhoods. The solution method has been particularly improved to handle the very large scale instances