由於傳統最短路徑的演算法(如：Dijkstra algorithm、Bellman algorithm)，僅可用來求解節線旅行時間為固定常數的最短路徑問題，然而當節線旅行時間為「時間相依且隨機(time dependent and stochastic)」時，此時便無法利用傳統的最短路徑演算法求解，因此，本研究提出適合的最短路徑演算法來解決這個問題。
　　時間相依且隨機之最短路徑問題，目前並沒有polynomial time的演算法，此問題已被証明為一個很難的問題(intractable problem)。且本研究發現，基因演算法之編碼方式有適合於最短路徑的編碼，因此，本研究採用基因演算法求解「時間相依且隨機之最短路徑問題」。本研究的演算法可以應用在先進旅行者資訊系統(advanced public transportation system)，在已知現況的條件下(例如：出發時間、起迄點等相關資訊)，於用路人出發之前給予一條適當的行進建議，提供有效的「行前資訊」(pri-trip)服務。
　　本研究依照不同的模擬規則，將隨機產生的30題網路範例分成三種不同的情境進行測試，以驗證基因演算法的可行性，並且與Fu所提出的演算法作比較。由測試結果得知，本研究之基因演算法在「演化代數為第1代」的時候，其求解時間及求解品質與Fu演算法一樣；基因演算法在「演化代數為第2代以後」，其求解品質明顯優於Fu演算法，而Fu演算法如果要達到與基因演算法一樣的求解品質，所須花費的求解時間，幾乎都是基因演算法求解時間十倍以上才有可能達成。

none

陳一昌，「台灣地區發展智慧型運輸系統(ITS)系統架構之研究」，交通部運輸研究所，2002。

交通部，「台灣地區智慧型運輸系統綱要計畫」，交通部，2001。

陳慧琪，「時間相依最短路徑問題演算方法之研究」，國立交通大學運輸工程與管理學系碩士論文，2000。

Ahn C.W., and Ramakrishna R.S., “A Genetic Algorithm for Shortest Path Routing Problem and the Size of Populations,” IEEE Transactions on Evolutionary Computation, Vol.6, No.6, pp.566-579, 2002.

Ahuja R. K., Magnanti T. L., and Orlin J. B., “Network Flow: Theory, Algorithm, and Applications,” Prentice Hall, Englewood Cliffs, NJ, 1993.

Ahn C. W., Ramakrishna R. S., and Kang C. G., “Efficient Clustering-based
Routing Protocol in Mobile Ad-hoc Networks,” in Proc. IEEE Vehicular
Technology Conference (VTC’02), pp.1647–1651, 2002.

Azaron A. and Kianfar F., “Dynamic Shortest Path in Stochastic Dynamic Network: Ship Routing Problem,” European Journal of Operational Research, vol.144, pp.138-156, 2003.

Baker B.M., and Ayechew M.A., “A Genetic Algorithm for Vehicle Routing Problem,” Computers & Operations Research, vol.30, pp.787-800, 2003.
Bellman E., “On a Routing Problem,” Quarterly of Applied Mathematics, Vol.16, pp.87-90, 1958.

Baker B. M. and Ayechew M. A., “A genetic algorithm for the vehicle routing problem,” Computers and Operations Research, Vol. 30, pp. 787-800, 2003.

Bieli M., Caramia M., and Carotenuto P., “Genetic Algorithms in Bus Network Optimization, ” Transportation Research Part C, Vol.10, No.1, pp.19–34, 2002.

Cook K. L., and Halsey E., “The Shortest Path Route through a Network with Time Dependent Internodal Transit Times,” Journal of Mathematical Analysis and Application,Vol.14, pp.493-498, 1966.

Davies C., and Lingras P., “Genetic Algorithm for Rerouting Shortest Paths in Dynamic and Stochastic Networks,” European Journal of Operational Research, Vol.144, pp.27-38, 2003.

