1 
Multiobjective stochastic path planningDasgupta, Sumantra 15 May 2009 (has links)
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 multilevel 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 readout 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 multicommodity 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.

2 
Multiobjective Optimization and Analysis of Slotted Waveguide Antenna Stiffened StructuresBrooks, Joseph Peyton 28 October 2022 (has links)
Slotted Waveguide Antenna Stiffened Structures (SWASS) offer a new way to integrate the antennas used by many aircraft systems in modern aircraft. Looking at the weather radars used by current aircraft and using the loading estimates of the X47B from Northrop Grumman, the designs went through several stages in the optimization procedure. The first stage centered around accounting for the stress concentrations present at the corners of the slots. These points led to local failure around the slots prior to the buckling of the overall structure, but the development of a concentration factor curve fit accounted for these in the optimization procedure and filled in a gap in the current literature. The models are then optimized, exposing a weakness in that these stress concentrations would lead to failure well before buckling in most designs with a loaded copper insert. To avoid this and shift most of the load to the supporting material, an initial gap is implemented in the eigenvalue buckling analysis, thus allowing for the simple 1D models to be rapidly optimized without the need for contact modelling upon the gap's closure. The waveguide designs are then analyzed to ensure that the optimization of the individual waveguides is not prioritizing the structural performance to the detriment of the electromagnetic performance. Multiple points along the optimized Pareto front are tested and showed that their electromagnetic performance was consistent across the various regions of the front, and that the desired frequency of 10 GHz used by weather radars was within the optimal operational range for the various designs. Continuing from the individual waveguides now to larger panels, high fidelity models were used to develop another curve fit that relates the buckling of a panel simply supported on all four sides to the buckling of a single constituent waveguide simply supported on both ends. This curve fit is then used to validate the larger panel's performance against anticipated flight loads, without the need to model entire panels during the optimization procedure. / Doctor of Philosophy / Modern aircraft utilize antennas for a variety of purpose, ranging from the weather radars in the nose of passenger airlines, to the communications antennas mounted on the exterior of military aircraft, and even the targeting radars used by weapons systems in modern military craft. However, these systems often require large empty spaces within the aircraft or interfere with the profile of the aircraft if mounted externally. Slotted Waveguide Antenna Stiffened Structures (SWASS) aims to eliminate these issues by integrating these antennas into the skin of the aircraft but uses the antennas themselves to help strengthen the structures, thereby eliminating the need to reroute the loads around them and making the aircraft lighter. These designs consist of a slotted metallic waveguide enclosed within supporting composite materials, which are substituted in place of the standard aircraft skin so as to fit seamlessly into the designs. Multiple issues can arise when attempting to do this, which this thesis tackles. To develop optimized, multifunctional designs the thesis balances the structural needs to integrate the designs into existing aircraft against the electromagnetic needs of the antenna systems it replaces. Gaps in the existing literature are addressed through the development of a curve fit to properly account for issues caused by the slots cut into the upper surface of the waveguides. New methods are also employed to simplify the optimization procedure. The first is reducing the load on the metallic waveguide through an initial gap by deriving a simplified model and eliminating the need for the complex models previously required. The next step is the creation of a new curve fit to relate the buckling of a single, less complex single waveguide model, to the buckling of the larger, more complex panel models. Throughout all of this, constraints and model validations are used to ensure that the designs meet their requirements, both as an antenna as well as a load bearing part of the aircraft's skin, specifically that of the X47B.

3 
A Novel Multiobjective EAbased Clustering Algorithm with Automatic Determination of the Number of ClustersChen, WenLing 07 September 2012 (has links)
Automatically determining the number of clusters without a priori knowledge is a difficult research issue for data clustering problem. An effective multiobjective evolutionary algorithm based clustering algorithm is proposed to not only overcome this problem but also provide a better clustering result in this study. The proposed algorithm differs from the traditional evolutionary algorithm in the sense that instead of a single crossover operator and a single mutation operator, the proposed algorithm uses a pool of crossover operators and a pool of mutation operators that are selected at random to increase the search diversity. To evaluate the performance of the proposed algorithm, several wellknown datasets are used. The simulation results show that not only can the proposed algorithm automatically determine the number of clusters, but it can also provide a better clustering result.

