The conventional information used to guide automobile drivers in selecting their driving routes is the shortest-distance 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 decision-making behaviour of driver route selection. Seven single-objective 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 two-stage 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 least-node path (LNP) problem, corresponding to the objective of passed intersections, as well as minimum-turn 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 user-friendly 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 two-stage 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 critical-section (CS) approach and the seed-path 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 radial-circumferential and grid-type 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 radial-circumferential and grid-type 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 non-commeasurable problem, whereby the standardisation objective value can be obtained. In addition, without any assisting information the PGA might fail to reach the best-compromise 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 P-pointer 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 E-pointer 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.
| Identifer | oai:union.ndltd.org:ADTP/230137 |
| Date | January 2009 |
| Creators | Chiu, Ching-Sheng, Surveying & Spatial Information Systems, Faculty of Engineering, UNSW |
| Publisher | Publisher:University of New South Wales. Surveying & Spatial Information Systems |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | http://unsworks.unsw.edu.au/copyright, http://unsworks.unsw.edu.au/copyright |
Page generated in 0.002 seconds