The Mixed Fleet Vehicle Routing Problem with overtime and light loads Formulation and Population Variable Neighbourhood search with Adaptive Memory

In this paper we consider a real-life Vehicle Routing Problem, characterized by heterogeneous vehicle fleet, demand-dependent service times, maximum allowable overtime and a special light load requirement. A new learning-based Population Variable Neighbourhood Search algorithm is designed to address this complex logistic problem. The computational experience suggests that savings up to 8% can be achieved when overtime and light load requirements are considered in advance. Moreover, accommodating for allowable overtime has shown to yield 12% better average utilization of the driver's working hours and 12.5% better average utilization of the vehicle load, without incurring extra running costs. The proposed metaheuristic method also shows some competitive results when applied to the special case of the real-life Vehicle Routing Problem, namely the Fleet Size and Mix Vehicle Routing Problem.