Deo N., and Pang C. Y., “Shortest Path Algorithm: Taxonomy and Annotation,” Network, Vol.14, pp.275, 1984.

Dijkstra E. W., “A Note on Two Problems on Connection with Graphs,” Numerical Mathematics, Vol.1, pp.395-412, 1959.

Dreyfus E., “An Appraisal of Some Shortest-Path Algorithms,” Operation Research, Vol.17, pp.395-412, 1969.

Fu L., and Rilett L. R., “Expected Shortest Paths in Dynamic and Stochastic Traffic Networks,” Transportation Research Part B, Vol.32, No.7, pp.499-516, 1998.

Fu L., “An Adaptive Routing Algorithm for In-vehicle Route Guidance Systems with Real-time Information,” Transportation Research Part B, Vol.35, pp.749-765, 2001

Gen M., and Cheng R., “Genetic Algorithms and Engineering Design,” John Wiley & Sons, 2000.

Gen M. and Li Y.,“Spanning tree-based genetic algorithm for bicriteria transportation problem ,”Computers and Industrial Engineering, Vol.35, pp. 531-534 , 1998.

Gen M., Cheng R., and Wang D., “Genetic Algorithm for Solving Shortest Path Problems,” Proceedings of 1997 IEEE International Conference on Evolutionary Computing, pp.401-406, 1997.

Hall R. W., “The Fastest Path through a Network with Random Time-Dependent Travel Times,” Transportation Science, Vol.20, No.3, pp.182-188, 1986.

Hwang H.,“An improved model for vehicle routing problem with time constraint based on genetic algorithm ,” Computers and Industrial Engineering, Vol.42, pp. 361-369, 2002.

Hedrick C., “Routing Information Protocol,” RFC 1058, 1988.

Holland J., “Adaptation in Natural and Artificial Systems,” Ann Arbor University of Michigan Press, 1975.

Leclerc F. and Potvin J., “Genetic Algorithms for Vehicle Dispatching, ” International Transactions in Operational Research, Vol.4, pp. 391-400, 1997.

Murthy S. and Garcia-Luna-Aceves J. J., “An Efficient Routing Protocol
for Wireless Networks,” ACM Mobile Networks Application Journal, pp.183–197, 1996.

Moy J., “Open Shortest Path First Protocol,” RFC 1583, 1994.

Orda B., and Rom R., “Shortest-Path and Minimum-Delay Algorithm in Networks with Time-Dependent Edge-Length,” Journal of the Association for Computing Machinery, Vol.37, No.3, pp.607-625, 1990.

Perkins C. E. and Bhagwat P., “Highly Dynamic Destination-Sequenced
Distance-Vector Routing (DSDV) for Mobile Computers,” Computer Communication Review, pp.234–244, 1994.

Park Y., “A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines,” International Journal of Production Economics, Vol. 73, pp. 175-188, 2001.

Sangit C. Cecilia C. and Lucy A.L., “Genetic Algorithms and Traveling Salesman Problems,” European Journal of Operational Research, vol.94, pp.490-510, 1996.

Syswerda G., “Scheduling Optimization Using Genetic Algorithms,” In Davis, L., Editor, Handbook of Genetic Algorithm, pp.332-349, 1991.

Wren A. and Wren D. O., “A genetic Algorithm for Public Transport Driver Scheduling,” Computers & Operations Research ,Vol.22, No.1, pp. 101–110, 1995.

Yen J. Y., “Finding the K Shortest Loopless Paths in a Networks,” Management Science, Vol.17, No.11, pp.712-716, 1971.

Zbigniew M., “Genetic Algorithms + Data Structures = Evolution Programs,” Third Revised and Extended Edition, 1996.

Ziliaskopoulos A. K. and Mahassani H. S., “Time-Dependent, Shortest Path Algorithm for Real-time Intelligent Vehicle System Applications,” Transportation Research Record 1408, TRB, National Research Council, Washington, DC. pp.94-100, 1993.