An Efficient Algorithm for a Travel Itinerary Planner under Time Constraints
Article Sidebar
Main Article Content
Abstract
This article proposed a design and development of an algorithm for a travel itinerary planner which focused on facilitating travelers to reach destinations as much as possible under the time constraints. The proposed algorithm is based on a simulated annealing algorithm (SA) and applies a shortest path search technique (SPS) to increase the efficiency of the algorithm. The performance evaluation of the proposed algorithm is tested on the travel itinerary planner problem under time constraints (TIPP), which is the main problem in this research. In addition, the testing has been extended in the traveling salesman problem (TSP). The evaluation results of TIPP and TSP problems are in the same direction. There are two aspects of evaluation for each problem. The first aspect is to test the elapsed time of algorithms. The experimental results reveal that the proposed algorithm spends less elapsed time than a basic SA, a progressive routing algorithm (PR), and an exhaustive routing algorithm (ER). However, the proposed algorithm is slightly worse than a greedy best first search algorithm (GBFS), which is a high-speed processing algorithm. The second aspect is to test the quality of solution performance. The results indicate that the proposed algorithm provides more quality of the solution than SA and GBFS. However, the developed algorithm is slightly worse than PR and ER, which are algorithms that guarantee to find for an optimal solution. Nevertheless, the developed algorithm spends much less elapsed time.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
Banos, R., Ortega, J., Gil, C., Fernandez, A., & De Toro, F. (2013). A Simulated Annealing-Based Parallel Multi-Objective Approach to Vehicle Routing Problems with Time Windows. Expert Systems with Applications. 40(5): 1696-1707. https://doi.org/10.1016/j.eswa.2012.09.012
Belhaiza, S., Hansen, P., & Laporte, G. (2014). A Hybrid Variable Neighborhood Tabu Search Heuristic for The Vehicle Routing Problem with Multiple Time Windows. Computers & Operations Research. 52: 269-281. https://doi.org/10.1016/j.cor.2013.08.010
Blum, c., & Roli, A. (2003). Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys (CSUR). 35(3): 268-308. https://doi.org/10.1145/937503.937505
Cerny, V. (1985). Thermodynamical Approach to The Traveling Salesman Problem: An Efficient Simulation Algorithm. Journal of Optimization Theory and Applications. 45(1): 41–51. https://doi.org/10.1007/BF00940812
Fang, L., Chen, P., & Liu, S. (2007). Particle Swarm Optimization with Simulated Annealing for TSP. In Proceedings of the 6th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering and Data Bases (pp. 206-210). Corfu Island, Greece.
Garey, M. R., & Johnson, D. S. (2002). Computers and Intractability; A Guide to the Theory of NP-Completeness (Vol. 29). New York: WH Freeman.
Geng, X., Chen, Z., Yang, W., Shi, D., & Zhao, K. (2011). Solving the Traveling Salesman Problem Based on An Adaptive Simulated Annealing Algorithm with Greedy Search. Applied Soft Computing. 11(4): 3680-3689. https://doi.org/10.1016/j.asoc.2011.01.039
Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers & Operations Research. 13(5): 533-549. https://doi.org/10.1016/0305-0548(86)90048-1
Hui, L., & Yonghui, C. (2010). Study of Heuristic Search and Exhaustive Search in Search Algorithms of The Structural Learning. In Proceeding of 2010 Second International Conference on Multi Media and Information Technology (pp.169-171). Kaifeng: China. https://doi.org/10.1109/MMIT.2010.163
Kirkpatrick, S., Gelatt Jr., C.D., & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science. 220(4598): 671–680. https://doi.org/10.1126/science.220.4598.671
Konthaitour. (2019). Tour Chaingmai. [Online]. Available: http://www.konthaitour.com/index.php?lay= show&ac=article&Id=540019445&Ntype=32
Korbua, S. (2013). The Development of a Travel Planner under Time Constraints. (In Thai). Master of Information Science Degree at Suranaree University of Technology.
Leung, C.H. S., Zhang, Z., Zhang, D., Hua, X., & Lim, K. M. (2013). A Meta-Heuristic Algorithm for Heterogeneous Fleet Vehicle Routing Problems with Two-Dimensional Loading Constraints. European Journal of Operational Research. 225(2): 199-210. https://doi.org/10.1016/j.ejor.2012.09.023
Lin, S. W., Vincent, F. Y., & Chou, S. Y. (2009). Solving the Truck and Trailer Routing Problem Based on A Simulated Annealing Heuristic. Computers & Operations Research. 36(5): 1683-1692. https://doi.org/10.1016/j.cor.2008.04.005
Lin, S. W., Vincent, F. Y., & Lu, C. C. (2011). A Simulated Annealing Heuristic for The Truck and Trailer Routing Problem with Time Windows. Expert Systems with Applications. 38(12): 15244-15252. https://doi.org/10.1016/j.eswa.2011.05.075
Maruyama, A., Shibata, N., Murata, Y., Yasumoto, K., & Ito., M. (2004). A Personal Tourism Navigation System to Support Traveling Multiple Destinations with Time Restrictions. In Proceeding of the 18th International Conference of Advanced Information Networking and Applications (AINA) 2004 (pp.18-21). Fukuoka, Japan. https://doi.org/10.1109/AINA.2004.1283747
Misevicius, A. (2015). Using Iterated Tabu Search for the Traveling Salesman Problem. Information Technology and Control. 32(3): 29-40.
Ngamsanit, P., Angskun, T., & Angskun, J. (2017). A Simulated Annealing Algorithm for Travel Itinerary Planning under Time Constraints. (In Thai). Journal of Science and Technology Mahasarakham University. 36(6): 713-727.
Ngamsanit, P., Angskun, T., & Angskun, J. (2009). An Online Trip Planner under Energy and Time Constraints. In Proceeding of the 13th National Computer Science and Engineering Conference (pp.480-486). Bangkok: Thailand.
Papadimitrou, C. H., & Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. New York. Dover Publications Inc.
Sudson, S., Kornwiwat, S., & Sudson, N. (2014). Simulated Annealing (SA) to Vehicle Routing Problems with Soft Time Windows. KKU Engineering Journal. 41(4): 449-461.
Sunstartravel. (2019). Sunstartravel D3. [Online]. Available: http://www.sunstartravel.net/tour-detail.php?id=15.
Vijay, M., & JAGADEESWARI, M. (2012). An Efficient Architecture for Robotic Path Planning. Development (IJECIERD). 2(2): 19-29.
Vincent, F. Y., Lin, S. W., Lee, W., & Ting, C. J. (2010). A Simulated Annealing Heuristic for The Capacitated Location Routing Problem. Computers & Industrial Engineering. 58(2): 288-299. https://doi.org/10.1016/j.cie.2009.10.007
Waters, C. D. J. (1987). A Solution Procedure for The Vehicle Scheduling Problem Based on Iterative Route Improvement. Journal of the Operational Research Society. 38(9): 833–839. https://doi.org/10.1057/jors.1987.137
Wolsey, L. A., & Nemhauser, G. L. (2014). Integer and Combinatorial Optimization. New York. John Wiley & Sons.
Wongjak, A., Siriboon, K., & Kruatrachue, B. (2011). Improve Neighbor Search Ability of Genetic Algorithms Using Particle Swarm Optimization Technique. Information Technology Journal. 7(2): 1-6.
Wu, B., Murata, Y., Shibata, N., Yasumoto, K., & Ito, M. (2009). A Method for Composing Tour Schedules Adaptive to Weather Change. In Proceeding of the Intelligent Vehicles Symposium 2009 IEEE (pp. 1407-1412). Xi’an, China. https://doi.org/10.1109/IVS.2009.5164491
