Decomposition Strategies for Solving a Large-Scale Consistent Vehicle Routing Problem

A large-scale consistent vehicle routing problem is under consideration. In the problem, a company has a fleet of capacitated vehicles located in multiple depots, and there is a set of customers requiring a service. Vehicle routing is performed on a given planning horizon, and a vehicle should not exceed a limit on working hours per day. Each customer has a frequency of visits, which indicates how many times the customer must be visited during the planning horizon. Besides, to ensure consistency in the schedule, a customer should be visited by the same driver, and the time intervals between two consecutive visits must be the same. This allows the company to gain a competitive advantage by improving its service quality. Total travel costs are minimized in the problem while satisfying all the constraints. We present a POPMUSIC-based decomposition approach aimed to solve large-scale instances of the problem. The idea behind this approach is to improve the quality of a solution by iteratively solving subproblems of an overall problem. To get a solution for the overall problem and its subproblems, we use the variable neighborhood search (VNS) scheme developed by us previously. In the computational experiments section, we show a comparison of applying VNS for the whole problem and applying two different decomposition strategies: route- and customer-based ones.