Solving the Fleet Size and Mix Vehicle Routing Problem with Time Windows via Adaptive Memory Programming

This paper presents a novel Adaptive Memory Programming (AMP) solution approach for the Fleet Size and Mix Vehicle Routing Problem with Time Windows (FSMVRPTW). The FSMVRPTW seeks to design a set of depot returning vehicle routes to service a set of customers with known demands, for a heterogeneous fleet of vehicles with different capacities and fixed costs. Each customer is serviced only once by exactly one vehicle, within fixed time intervals that represent the earliest and latest times during the day that service can take place. The objective is to minimize the total transportation costs, or similarly to determine the optimal fleet composition and dimension following least cost vehicle routes. The proposed method utilizes the basic concept of an AMP solution framework equipped with a probabilistic semi-parallel construction heuristic, a novel solution re-construction mechanism, an innovative Iterated Tabu Search algorithm tuned for intensification local search and frequency-based long term memory structures. Computational experiments on well-known benchmark data sets illustrate the efficiency and effectiveness of the proposed method. Compared to the current state-of-the-art, the proposed method improves the best reported cumulative and mean results over most problem instances with reasonable computational requirements.