Dasgupta, Sumantra (2008-05). Multi-objective stochastic path planning. Master's Thesis. Thesis uri icon

abstract

  • The present research formulates the path planning as an optimization problem with multiple objectives and stochastic edge parameters. The first section introduces different variants of the PP problem and discusses existing solutions to the problem. The next section introduces and solves various versions of the PP model within the scope of this research. The first three versions describe a single entity traveling from a single source to a single destination node. In the first version, the entity has a single objective and abides by multiple constraints. The second version deals with an entity traveling with multiple objectives and multiple constraints. The third version is a modification of the second version where the actual probability distributions of travel times along edges are known. The fourth and final version deals with multiple heterogeneous entities routed from multiple sources (supply nodes) to multiple destinations (demand nodes) along capacitated edges. Each of these formulations is solved by using either exact algorithms or heuristics developed in this research. The performance of each algorithm/heuristic is discussed in the final section. The main contributions of this research are: 1. Provide a framework for analyzing PP in presence of multiple objectives and stochastic edge parameters. 2. Identify candidate constraints where clustering based multi-level programming can be applied to eliminate infeasible edges. 3. Provide an exact O (V.E) algorithm for building redundant shortest paths. 4. Provide an O (V.E+C2) heuristic for generating Pareto optimal shortest paths in presence of multiple objectives where C is the upper bound for path length. The complexity can be further reduced to O (V.E) by using graphical read-out of the Pareto frontier. 5. Provide a cost structure which can capture multiple key probability distribution parameters of edge variables. This is in contrast with usual techniques which just capture single parameters like the mean or the variance of distributions. 6. Provide a MIP formulation to a multi-commodity transportation problem with multiple decision variables, stochastic demands and uncertain edge/route capacities. 7. Provide an alternate formulation to the classic binary facility selection problem.
  • The present research formulates the path planning as an optimization problem
    with multiple objectives and stochastic edge parameters. The first section introduces
    different variants of the PP problem and discusses existing solutions to the problem. The
    next section introduces and solves various versions of the PP model within the scope of
    this research. The first three versions describe a single entity traveling from a single
    source to a single destination node. In the first version, the entity has a single objective
    and abides by multiple constraints. The second version deals with an entity traveling
    with multiple objectives and multiple constraints. The third version is a modification of
    the second version where the actual probability distributions of travel times along edges
    are known. The fourth and final version deals with multiple heterogeneous entities
    routed from multiple sources (supply nodes) to multiple destinations (demand nodes)
    along capacitated edges. Each of these formulations is solved by using either exact
    algorithms or heuristics developed in this research. The performance of each
    algorithm/heuristic is discussed in the final section. The main contributions of this
    research are: 1. Provide a framework for analyzing PP in presence of multiple objectives and
    stochastic edge parameters.
    2. Identify candidate constraints where clustering based multi-level programming
    can be applied to eliminate infeasible edges.
    3. Provide an exact O (V.E) algorithm for building redundant shortest paths.
    4. Provide an O (V.E+C2) heuristic for generating Pareto optimal shortest paths in
    presence of multiple objectives where C is the upper bound for path length. The
    complexity can be further reduced to O (V.E) by using graphical read-out of the
    Pareto frontier.
    5. Provide a cost structure which can capture multiple key probability distribution
    parameters of edge variables. This is in contrast with usual techniques which just
    capture single parameters like the mean or the variance of distributions.
    6. Provide a MIP formulation to a multi-commodity transportation problem with
    multiple decision variables, stochastic demands and uncertain edge/route
    capacities.
    7. Provide an alternate formulation to the classic binary facility selection problem.

publication date

  • May 2008