4 
Performance Evaluation of Dynamic Particle Swarm OptimizationUrade, Hemlata S., Patel, Rahila 15 February 2012 (has links)
Optimization has been an active area of research for
several decades. As many realworld optimization
problems become increasingly complex, better
optimization algorithms are always needed.
Unconstrained optimization problems can be formulated
as a Ddimensional minimization problem as follows:
Min f (x) x=[x1+x2+……..xD]
where D is the number of the parameters to be optimized.
subjected to: Gi(x) <=0, i=1…q
Hj(x) =0, j=q+1,……m
Xε [Xmin, Xmax]D, q is the number of inequality
constraints and mq is the number of equality constraints.
The particle swarm optimizer (PSO) is a relatively new
technique. Particle swarm optimizer (PSO), introduced by
Kennedy and Eberhart in 1995, [1] emulates flocking
behavior of birds to solve the optimization problems. / In this paper the concept of dynamic particle swarm
optimization is introduced. The dynamic PSO is different from
the existing PSO’s and some local version of PSO in terms of
swarm size and topology. Experiment conducted for benchmark
functions of single objective optimization problem, which shows
the better performance rather the basic PSO. The paper also
contains the comparative analysis for Simple PSO and Dynamic
PSO which shows the better result for dynamic PSO rather than
simple PSO.

5 
Dynamic Games and Multiobjective Optimization applied to designing Sustainable Urban NeighbourhoodsVanin, Daniel 11 January 2013 (has links)
This thesis intends to utilize mathematical models for testing the development of sustainable urban neighbourhoods and analyze the impact of these developments at city level using dynamic and multiobjective optimization techniques. These techniques aim to monitor and lower urban carbon emission levels, while predicting the municipality’s projected tax revenues. This study shows how multiple decision making models can operate and re late to help analyze the implementation of a sustainable neighbourhood design in a midsize urban area.

6 
Genetic programming for manufacturing optimisationDimopoulos, Christos January 2000 (has links)
No description available.

