Tabu Search for Fleet Size and Mix Vehicle Routing Problem with Hard and Soft Time Windows
The paper presents a tabu search heuristic for the Fleet Size and Mix Vehicle Routing Problem (FSMVRP) with hard and soft time windows. The objective function minimizes the sum of travel costs, fixed vehicle costs, and penalties for soft time window violations. The algorithm is based on the tabu search with several neighborhoods. The main contribution of the paper is the efficient algorithm for a real-life vehicle routing problem. To the best of our knowledge, there are no papers devoted to the FSMVRP problem with soft time windows, while in real-life problems, this is a usual case. We investigate the performance of the proposed heuristic on the classical Solomon instances with additional constraints. We also compare our approach without soft time windows and heterogeneous fleet of vehicles with the recently published results on the VRP problem with hard time windows.