本論文的主要目標為使用A*演算法用於旅遊規劃，首先將最大化的旅遊目標，轉為最小化成本問題，並將A*演算法用於單一目標最佳化，接著藉由時間限制來刪減搜尋區域以及提出以逆向演算法來估測旅遊因素的經驗成本。透過實驗顯示，使用逆向經驗估測後，搜尋所產生的節點數目大幅減少，並且深度愈深時效果愈明顯，在深度為7時，可以減少達200多倍的節點數目以及提升300多倍的搜尋速度，並且找到的旅遊路線其整體熱門度也非常接近於整體熱門度最高的路線；然而透過實驗顯示單一旅遊因素會造成的行車距離過長或是旅遊路線熱門度過低的問題，因此我們提出多重滿意度優化，依據旅行者所設定的「滿意條件」，讓不同的旅遊因素可依據旅行者所設定的「滿意條件」換算為成本，再進行最小化成本搜尋，讓多種旅遊因素可以同時反映在旅遊路線上，藉此找出多目標折衷的最佳化結果。我們透過不滿意度來評估多目標的效果，顯示基於滿意度的多目標最佳化可以大幅度的降低不滿意度。最後我們將加入新的旅遊因素，我們把他稱之為例外。例外可以看做是由於某些特定原因造成旅遊多餘的成本，透過實驗顯示整合異質性的多重滿意度優化可以處理各種例外狀況，在多重、動態目標的旅程規劃問題上具有應用潛力。

Trip planning that may integrate diverse information sources to meet travelers’ multiple goals or preferences has become important for intelligent transportation services. Algorithm A* that was a popular approach for trip planning, but has not been well addressed for multiobjectives issue as well as search efficiency. In this paper, heuristic estimate and multiobjectives optimization for A* search on trip planning are proposed to handle the issues. First, a backward algorithm for estimating the heuristics for A* search was proposed to reduce the search complexity and speed up the search. The Backward heuristic is obtained from the expectation of reward. Experimental show that, the backward heuristic may reduce the number of nodes by 200 times and increase search speed by 300 times at the depth of 7, and the total attraction of the obtained trip is very close to the optimal one. To deal with the issue of multiple objectives, such trip factors as attraction to be maximized need first be converted into costs for minimization according to the satisfaction conditions predefined by the user. All the costs of trip factors, including those for time, distance, attraction and so on, could then be accumulated individually and made use of to meet some criteria, such as the time constraints, while minimized jointly to find the eclectic trips fulfilling traveler’s multiple goals. In the experiments of multiobjective planning it could be shown that, the tradeoff among multiple factors may be achieved, and the proposed optimization may reduce overall dissatisfaction effectively. Furthermore, the proposed scheme is capable of taking the exceptions in trip planning such as traffic jam into account. The extra trip factor may be formulated as an extra cost for minimization and considered during search. It means the approach is flexible not only for heterogeneous objectives but for dynamic objectives, and has great potential in applications of travel service.

[1] P. E. Hart, N. J. Nilsson, and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968.
[2] L. Fu, D. Sun, and L. R. Rilett, "Heuristic shortest path algorithms for transportation applications: State of the art," Computers & Operations Research, vol. 33, no. 11, pp. 3324-3343, 2006/11/01/ 2006.
[3] L. Mandow et al., "A new approach to multiobjective A* search," presented at the Proceedings of the 19th international joint conference on Artificial intelligence, Edinburgh, Scotland, 2005.
[4] W.-m. Gai, Z.-a. Jiang, Y.-f. Deng, J. Li, and Y. Du, "Multiobjective Route Planning Model and Algorithm for Emergency Management," Mathematical Problems in Engineering, vol. 2015, p. 17, 2015, Art. no. 565403.
[5] A. W. Drake, Fundamentals of Applied Probability Theory. Mcgraw-Hill College, 1967.
[6] L. R. Rabiner, "A tutorial on hidden Markov models and selected applications in speech recognition," Proceedings of the IEEE, vol. 77, no. 2, pp. 257-286, 1989.
[7] L. E. Baum and J. A. Eagon, "An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology," (in en), Bull. Amer. Math. Soc., vol. 73, no. 3, pp. 360-363, 1967/05 1967.
[8] T. Tsiligirides, "Heuristic Methods Applied to Orienteering," Journal of the Operational Research Society, vol. 35, no. 9, pp. 797-809, 1984/09/01 1984.
[9] P. Vansteenwegen, W. Souffriau, and D. V. Oudheusden, "The orienteering problem: A survey," European Journal of Operational Research, vol. 209, no. 1, pp. 1-10, 2011/02/16/ 2011.
[10] X. Li, "Multi-day and multi-stay travel planning using geo-tagged photos," presented at the Proceedings of the Second ACM SIGSPATIAL International Workshop on Crowdsourced and Volunteered Geographic Information, Orlando, Florida, 2013.
[11] Z. Friggstad, S. Gollapudi, K. Kollias, T. Sarlos, C. Swamy, and A. Tomkins, "Orienteering Algorithms for Generating Travel Itineraries," presented at the Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, Marina Del Rey, CA, USA, 2018.
[12] P. Mrazovic, J. L. Larriba-Pey, and M. Matskin, "Improving Mobility in Smart Cities with Intelligent Tourist Trip Planning," presented at the 2017 IEEE 41st Annual Computer Software and Applications Conference, Turin, 2017.
[13] G. Chen, S. Wu, J. Zhou, and A. K. H. Tung, "Automatic Itinerary Planningfor Traveling Services," IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 3, pp. 514 - 527, 2014.
[14] P. Bolzoni, S. Helmer, K. Wellenzohn, J. Gamper, and P. Andritsos, "Efficient itinerary planning with category constraints," presented at the Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Dallas, Texas, 2014.
[15] K. H. Lim, J. Chan, S. Karunasekera, and C. Leckie, "Personalized Itinerary Recommendation with Queuing Time Awareness," presented at the Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, Shinjuku, Tokyo, Japan, 2017.
[16] C. Zhang, H. Liang, K. Wang, and J. Sun, "Personalized Trip Recommendation with POI Availability and Uncertain Traveling Time," presented at the Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, Melbourne, Australia, 2015.
[17] E. Palumbo, G. Rizzo, R. Troncy, and E. Baralis, "Predicting Your Next Stop-over from Location-based Social Network Data with Recurrent Neural Networks," in RecTour@RecSys, 2017.
[18] Y. Yao, Z. Peng, B. Xiao, and J. Guan, "An efficient learning-based approach to multi-objective route planning in a smart city," in 2017 IEEE International Conference on Communications (ICC), 2017, pp. 1-6.
[19] D. Quercia, R. Schifanella, and L. M. Aiello, "The Shortest Path to Happiness: Recommending Beautiful, Quiet, and Happy Routes in the City," ArXiv e-prints, Accessed on: July 01, 2014Available: https://ui.adsabs.harvard.edu/#abs/2014arXiv1407.1031Q
[20] X. Wu, H. Guan, Y. Han, and J. Ma, "A tour route planning model for tourism experience utility maximization," Advances in Mechanical Engineering, vol. 9, no. 10, p. 1687814017732309, 2017.