Quality of service objectives for vehicle routing problem with time windows

Abstract In this paper we tackle a variant of the vehicle routing problem from the perspective of the quality in customer service. The proposed model corresponds to a routing planning problem where, in addition to the efficiency in the use of resources and time, the delivery process requires to reduce the response time to satisfy the customer demands. The problem includes the constraints of the well-known Vehicle Routing Problem with Time Windows but incorporates objective functions aimed at optimizing the service quality. The quality is here associated with the time the vehicles reach the existing customers within their time windows. Due to the complexity of the optimization problem under analysis, approximate approaches are identified as promising candidates to obtain high-quality solutions within reasonable computational times in realistic scenarios. In this regard, we propose a hybrid metaheuristic that combines the features of the Greedy Randomized Adaptive Search Procedure and the Variable Neighbourhood Search in order to generate efficient solutions of the optimization problem. The computational experiments demonstrate our algorithmic proposal is highly effective in providing high-quality solutions of classic problem instances and requires short computational times.