A metaheuristic solution approach with two construction heuristics for vehicle routing problem with simultaneous Linehauls and Backhauls

Authors : Mustafa DEMİRBİLEK

Pages : 226-236

View : 27 | Download : 11

Publication Date : 2021-09-27

Article Type : Research Paper

Abstract :Since highly competitive business environments and strict governmental regulations, logistic companies have started to handle pickup and delivery activities at the same time to satisfy demands of customers. This problem is called as Vehicle Routing Problem with Simultaneous Linehauls and Backhauls insert ignore into journalissuearticles values(VRPSLB);. The objective is to minimize total travel times of vehicles that visit a predetermined number of customers in a service area. When delivering and collecting orders of customers, we must also make sure not to exceed capacity of vehicles. Since VRPB is in NP Hard class, exact solution methods do not work for large problem sets. In this study, we proposed a simulated annealing insert ignore into journalissuearticles values(SA); metaheuristic method with two construction heuristics, Clark and Wright insert ignore into journalissuearticles values(CW); algorithm and the nearest neighbourhood insert ignore into journalissuearticles values(NN); search algorithm. Since quality of final solutions are directly related to the quality of initial solutions, we propose two heuristics to generate initial solutions. Daily working times for vehicles and service times for customers are considered as hard constraints in this problem. Results of SA with two heuristics are compared to results of the mixed integer linear programming insert ignore into journalissuearticles values(MILP); for relatively small problem sets where the numbers of customers and vehicles vary 20 to 40 and 2 to 5, respectively. Results demonstrate that SA provides up to %7 longer total travel times compared to MILP. SA with NN shows better performance compared to SA with CW. For large problems, we do not observe a significant difference between the performance of SA with NN and SA with CW.
Keywords : Simulated annealing approach, Construction heuristics, Vehicle routing problem with simultaneous Linehauls and Backhauls, Mixed integer linear programming

ORIGINAL ARTICLE URL