A hybrid evolutionary local search with depth first search split procedure for the heterogeneous vehicle routing problems

摘要

Routing Problems have been deeply studied over the last decades. Split procedures have proved their efficiency for those problems, especially within global optimization frameworks. The purpose is to build a feasible routing solution by splitting a giant tour into trips. This is done by computing a shortest path on an auxiliary graph built from the giant tour. One of the latest advances consists in handling extra resource constraints through the generation of labels on the nodes of the auxiliary graph. Lately, the development of a new generic split family based on a Depth First Search (DFS) approach during label generation has highlighted the efficiency of this new method for the routing problems, through extensive numerical evaluations on the location-routing problem. In this paper, we present a hybrid Evolutionary Local Search (hybrid ELS) for non-homogeneous fleet Vehicle Routing Problems (VRP) based on the application of split strategies. Experiments show our method is able to handle all known benchmarks, from Vehicle Fleet Mix Problems to Heterogeneous Fleet VRP (HVRP). We also propose a set of new realistic HVRP instances from 50 to more than 250 nodes coming from French counties. It relies on real distances in kilometers between towns. Since many classical HVRP instance sets are solved to optimality, this new set of instances could allow a fair comparative study of methods. The DFS split strategy shows its efficiency and attests the fact that it can be a promising line of research for routing problems including numerous additional constraints.