The period routing problem

TLDR

The largest benchmark problem in the literature was solved by Russell and Igo. The study proposes heuristic algorithms to design vehicle routes that satisfy customer service levels while minimizing distribution costs over a multi‑day period. The heuristics first assign delivery days to satisfy service levels, then iteratively interchange routes to reduce costs, modeling each day’s routing as a median problem followed by a traveling salesman problem. Computational experiments on up to 126‑customer instances show the heuristics outperform previous solutions, achieving a 13% improvement on the largest benchmark problem.

Abstract

Abstract In this paper we present heuristic algorithms for the period vehicle routing problem, the problem of designing vehicle routes to meet required service levels for customers and minimize distribution costs over a given several‐day period of time. These heuristic algorithms are based on an initial choice of customer delivery days which meet the service level requirements, followed by an interchange procedure in an attempt to minimize distribution costs. The heuristic algorithms represent distribution costs by replacing the vehicle routing problem for each day of the period by (i) a median problem and (ii) a traveling salesman problem. Computational results and comparisons are given for the algorithms, based on test problems derived from the literature with up to 126 customers. The largest of these problems is the one given and solved by Russell and Igo. The solution obtained for this problem by the heuristic algorithms shows an improvement of 13% over the previous best solution.