7 
Techniques and algorithms for solving the multiobjective path optimisation problem for car navigationChiu, ChingSheng, Surveying & Spatial Information Systems, Faculty of Engineering, UNSW January 2009 (has links)
The conventional information used to guide automobile drivers in selecting their driving routes is the shortestdistance path (SDP). As several researchers have pointed out, driver route selection is a multiple criteria decision process. This research proposes a multiobjective path optimisation (MOPO) decision model to make a more precise simulation of the decisionmaking behaviour of driver route selection. Seven singleobjective path optimisation (SOPO) decision models are taken into account to establish the MOPO decision model. They relate to travel time, travel cost, cumulative distance, roadway capacity, roadway grade, passed intersections and number of turns. To solve the MOPO problem, a twostage technique which incorporates shortest path (SP) algorithms and techniques for solving the multiobjective programming problem and a path genetic algorithm (PGA) are proposed. In addition, algorithms such as Dijkstra, A* and GA are reviewed and algorithms that are applicable for solving the MOPO problems are suggested. Furthermore, new algorithms for solving leastnode path (LNP) problem, corresponding to the objective of passed intersections, as well as minimumturn path (MTP) problem, corresponding to the objective of number of turns, are developed. To conduct the empirical study, a software tool  the multiobjective path optimisation analysis tool (MOPOAT)  was implemented. It contains tools for constructing a road network and its corresponding network topology, the environment of coding techniques for solving the MOPO problems and tools for the manipulation, statistics, analysis and display of experimental results. The purpose of implementing the MOPOAT software is to provide more efficient, convenient and userfriendly tools for solving MOPO and SOPO problems so that an empirical study of real road networks can be carried out more easily. To demonstrate the advantages of the proposed model in supporting more diverse information to drivers to assist in route selection, several experiments were conducted utilising three real road networks with different roadway types and numbers of nodes and links. Techniques and algorithms such as the twostage approach, Dijkstra and the PGA for solving the MOPO problem, and the Dijkstra, LNP and MTP algorithms for solving the SOPO problems were applied. Finally, to deal with improvements in computational efficiency for identifying SPs in a large road network and for population initialisation of the PGA, the criticalsection (CS) approach and the seedpath expansion (SPE) approach are proposed. To compare the run time between the conventional SP and CS algorithms as well as the PGA and the SPE algorithms, tools were implemented with commercial GIS, and experimental tests were conducted using road networks with a large amount of nodes and links and different roadway types. Through these theoretical and empirical studies, several useful contributions and conclusions were obtained. Some of the most significant findings are: 1. The experimental results demonstrate the advantages of integration with commercial GIS packages in supporting both spatial and attribute data displays. It can be safely said that, assisted by the MOPOAT software, it is easy for automobile drivers to obtain the optimal paths of the SDP, LNP, MTP and MOPO problems in seconds, despite these problems being highly complex and difficult to resolve manually. 2. According to the experimental results, the proposed LNP, MTP and MOPO decision models give automobile drivers richer information for choosing their driving routes in a more diverse way. 3. It is shown by the experimental results that the SDP and LNP mostly locate different paths in both radialcircumferential and gridtype road networks, and that the total passed intersections by the SDP are greater than passed by the LNP. Moreover, it is revealed that ambiguous turns might occur in both radialcircumferential and gridtype road networks. 4. It is found that the number of nodes of the SDP is in general greater than the number of nodes of the LNP and MTP irrespective of the type of road network. 5. A sensitivity analysis for weights shows that as the weighting value of the SDP objective incrementally increases by 0.1 units, the corresponding SDP??s objective value varies either low or high. The same results also occur for the LNP and MTP objectives. This verifies the fact that the weighting coefficients do not reflect proportionally the relative importance of the objectives. Moreover, the MTP objective has the higher sensitivity in comparison with the other two objectives. 6. Despite utilising Dijkstra or PGA algorithms for solving the MOPO problem, the LNP and MTP algorithms have to be employed to solve the noncommeasurable problem, whereby the standardisation objective value can be obtained. In addition, without any assisting information the PGA might fail to reach the bestcompromise solution. 7. It is found that the total run time for solving the MOPO problem by applying the Dijkstra algorithm is much faster than by the PGA. However, if the run time excludes the time needed for population initialisation, the PGA is much faster than the Dijkstra algorithm. 8. Based on calculated bottlenecks, the proposed CS approach partitions a SP into many critical sections in advance, with the result that a long SP can be obtained by combining all SPs of all CSs. The experimental results show that the run time of the CS algorithm is much faster than Dijkstra??s algorithm. Moreover, the test result for the Ppointer indicates that if the total number of nodes of a SP grows the computational efficiency of the CS algorithm becomes significantly better than the Dijkstra algorithm, and that the CS approach has the best performance. 9. The experimental result for the Epointer reveals that the computational efficiency of the CS algorithm will decrease gradually as the number of selected CSs increases. Therefore, the total percentage of selected CSs suggested by the experimental result is no more than 30 percent. 10. According to the experimental results, the performance order among SDP, LNP and MTP algorithms from fast to slow is SDP, MTP and LNP, and the LNP algorithm requires much more time than the other two algorithms. 11. As the total nodes of a path increase, most of the run time for SDP and LNP also increases. However, there are still some paths that violate the above rule. This result verifies that the run time needed for solving SDP and LNP is not only affected by the node numbers but also depends on the network topology. 12. Run time for solving the MOPO problem by applying the PGA is faster than applying the Dijkstra algorithm, if the run time of the former algorithm does not take into account the population initialisation time. Nevertheless, if the run time of the former algorithm does take into account the population initialisation time, the latter algorithm is much faster than the former algorithm. 13. In comparing the run time for population initialisation, the run time of the evolution process by applying the PGA is quite small, and the bottleneck of the run time for solving MOPO problem by applying the PGA is the population initialisation. 14. The population initialisation time is reduced significantly by applying the SPE algorithm, and increases at a very slow rate as the number of nodes of a path increases. As the total nodes of a path grow ever larger, the computing time is reduced more noticeably.

