A Modified Column Generation to Solve the Heterogeneous Fixed Fleet Open Vehicle Routing Problem

Abstract

In the heterogeneous fixed fleet open vehicle routing problem (HFFOVRP), several different types of vehicles can be used to service the customers. The types of vehicles are different in terms of capacity, fixed cost, and variable cost. In this problem, the vehicles are not required to return to the depot after completing a service and the number of vehicles of each type is fixed and limited. Since this problem belongs to NP-hard problems, in this paper a compound heuristic algorithm called SISEC which includes sweep algorithm, insert, swap, and 2-opt moves, modified elite ant system (EAS), and column generation (CG) is applied to solve the HFFOVRP. We report computational results on 22 problems and solve each problem by using our SISEC. The results which were compared to the results of exact algorithms and the classic CG confirm that the proposed algorithm produces high quality solutions within an acceptable computation time.