The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm

•We introduce the fleet size and mix location-routing problem with time windows (FSMLRPTW).•We develop integer programming formulations for the FSMLRPTW.•We present a hybrid evolutionary search algorithm for the FSMLRPTW.

This paper introduces the fleet size and mix location-routing problem with time windows (FSMLRPTW) which extends the location-routing problem by considering a heterogeneous fleet and time windows. The main objective is to minimize the sum of vehicle fixed cost, depot cost and routing cost. We present mixed integer programming formulations, a family of valid inequalities and we develop a powerful hybrid evolutionary search algorithm (HESA) to solve the problem. The HESA successfully combines several metaheuristics and offers a number of new advanced efficient procedures tailored to handle heterogeneous fleet dimensioning and location decisions. We evaluate the strengths of the proposed formulations with respect to their ability to find optimal solutions. We also investigate the performance of the HESA. Extensive computational experiments on new benchmark instances have shown that the HESA is highly effective on the FSMLRPTW.