8 
Techniques and algorithms for solving the multiobjective path optimisation problem for car navigationChiu, ChingSheng, Surveying & Spatial Information Systems, Faculty of Engineering, UNSW January 2009 (has links)
The conventional information used to guide automobile drivers in selecting their driving routes is the shortestdistance path (SDP). As several researchers have pointed out, driver route selection is a multiple criteria decision process. This research proposes a multiobjective path optimisation (MOPO) decision model to make a more precise simulation of the decisionmaking behaviour of driver route selection. Seven singleobjective path optimisation (SOPO) decision models are taken into account to establish the MOPO decision model. They relate to travel time, travel cost, cumulative distance, roadway capacity, roadway grade, passed intersections and number of turns. To solve the MOPO problem, a twostage technique which incorporates shortest path (SP) algorithms and techniques for solving the multiobjective programming problem and a path genetic algorithm (PGA) are proposed. In addition, algorithms such as Dijkstra, A* and GA are reviewed and algorithms that are applicable for solving the MOPO problems are suggested. Furthermore, new algorithms for solving leastnode path (LNP) problem, corresponding to the objective of passed intersections, as well as minimumturn path (MTP) problem, corresponding to the objective of number of turns, are developed. To conduct the empirical study, a software tool  the multiobjective path optimisation analysis tool (MOPOAT)  was implemented. It contains tools for constructing a road network and its corresponding network topology, the environment of coding techniques for solving the MOPO problems and tools for the manipulation, statistics, analysis and display of experimental results. The purpose of implementing the MOPOAT software is to provide more efficient, convenient and userfriendly tools for solving MOPO and SOPO problems so that an empirical study of real road networks can be carried out more easily. To demonstrate the advantages of the proposed model in supporting more diverse information to drivers to assist in route selection, several experiments were conducted utilising three real road networks with different roadway types and numbers of nodes and links. Techniques and algorithms such as the twostage approach, Dijkstra and the PGA for solving the MOPO problem, and the Dijkstra, LNP and MTP algorithms for solving the SOPO problems were applied. Finally, to deal with improvements in computational efficiency for identifying SPs in a large road network and for population initialisation of the PGA, the criticalsection (CS) approach and the seedpath expansion (SPE) approach are proposed. To compare the run time between the conventional SP and CS algorithms as well as the PGA and the SPE algorithms, tools were implemented with commercial GIS, and experimental tests were conducted using road networks with a large amount of nodes and links and different roadway types. Through these theoretical and empirical studies, several useful contributions and conclusions were obtained. Some of the most significant findings are: 1. The experimental results demonstrate the advantages of integration with commercial GIS packages in supporting both spatial and attribute data displays. It can be safely said that, assisted by the MOPOAT software, it is easy for automobile drivers to obtain the optimal paths of the SDP, LNP, MTP and MOPO problems in seconds, despite these problems being highly complex and difficult to resolve manually. 2. According to the experimental results, the proposed LNP, MTP and MOPO decision models give automobile drivers richer information for choosing their driving routes in a more diverse way. 3. It is shown by the experimental results that the SDP and LNP mostly locate different paths in both radialcircumferential and gridtype road networks, and that the total passed intersections by the SDP are greater than passed by the LNP. Moreover, it is revealed that ambiguous turns might occur in both radialcircumferential and gridtype road networks. 4. It is found that the number of nodes of the SDP is in general greater than the number of nodes of the LNP and MTP irrespective of the type of road network. 5. A sensitivity analysis for weights shows that as the weighting value of the SDP objective incrementally increases by 0.1 units, the corresponding SDP??s objective value varies either low or high. The same results also occur for the LNP and MTP objectives. This verifies the fact that the weighting coefficients do not reflect proportionally the relative importance of the objectives. Moreover, the MTP objective has the higher sensitivity in comparison with the other two objectives. 6. Despite utilising Dijkstra or PGA algorithms for solving the MOPO problem, the LNP and MTP algorithms have to be employed to solve the noncommeasurable problem, whereby the standardisation objective value can be obtained. In addition, without any assisting information the PGA might fail to reach the bestcompromise solution. 7. It is found that the total run time for solving the MOPO problem by applying the Dijkstra algorithm is much faster than by the PGA. However, if the run time excludes the time needed for population initialisation, the PGA is much faster than the Dijkstra algorithm. 8. Based on calculated bottlenecks, the proposed CS approach partitions a SP into many critical sections in advance, with the result that a long SP can be obtained by combining all SPs of all CSs. The experimental results show that the run time of the CS algorithm is much faster than Dijkstra??s algorithm. Moreover, the test result for the Ppointer indicates that if the total number of nodes of a SP grows the computational efficiency of the CS algorithm becomes significantly better than the Dijkstra algorithm, and that the CS approach has the best performance. 9. The experimental result for the Epointer reveals that the computational efficiency of the CS algorithm will decrease gradually as the number of selected CSs increases. Therefore, the total percentage of selected CSs suggested by the experimental result is no more than 30 percent. 10. According to the experimental results, the performance order among SDP, LNP and MTP algorithms from fast to slow is SDP, MTP and LNP, and the LNP algorithm requires much more time than the other two algorithms. 11. As the total nodes of a path increase, most of the run time for SDP and LNP also increases. However, there are still some paths that violate the above rule. This result verifies that the run time needed for solving SDP and LNP is not only affected by the node numbers but also depends on the network topology. 12. Run time for solving the MOPO problem by applying the PGA is faster than applying the Dijkstra algorithm, if the run time of the former algorithm does not take into account the population initialisation time. Nevertheless, if the run time of the former algorithm does take into account the population initialisation time, the latter algorithm is much faster than the former algorithm. 13. In comparing the run time for population initialisation, the run time of the evolution process by applying the PGA is quite small, and the bottleneck of the run time for solving MOPO problem by applying the PGA is the population initialisation. 14. The population initialisation time is reduced significantly by applying the SPE algorithm, and increases at a very slow rate as the number of nodes of a path increases. As the total nodes of a path grow ever larger, the computing time is reduced more noticeably.

