The Study on Methods for Solving a Multi-Objective Route Optimization Problem
| Autor: | Chi-Ju Wu, 吳奇儒 |
|---|---|
| Rok vydání: | 2007 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 95 Conventional methods in solving route optimization problems only focus on a single objective, mostly on one of the distance, time, or cost. According to the research regarding decision criteria for car drivers’ route choice, the distance and number of traffic light passed are two of the most important decision criteria. The route choice problem for drivers is a multi-objective route optimization (MORO) processes. Many researches have pointed out that the shortest path (SP) problem is NP-complete. It is hard to find the best-compromise solution of the SP problem without spending much effort. It is also impossible to identify the best-compromise solution of the SP problem by utilizing mathematical programming approach in a finite time. A heuristic or macro algorithm is usually applied to solve the SP problem, genetic or Dijkstra algorithm for example. In this research the MORO problem is resolved by utilizing two approaches, the integration and the heuristic algorithm approaches. The former converts the multi-objective problem into a single objective problem by utilizing the weight-sum method and then the Dijkstra is applied to identify the best-compromise solution. While the latter utilizes the genetic algorithm to search the best-compromise solution through the transformation of routes into genes and chromosomes and the design of suitable copy, crossover and mutation functions to provide randomly and broadly searching capabilities for a real road network. The experimental result shows that the best-compromise solution identified by the genetic algorithm is the same as the integration approach. It is sufficiently to convince that it is possible to apply the genetic algorithm to find the best-compromise solution for the MORO problem. The empirical test result also shows that the genetic operators and functions proposed by this research reveal their high contribution in solving the MORO problem. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|