Territory Design for the Multi-Period Vehicle Routing Problem with Time Windows

This study introduces the Territory Design for the Multi-Period Vehicle Routing Problem with Time Windows (TD-MPVRPTW) problem, motivated by a real-world application at a food company's distribution center. This problem deals with the design of contiguous and compact territories for delivery of orders from a depot to a set of customers, with time windows, over a multi-period planning horizon. Customers and their demands vary over time. The problem is modeled as a mixed-integer linear program (MILP) and solved by a proposed heuristic. The heuristic solutions are compared with the proposed MILP solutions on a set of small artificial instances and the food company's solutions on a set of real-world instances. Computational results show that the proposed algorithm can yield high-quality solutions within moderate running times. A methodology is proposed in which the territories computed by the proposed heuristic on the past demand of one month are used for the operational routing during the following month, in which the demand is known only one day in advance. An evaluation shows that the territories obtained with our methodology would have led to levels of service significantly better than the ones that were experienced by the company, using a significantly lower number of vehicles to execute the deliveries.

Automated summary

This study introduces a territory design for the multi-period vehicle routing problem with time windows (TD-MPVRPTW) in a food company's distribution center. The study proposes a heuristic algorithm to solve the problem and compares it with existing solutions. The results show that the proposed algorithm can provide high-quality solutions within a reasonable running time. The study also presents a methodology in which the computed territories from the past month are used for the operational routing in the following month. Evaluation results demonstrate that the territories obtained with this methodology can significantly improve service levels and require fewer vehicles for delivery.