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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2755 |
| Date | 15 May 2009 |
| Creators | Dasgupta, Sumantra |
| Contributors | Banerjee, Amarnath |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Thesis, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.0022 seconds