Graph theory based formulation of multi-period distribution expansion problems

Distribution expansion planning is a complex combinatorial optimization problem. Various heuristic and mathematical models have been proposed for solving such a complex problem. One of the major characteristics of these models is whether they consider a single planning period or multi planning periods. Although multi-period problems are far more challenging to formulate and considerably more complex computationally, they produce more consistent and economic expansion plans. The multi-period problems have been formulated as complete dynamic problems and decomposition problems. Complete dynamic models, due to significant computational complexity, are limited to small size multi-period problems while decomposition algorithms proposed so far inadequately and inaccurately take into account interactions that exist between periods.