Graph theory based formulation of multi-period distribution expansion problems

Abstract

In this paper a multi-period planning problem, with arbitrarily defined planning goals, is formulated in terms of graph theory. The proposed formulation represents a multi-period planning problem as a weighted graph problem and thus decomposes original problem into a number of sequences (spanning paths) of static planning problems without loss of accuracy. This graph problem is solved using dynamic programming technique. The proposed dynamic programming algorithm guaranties that optimal solution of multi-period planning problems will be found efficiently, assuming that optimality of static planning problems is guarantied. Detailed numerical results and comparisons presented in the paper show that proposed approach could improve noticeably the quality of multi-period solutions. © 2010 Elsevier B.V. All rights reserved.