Long-Range Facility Planning Based on Dynamic Programming for Optimum Combined Cost and Probability Paths

Abstract

Dynamic programming (DP)-based planning algorithms have been shown to be valuable tools since they provide a basis for sampling, enumeration, and optimization of options for long-range deployment of facilities. Previous applications of DP to optimize pipeline long-range facility planning problems based on either the least-cost path for the facility or the most-probable path for noncost constraints have been documented in the literature. Such applications, however, are faced with a challenge in selecting the optimum facility deployment path, as the least-cost path does not always necessarily coincide with the most-probable path. As a result, the selection of a path that combines both features has to be achieved through a subjective compromise and in a rather arbitrary manner. In the present paper, two new DP methods have been developed which are based on the concept of combining cost and probability to give a single-objective probability-adjusted cost. One method incorporated the probability of each arc in the DP architecture using a variation of the Black-Scholes partial differential equation. The solution of the resulting equation gave a probability-adjusted arc cost dependent on the year (or stage) the cost incurred, the overall probability of all constraints associated with this arc, and the risk-free rate. The other method was based on simply dividing the present value of each arc cost by its probability to give a single probability-adjusted cost. Both approaches were applied to a complex DP architecture composed of 10 stages and 10 different options at each stage in which all options were available at every stage in a directed manner. The optimum paths from the new approaches were compared to the least-cost options, and most-probable options, and were found to combine the two features. Finally, all options from all methods were found to lie on a Pareto front obtained from a multiobjective genetic algorithm.