A multiphase approach to the period routing problem

In this article, we present a multiphase approach to the period routing problem. The period routing problem involves the design of effective vehicle routes that satisfy customer service frequencies over a specified planning horizon. The first phase of analysis consists of a generalized network approximation to achieve an efficient initial solution. The second phase involves an interchange heuristic that reduces distribution costs by solving a surrogate traveling salesman problem. The third phase consists of an interchange heuristic that further reduces the distribution costs by addressing the actual vehicle routes of the period routing problem. A fourth phase utilizes a 0–1 integer model to attempt further improvements. Computational results on test problems indicate that the multiphase approach yields improvements over previous best solutions.