The period routing problem (with N. Christofides), Networks, vol.14, no.2, 1984, pp237-256
In this paper we present heuristic algorithms for the period vehicle routing problem, the problem of designing vehicles 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 attempt to 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 travelling 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 and improvement of 13% over the previous best solution.