Abstract: We develop a heuristic for the consistent vehicle routing problem with time windows (ConVRPTW), which is motivated by a real-world application at a food company's distribution center. Besides standard VRPTW restrictions, ConVRPTW assigns each customer just one driver to fulfill his or her orders during the whole multiperiod planning horizon. For each driver and period, a route is sought to serve all their customers with positive demand. For each customer, the number of periods between consecutive orders and the ordered quantities is highly irregular. This causes difficulties in the daily routing, negatively impacting the service level of the company. Similar problems have been studied as ConVRP, where the number of drivers is fixeda priori, and only the total travel time is minimized. Moreover, the clients present no time window constraints, but the visits should be scheduled with a small arrival time variation. In our model, the objective is to minimize the number of drivers. We impose hard time windows but do not consider time consistency in more detail. We compare solutions given by the heuristic with solutions of a mixed-integer linear programming model on a set of small artificial instances and solutions used by the food company on real-world instances. The results show the effectiveness of the heuristic. For the company, we obtain significant improvements in the routing plans, with a lower number of vehicles and a higher rate of orders delivered within the prescribed time window.

Abstract: Vehicle Routing Problems (VRP) comprise many variants obtained by adding to the original problem constraints representing diverse system characteristics. Different variants are widely studied in the literature; however, the impact that these constraints have on the structure of the search space associated with the problem is unknown, and so is their influence on the performance of search algorithms used to solve it. This article explores how assignation constraints (such as a limited vehicle capacity) impact VRP by disturbing the network structure defined by the solution space and the local operators in use. This research focuses on Fitness Landscape Analysis for the multiple Traveling Salesman Problem (m-TSP) and Capacitated VRP (CVRP). We propose a new Fitness Landscape Analysis measure that provides valuable information to characterize the fitness landscape's structure under specific scenarios and obtain several relationships between the fitness landscape's structure and the algorithmic performance.