9 
Techniques and algorithms for solving the multiobjective path optimisation problem for car navigationChiu, ChingSheng, Surveying & Spatial Information Systems, Faculty of Engineering, UNSW January 2009 (has links)
The conventional information used to guide automobile drivers in selecting their driving routes is the shortestdistance path (SDP). As several researchers have pointed out, driver route selection is a multiple criteria decision process. This research proposes a multiobjective path optimisation (MOPO) decision model to make a more precise simulation of the decisionmaking behaviour of driver route selection. Seven singleobjective path optimisation (SOPO) decision models are taken into account to establish the MOPO decision model. They relate to travel time, travel cost, cumulative distance, roadway capacity, roadway grade, passed intersections and number of turns. To solve the MOPO problem, a twostage technique which incorporates shortest path (SP) algorithms and techniques for solving the multiobjective programming problem and a path genetic algorithm (PGA) are proposed. In addition, algorithms such as Dijkstra, A* and GA are reviewed and algorithms that are applicable for solving the MOPO problems are suggested. Furthermore, new algorithms for solving leastnode path (LNP) problem, corresponding to the objective of passed intersections, as well as minimumturn path (MTP) problem, corresponding to the objective of number of turns, are developed. To conduct the empirical study, a software tool  the multiobjective path optimisation analysis tool (MOPOAT)  was implemented. It contains tools for constructing a road network and its corresponding network topology, the environment of coding techniques for solving the MOPO problems and tools for the manipulation, statistics, analysis and display of experimental results. The purpose of implementing the MOPOAT software is to provide more efficient, convenient and userfriendly tools for solving MOPO and SOPO problems so that an empirical study of real road networks can be carried out more easily. To demonstrate the advantages of the proposed model in supporting more diverse information to drivers to assist in route selection, several experiments were conducted utilising three real road networks with different roadway types and numbers of nodes and links. Techniques and algorithms such as the twostage approach, Dijkstra and the PGA for solving the MOPO problem, and the Dijkstra, LNP and MTP algorithms for solving the SOPO problems were applied. Finally, to deal with improvements in computational efficiency for identifying SPs in a large road network and for population initialisation of the PGA, the criticalsection (CS) approach and the seedpath expansion (SPE) approach are proposed. To compare the run time between the conventional SP and CS algorithms as well as the PGA and the SPE algorithms, tools were implemented with commercial GIS, and experimental tests were conducted using road networks with a large amount of nodes and links and different roadway types. Through these theoretical and empirical studies, several useful contributions and conclusions were obtained. Some of the most significant findings are: 1. The experimental results demonstrate the advantages of integration with commercial GIS packages in supporting both spatial and attribute data displays. It can be safely said that, assisted by the MOPOAT software, it is easy for automobile drivers to obtain the optimal paths of the SDP, LNP, MTP and MOPO problems in seconds, despite these problems being highly complex and difficult to resolve manually. 2. According to the experimental results, the proposed LNP, MTP and MOPO decision models give automobile drivers richer information for choosing their driving routes in a more diverse way. 3. It is shown by the experimental results that the SDP and LNP mostly locate different paths in both radialcircumferential and gridtype road networks, and that the total passed intersections by the SDP are greater than passed by the LNP. Moreover, it is revealed that ambiguous turns might occur in both radialcircumferential and gridtype road networks. 4. It is found that the number of nodes of the SDP is in general greater than the number of nodes of the LNP and MTP irrespective of the type of road network. 5. A sensitivity analysis for weights shows that as the weighting value of the SDP objective incrementally increases by 0.1 units, the corresponding SDP??s objective value varies either low or high. The same results also occur for the LNP and MTP objectives. This verifies the fact that the weighting coefficients do not reflect proportionally the relative importance of the objectives. Moreover, the MTP objective has the higher sensitivity in comparison with the other two objectives. 6. Despite utilising Dijkstra or PGA algorithms for solving the MOPO problem, the LNP and MTP algorithms have to be employed to solve the noncommeasurable problem, whereby the standardisation objective value can be obtained. In addition, without any assisting information the PGA might fail to reach the bestcompromise solution. 7. It is found that the total run time for solving the MOPO problem by applying the Dijkstra algorithm is much faster than by the PGA. However, if the run time excludes the time needed for population initialisation, the PGA is much faster than the Dijkstra algorithm. 8. Based on calculated bottlenecks, the proposed CS approach partitions a SP into many critical sections in advance, with the result that a long SP can be obtained by combining all SPs of all CSs. The experimental results show that the run time of the CS algorithm is much faster than Dijkstra??s algorithm. Moreover, the test result for the Ppointer indicates that if the total number of nodes of a SP grows the computational efficiency of the CS algorithm becomes significantly better than the Dijkstra algorithm, and that the CS approach has the best performance. 9. The experimental result for the Epointer reveals that the computational efficiency of the CS algorithm will decrease gradually as the number of selected CSs increases. Therefore, the total percentage of selected CSs suggested by the experimental result is no more than 30 percent. 10. According to the experimental results, the performance order among SDP, LNP and MTP algorithms from fast to slow is SDP, MTP and LNP, and the LNP algorithm requires much more time than the other two algorithms. 11. As the total nodes of a path increase, most of the run time for SDP and LNP also increases. However, there are still some paths that violate the above rule. This result verifies that the run time needed for solving SDP and LNP is not only affected by the node numbers but also depends on the network topology. 12. Run time for solving the MOPO problem by applying the PGA is faster than applying the Dijkstra algorithm, if the run time of the former algorithm does not take into account the population initialisation time. Nevertheless, if the run time of the former algorithm does take into account the population initialisation time, the latter algorithm is much faster than the former algorithm. 13. In comparing the run time for population initialisation, the run time of the evolution process by applying the PGA is quite small, and the bottleneck of the run time for solving MOPO problem by applying the PGA is the population initialisation. 14. The population initialisation time is reduced significantly by applying the SPE algorithm, and increases at a very slow rate as the number of nodes of a path increases. As the total nodes of a path grow ever larger, the computing time is reduced more noticeably.

