臺灣博碩士論文加值系統

在全球許多都市，交通壅塞已經成為一個嚴重的問題，並已造成了許多不良的效應，像是空氣汙染、能源浪費、增加通勤時間以及產生二氧化碳等。共乘是一個有效解決交通壅塞問題的方法之一，這將有效地提升車輛的使用率以及減少閒置座位。在本文提出的行動客戶端，共乘使用者可以透過他們的智慧型手持裝置連接上行動通訊網路，送出共乘需求到全球雲端共乘服務模組，並接收共乘配對結果。接下來，全球雲端共乘服務模組是用來處理接收到的共乘需求，並透過本文提出的基於基因演算法之共乘路由與配對演算法，產生合適的共乘配對結果，其中，本演算法將大幅度的減少求解大量使用者之共乘路由配對問題時，所需要的運算時間。此外，為了發展一個可用於世界各地的共乘服務，我們整合了開放式全球地理圖資系統到我們提出的全球雲端共乘服務模組之中。我們的實驗結果顯示，在求解不同的測試情境之共乘路由與配對問題時，當同時考慮到解的品質與所需要的處理時間，本文提出的基於基因演算法之共乘路由與配對演算法有辦法提供近似於窮舉演算法所計算出來之擁有最短旅途成本的最佳解，而且運算速度也快於窮舉演算法以及亂數配對演算法，進而可以大幅地減少所需要的處理時間。

Traffic congestion has been a serious problem in many urban areas around the world, causing various negative impacts such as generation of air pollution, wasting of fuel, increased travel time, production of carbon dioxide emissions, and so on. Carpooling is one of the most effective solutions to traffic congestion. It consists of increasing the occupancy rate of cars by reducing the empty seats in these vehicles effectively. In this paper, we propose an intelligent carpool system called BlueNet. The proposed system involves two significant proposed modules: the Mobile Client module and the Cloud Global Carpool Services module. In our proposed Mobile Client module, the carpool users can send carpool requests and receive carpool matching results via the proposed Cloud Global Carpool Services module by using their smart handheld devices via the mobile communication network. The following Cloud Global Carpool Services module is used to manage requests and generate suitable match results through the proposed Genetic-based Carpool Route and Matching algorithm. The Genetic-based Carpool Route and Matching algorithm furthers the solution to the carpool route and matching problem by dramatically reducing the time required to match a large number of users. In order to develop a carpool service that can be used around the world, we integrated the open GIS system with abundant global geographical information into the proposed Cloud Global Carpool Services module. In regard to the quality of the solutions and processing time, the experimental results show that the proposed Genetic-based Carpool Route and Matching algorithm consistently is able to find carpool route and matching results that are among the most optimal. Use of the Genetic-based Carpool Route and Matching algorithm may result in a similar minimum travel cost as obtained by the exhaustive algorithm. However the Genetic-based Carpool Route and Matching algorithm operates with significantly less computational complexity than does the Exhaustive algorithm, thus requiring less time. The Genetic-based Carpool Route and Matching algorithm is also substantially faster than the Random Matching algorithm.

中文摘要 i
ABSTRACT ii
誌謝 iv
CONTENTS v
LIST OF TABLES vi
LIST OF FIGURES vii
Chapter 1 INTRODUCTION 1
Chapter 2 THE PROPOSED FRAMEWORK 4
2.1 Mobile Client Module 5
2.2 Cloud Global Carpool Services module 6
Chapter 3 PROPOSED GENETIC-BASED APPROACH 7
3.1 Evolution Initialization Module 9
3.1.1 Chromosome Representation procedure 9
3.1.2 Population Initialization procedure 11
3.2 Genetic Evolution Module 12
3.2.1 Chromosome Evaluation procedure 12
3.2.2 Chromosome Selection procedure 13
3.2.3 Chromosome Crossover procedure 14
3.2.4 Chromosome Mutation procedure 16
Chapter 4 EXPERIMENTAL RESULTS 17
4.1 The Comparison between GCRM, EA, and RM 17
4.2 Further Analysis on the GCRM Algorithm 21
Chapter 5 CONCLUSIONS 25
REFERENCES 27

