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

Year 2021, Volume: 39 Issue: 3, 226 - 236, 27.09.2021

Mustafa Demirbilek

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 (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 (SA) metaheuristic method with two construction heuristics, Clark and Wright (CW) algorithm and the nearest neighbourhood (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 (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

References

• [1] Dantzig GB, Ramser JH. The truck dispatching problem. Management Science 1959;6:80–91 [CrossRef]
• [2] Laporte G. Fifty years of vehicle routing. Transportation Science 2009;43:408–16. [CrossRef]