10 
Techniques and algorithms for solving the multiobjective path optimisation problem for car navigationChiu, ChingSheng, Surveying & Spatial Information Systems, Faculty of Engineering, UNSW January 2009 (has links)
The conventional information used to guide automobile drivers in selecting their driving routes is the shortestdistance path (SDP). As several researchers have pointed out, driver route selection is a multiple criteria decision process. This research proposes a multiobjective path optimisation (MOPO) decision model to make a more precise simulation of the decisionmaking behaviour of driver route selection. Seven singleobjective path optimisation (SOPO) decision models are taken into account to establish the MOPO decision model. They relate to travel time, travel cost, cumulative distance, roadway capacity, roadway grade, passed intersections and number of turns. To solve the MOPO problem, a twostage technique which incorporates shortest path (SP) algorithms and techniques for solving the multiobjective programming problem and a path genetic algorithm (PGA) are proposed. In addition, algorithms such as Dijkstra, A* and GA are reviewed and algorithms that are applicable for solving the MOPO problems are suggested. Furthermore, new algorithms for solving leastnode path (LNP) problem, corresponding to the objective of passed intersections, as well as minimumturn path (MTP) problem, corresponding to the objective of number of turns, are developed. To conduct the empirical study, a software tool  the multiobjective path optimisation analysis tool (MOPOAT)  was implemented. It contains tools for constructing a road network and its corresponding network topology, the environment of coding techniques for solving the MOPO problems and tools for the manipulation, statistics, analysis and display of experimental results. The purpose of implementing the MOPOAT software is to provide more efficient, convenient and userfriendly tools for solving MOPO and SOPO problems so that an empirical study of real road networks can be carried out more easily. To demonstrate the advantages of the proposed model in supporting more diverse information to drivers to assist in route selection, several experiments were conducted utilising three real road networks with different roadway types and numbers of nodes and links. Techniques and algorithms such as the twostage approach, Dijkstra and the PGA for solving the MOPO problem, and the Dijkstra, LNP and MTP algorithms for solving the SOPO problems were applied. Finally, to deal with improvements in computational efficiency for identifying SPs in a large road network and for population initialisation of the PGA, the criticalsection (CS) approach and the seedpath expansion (SPE) approach are proposed. To compare the run time between the conventional SP and CS algorithms as well as the PGA and the SPE algorithms, tools were implemented with commercial GIS, and experimental tests were conducted using road networks with a large amount of nodes and links and different roadway types. Through these theoretical and empirical studies, several useful contributions and conclusions were obtained. Some of the most significant findings are: 1. The experimental results demonstrate the advantages of integration with commercial GIS packages in supporting both spatial and attribute data displays. It can be safely said that, assisted by the MOPOAT software, it is easy for automobile drivers to obtain the optimal paths of the SDP, LNP, MTP and MOPO problems in seconds, despite these problems being highly complex and difficult to resolve manually. 2. According to the experimental results, the proposed LNP, MTP and MOPO decision models give automobile drivers richer information for choosing their driving routes in a more diverse way. 3. It is shown by the experimental results that the SDP and LNP mostly locate different paths in both radialcircumferential and gridtype road networks, and that the total passed intersections by the SDP are greater than passed by the LNP. Moreover, it is revealed that ambiguous turns might occur in both radialcircumferential and gridtype road networks. 4. It is found that the number of nodes of the SDP is in general greater than the number of nodes of the LNP and MTP irrespective of the type of road network. 5. A sensitivity analysis for weights shows that as the weighting value of the SDP objective incrementally increases by 0.1 units, the corresponding SDP??s objective value varies either low or high. The same results also occur for the LNP and MTP objectives. This verifies the fact that the weighting coefficients do not reflect proportionally the relative importance of the objectives. Moreover, the MTP objective has the higher sensitivity in comparison with the other two objectives. 6. Despite utilising Dijkstra or PGA algorithms for solving the MOPO problem, the LNP and MTP algorithms have to be employed to solve the noncommeasurable problem, whereby the standardisation objective value can be obtained. In addition, without any assisting information the PGA might fail to reach the bestcompromise solution. 7. It is found that the total run time for solving the MOPO problem by applying the Dijkstra algorithm is much faster than by the PGA. However, if the run time excludes the time needed for population initialisation, the PGA is much faster than the Dijkstra algorithm. 8. Based on calculated bottlenecks, the proposed CS approach partitions a SP into many critical sections in advance, with the result that a long SP can be obtained by combining all SPs of all CSs. The experimental results show that the run time of the CS algorithm is much faster than Dijkstra??s algorithm. Moreover, the test result for the Ppointer indicates that if the total number of nodes of a SP grows the computational efficiency of the CS algorithm becomes significantly better than the Dijkstra algorithm, and that the CS approach has the best performance. 9. The experimental result for the Epointer reveals that the computational efficiency of the CS algorithm will decrease gradually as the number of selected CSs increases. Therefore, the total percentage of selected CSs suggested by the experimental result is no more than 30 percent. 10. According to the experimental results, the performance order among SDP, LNP and MTP algorithms from fast to slow is SDP, MTP and LNP, and the LNP algorithm requires much more time than the other two algorithms. 11. As the total nodes of a path increase, most of the run time for SDP and LNP also increases. However, there are still some paths that violate the above rule. This result verifies that the run time needed for solving SDP and LNP is not only affected by the node numbers but also depends on the network topology. 12. Run time for solving the MOPO problem by applying the PGA is faster than applying the Dijkstra algorithm, if the run time of the former algorithm does not take into account the population initialisation time. Nevertheless, if the run time of the former algorithm does take into account the population initialisation time, the latter algorithm is much faster than the former algorithm. 13. In comparing the run time for population initialisation, the run time of the evolution process by applying the PGA is quite small, and the bottleneck of the run time for solving MOPO problem by applying the PGA is the population initialisation. 14. The population initialisation time is reduced significantly by applying the SPE algorithm, and increases at a very slow rate as the number of nodes of a path increases. As the total nodes of a path grow ever larger, the computing time is reduced more noticeably.

Page generated in 0.1496 seconds