  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 their orders during the whole
multi-period 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 are 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 fixed a 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 MILP 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.

Artificial Intelligence;Optimization and Control