[1]F. Y. Wang, S. Tang, Y. Sui, and X. Wang, “Toward intelligent transportation systems for the 2008 Olympics,” IEEE Intelligent Systems, vol. 18, pp. 8–11, Nov. 2003
[2]R. Barrero, J. V. Mierlo, and X. Tackoen, “Energy savings in public transport,” IEEE Vehicular Technology Magazine, vol. 3, pp. 26–36, Sep. 2008
[3]S. Tsugawa and S. Kato, “Energy ITS: another application of vehicular communications,” IEEE Communications Magazine, vol. 48, pp. 120–126, Nov. 2010
[4]S. Hartwig and M. Buchmann, “Empty Seats Traveling,” Nokia Research Center Bochum, Feb. 2007
[5]R. Fagin and J. H. Williams, “A Fair Carpool Scheduling Algorithm,” IBM Journal of Research and Development, vol. 27, pp. 133–139, Mar. 1983
[6]R. K. Megalingam, R. N. Nair, V. Radhakrishnan, and A. V. Vidyapeetham, “Automated Wireless Carpooling System for an Eco-Friendly Travel,” Electronics Computer Technology, vol. 4, pp. 325–329, Apr. 8-10 2011
[7][Online]. Available: http://www.carpoolglobal.com
[8][Online]. Available: http://alternetrides.com
[9][Online]. Available: http://www.shareyourride.net
[10][Online]. Available: http://www.carpoolingnetwork.com
[11][Online]. Available: http://www.carpoolking.com
[12]Z. Dawy, A. Husseini, E. Yaacoub, and L. Al-Kan, “A Wireless Communications Laboratory on Cellular Network Planning,” IEEE Transactions on Education, vol. 53, pp. 653–661, Nov. 2010
[13]Z. Shen, A. Papasakellariou, J. Montojo, D. Gerstenberger, and F. Xu, “Overview of 3GPP LTE-advanced carrier aggregation for 4G wireless communications,” IEEE Communications Magazine, vol. 50, pp. 122–130, Feb. 2012
[14]Google Maps, http://www.googlemaps.com
[15]Bing Maps, http://www.bing.com/maps/
[16]OpenLayers, http://openlayers.org/
[17]R. Baraglia, J. I. Hidalgo, and R. Perego, “A hybrid heuristic for the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 5, pp. 613–622, Dec. 2001
[18]S. Jung and B. R. Moon, “Toward minimal restriction of genetic encoding and crossovers for the two-dimensional Euclidean TSP,” IEEE Transactions on Evolutionary Computation, vol. 32, pp. 557–565, Dec. 2002
[19]H. D. Jin, K. S. Leung, M. L. Wong, and Z. B. Xu, “An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 33, pp. 877–888, Dec. 2003
[20]H. D. Nguyen, I. Yoshihara, K. Yamamori, and M. Yasunaga, “Implementation of an Effective Hybrid GA for Large-Scale Traveling Salesman Problems,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 37, pp. 92–99, Feb. 2007
[21]I. Benyahia and J. Y. Potvin, “Decision support for vehicle dispatching using genetic programming,” IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 28, pp. 306–314, May 1998
[22]H. C. W. Lau, T. M. Chan, W. T. Tsui, and W. K. Pang, “Application of Genetic Algorithms to Solve the Multidepot Vehicle Routing Problem,” IEEE Transactions on Automation Science and Engineering, vol. 7, pp. 383–392, April. 2010
[23]C. W. Ahn and R. S. Ramakrishna, “A genetic algorithm for shortest path routing problem and the sizing of populations,” IEEE Transactions on Evolutionary Computation, vol. 6, pp. 566–579, Dec. 2002
[24]T. Y. Chou, T. K. Liu, C. N. Lee, and C. R. Jeng, “Method of Inequality-Based Multiobjective Genetic Algorithm for Domestic Daily Aircraft Routing,” IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 38, pp. 299–308, Mar. 2008
[25]L. Ozdamar, “A genetic algorithm approach to a general category project scheduling problem,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 29, pp. 44–59, Feb. 1999
[26]L. Y. Tseng, and S. C. Chen, “Two-Phase Genetic Local Search Algorithm for the Multimode Resource-Constrained Project Scheduling Problem,” IEEE Transactions on Evolutionary Computation, vol. 13, pp. 848–857, Aug. 2009
[27] R. Zamani, “An Accelerating Two-Layer Anchor Search With Application to the Resource-Constrained Project Scheduling Problem,” IEEE Transactions on Evolutionary Computation, vol. 14, pp. 975–984, Dec. 2010
[28] W. Huang and L. Ding, “Project-Scheduling Problem With Random Time-Dependent Activity Duration Times,” IEEE Transactions on Engineering Management, vol. 58, pp. 377–387, May 2011
[29] H. Ishibuchi and T. Murata, “A multi-objective genetic local search algorithm and its application to flowshop scheduling,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 28, pp. 392–403, Aug. 1998
[30] H. Ishibuchi, T. Yoshida, and T. Murata, “Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling,” IEEE Transactions on Evolutionary Computation, vol. 7, pp. 204–223, Apr. 2003
[31] B. B. Li and L. Wang, “A Hybrid Quantum-Inspired Genetic Algorithm for Multiobjective Flow Shop Scheduling,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 37, pp. 576–591, June 2007
[32] F. Zhang, Y. F. Zhang, and A. Y. C. Nee, “Using genetic algorithms in process planning for job shop machining,” IEEE Transactions on Evolutionary Computation, vol. 1, pp. 278–289, Nov. 1997
[33] R. C. CorreAa, A. Ferreira, and P. Rebreyend, “Scheduling multiprocessor tasks with genetic algorithms,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, pp. 825–837, Aug. 1999
[34] S. Hajri, N. Liouane, S. Hammadi, and P. Borne, “A controlled genetic algorithm by fuzzy logic and belief functions for job-shop scheduling,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 30, pp. 812–818, Oct. 2000
[35] M. T. Jensen, “Generating robust and flexible job shop schedules using genetic algorithms,” IEEE Transactions on Evolutionary Computation, vol. 7, pp. 275–288, June 2003
[36] S. S. Sancho and X. Yao, “A hybrid Hopfield network-genetic algorithm approach for the terminal assignment problem,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 34, pp. 2343–2353, Dec. 2004
[37] Z. X. Guo, W. K. Wong, S. Y. S. Leung, J. T. Fan, and S. F. Chan, “A Genetic-Algorithm-Based Optimization Model for Solving the Flexible Assembly Line Balancing Problem With Work Sharing and Workstation Revisiting,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 38, pp. 218–228, Mar. 2008
[38] Y. W. Leung and Y. Wang, “An orthogonal genetic algorithm with quantization for global numerical optimization,” IEEE Transactions on Evolutionary Computation, vol. 5, pp. 41–53, Feb. 2001
[39] J. T. Tsai, T. K. Liu, and J. H. Chou, “Hybrid Taguchi-genetic algorithm for global numerical optimization,” IEEE Transactions on Evolutionary Computation, vol. 8, pp. 365–377, Aug. 2004
[40] W. Zhong, J. Liu, M. Xue, and L. Jiao, “A multiagent genetic algorithm for global numerical optimization,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 34, pp. 1128–1141, Apr. 2004
[41] Z. Tu and Y. Lu, “A robust stochastic genetic algorithm (StGA) for global numerical optimization,” IEEE Transactions on Evolutionary Computation, vol. 8, pp. 456–470, Oct. 2004
[42] W. A. Farag, V. H. Quintana, and G. L. Torres, “A genetic-based neuro-fuzzy approach for modeling and control of dynamical systems” IEEE Transactions on Neural Networks, vol. 9, pp. 756–767, Sep. 1998
[43] R. A. Krohling and J. P. Rey, “Design of optimal disturbance rejection PID controllers using genetic algorithms,” IEEE Transactions on Evolutionary Computation, vol. 5, pp. 78–82, Feb 2001
[44] S. Venkatraman and G. G. Yen, “A Generic Framework for Constrained Optimization Using Genetic Algorithms,” IEEE Transactions on Evolutionary Computation, vol. 9, pp. 424–435, Aug. 2005
[45] M. R. Hsu, W. H. Ho, and J. H. Chou, “Stable and Quadratic Optimal Control for TS Fuzzy-Model-Based Time-Delay Control Systems,” IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 15, pp. 933–944, July 2008
[46] W. H. Ho, J. T. Tsai, and J. H. Chou, “Robust Quadratic-Optimal Control of TS-Fuzzy-Model-Based Dynamic Systems With Both Elemental Parametric Uncertainties and Norm-Bounded Approximation Error,” IEEE Transactions on Fuzzy Systems, vol. 17, pp. 518–531, June2009
[47] H. Ishibuchi, K. Nozaki, N. Yamamoto, and H. Tanaka, “Selecting fuzzy if-then rules for classification problems using genetic algorithms,” IEEE Transactions on Fuzzy Systems, vol. 3, pp. 260–270, Aug. 1995
[48] D. P. Muni, N. R. Pal, and J. Das, “A novel approach to design classifiers using genetic programming,” IEEE Transactions on Evolutionary Computation, vol. 8, pp. 183–196, Apr. 2004
[49] J. Tippayachai, W. Ongsakul, and I. Ngamroo, “Parallel micro genetic algorithm for constrained economic dispatch,” IEEE Transactions on Power Systems, vol. 17, pp. 790–797, Aug. 2002
[50] I. G. Damousis, A. G. Bakirtzis, and P. S. Dokopoulos, “Network-constrained economic dispatch using real-coded genetic algorithm,” IEEE Transactions on Power Systems, vol. 18, pp. 198–205, Feb. 2003
[51] Y. L., G. Li, and Z. B. Xu, “A genetic algorithm for the multiple destination routing problems,” IEEE Transactions on Evolutionary Computation, vol. 2, pp. 150–161, Nov. 1998
[52] Q. Zhang and Y. W. Leung, “An orthogonal genetic algorithm for multimedia multicast routing,” IEEE Transactions on Evolutionary Computation, vol. 3, pp. 53–62, Apr. 1999
[53] F. D. Rango, M. Tropea, A. F. Santamaria, and S. Marano, “Multicast QoS Core-Based Tree Routing Protocol and Genetic Algorithm Over an HAP-Satellite Architecture,” IEEE Transactions on Vehicular Technology, vol. 58, pp. 4447–4461, Oct. 2009
[54] G. Leary, K. Srinivasan, K. Mehta, and K. S. Chatha, “Design of Network-on-Chip Architectures With a Genetic Algorithm-Based Technique,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 17, pp. 674–687, May 2009