An evolutionary approach for multi-objective vehicle routing problems with backhauls

• A multiobjective evolutionary algorithm for vehicle routing problems with backhauls.
• Our approach equals or improves upon some of the best-known single-objective results.
• Instances have few bi-objective conflicts; SSMOEA, NSGA-II and MOEA/D perform well.
• Large tri-objective solution sets and significant differences in both algorithms.
• Triobjective setting finds comparable solutions to those from bi-objective settings.

The vehicle routing problem (VRP) is an important aspect of transportation logistics with many variants. This paper studies the VRP with backhauls (VRPB) in which the set of customers is partitioned into two subsets: linehaul customers requiring a quantity of product to be delivered, and backhaul customers with a quantity to be picked up. The basic VRPB involves finding a collection of routes with minimum cost, such that all linehaul and backhaul customers are serviced. A common variant is the VRP with selective backhauls (VRPSB), where the collection from backhaul customers is optional. For most real world applications, the number of vehicles, the total travel cost, and the uncollected backhauls are all important objectives to be minimized, so the VRPB needs to be tackled as a multi-objective problem. In this paper, a similarity-based selection evolutionary algorithm approach is proposed for finding improved multi-objective solutions for VRPB, VRPSB, and two further generalizations of them, with fully multi-objective performance evaluation.

Figure optionsDownload as PowerPoint slide