A Metaheuristic Algorithm for the Fleet Size and Mix Vehicle Routing Problem with Pickups and Deliveries

Abstract

Abstract This thesis addresses an extended variant of the fleet size and mix vehicle routing problem with aspects such as split pickups and deliveries, different loading and unloading methods, and the charging of electric vehicles. The aim of the work has been to be able to efficiently solve large-scale instances of the problem based on real data. To tackle this objective, a metaheuristic algorithm has been developed based on the adaptive large neighborhood search framework. A procedure for destroying and repairing a solution has been designed and implemented such that the challenging aspects of the problem definition are handled appropriately. Moreover, the use of simulated annealing and the technique of applying noise to diversify the search have been explored. The algorithm was run on three realistic instances, in a set of shorter runs to investigate the effect of adding noise and using simulated annealing. Then, three relatively long runs were conducted to obtain definitive solutions to the instances. The algorithm managed to find a promising solutions to all three instances, and the objective value of the best solutions found were significantly lower than the objective values of the initial solutions.