An Improved Genetic Algorithm Approach for Vehicle Routing Problems with Backhauls

In this paper, we address the vehicle routing problems with backhauls. This type of vehicle routing problem consists of two types of delivery, linehaul and backhaul cases. For the linehaul case, vehicles deliver goods/products from a single depot to receiver customers. In contrast, for the backhaul case, the delivery process starts from the sender customers and ends at the depot. This problem is classified as NP-hard, indeed, a high cost and a high number of vehicles will be caused in case of poor planning and management. Thus, it is important to develop an efficient strategy to manage this process in a way to reduces the overall cost. In this paper, we first formulated an assignment integer linear programming model, which is proven to solve instances of limited size. For large-scale instances, we developed an evolutionary genetic algorithm approach, which has been tested to be efficient for solving large-scale problems. The result shows that combining the linehaul and backhaul cases saves on delivery cost and vehicles.