A customer-centric routing problem with multiple trips of a single vehicle

In this study, we introduce a routing problem with multiple uses of a single vehicle and service time in demand points, minimizing the sum of clients’ waiting time to receive service. This problem is relevant in the distribution of aid in disaster-stricken communities, in the recollection and/or delivery of perishable goods and personnel transportation, among other situations, where reaching clients to perform service, fast and fair, is a priority. We consider vehicle capacity and travel distance constraints, forcing multiple use of the vehicle during the planning horizon. This paper presents two mixed integer formulations for this problem, based on a multi-level network, as well as a metaheuristic algorithm. The proposed models can solve to optimality instances with up to 30 clients. The proposed metaheuristic algorithm obtains high-quality solutions in short computational times.