Fuzzy multi-objective programming algorithm for vehicle routing problems with backhauls

Abstract

The vehicle routing problem with backhauls (VRPB) is an extension of the standard vehicle routing problem. VRPB has two sets of customers: linehaul customers and backhaul customers. The aim of this study is to propose a new algorithm based on fuzzy multi-objective programming (FMOP-VRPB algorithm) to solve the VRPB. The FMOP-VRPB algorithm has three phases; clustering, routing and local search. In the clustering phase, customers are assigned to vehicles by the proposed multi-objective programming (MOP) model with two objective functions: minimizing the total distance and maximizing the total savings value. The proposed MOP model is solved by fuzzy operators. The weights of the objectives are also calculated by a fuzzy two-person zero-sum game with mixed strategies using membership functions in a fuzzy pay-off matrix. In the routing phase, each vehicle is routed as a traveling salesman problem with backhauls. The local search phase is used to improve the routes. The primary contributions of the FMOP-VRPB algorithm are to consider the two objectives, to determine the weights of objectives using the proposed fuzzy pay-off matrix in the clustering phase and to use only mathematical programming in both the clustering and routing phases through many customers in an acceptable CPU time. The algorithm will also show that the proposed MOP model defines the seed customers itself in the clustering phase and will always generates feasible clusters, contrary to the reports in the literature. Benchmark problems from the literature are solved to test the performance of the FMOP-VRPB algorithm. The results indicate that the FMOP-VRPB algorithm generates sufficient solutions, and CPU times are within acceptable limits. In addition, a weekly routing problem for a logistics department of a ceramics firm in Turkey is solved by the FMOP-VRPB algorithm. Additionally, this study is the first to solve a real world VRPB; the solution shows that the FMOP-VRPB algorithm is suitable and effective for real world problems