An Efficient Algorithm for a Travel Itinerary Planner under Time Constraints
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
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.
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.
Blum, c., & Roli, A. (2003). Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys (CSUR). 35(3): 268-308.
Cerny, V. (1985). Thermodynamical Approach to The Traveling Salesman Problem: An Efficient Simulation Algorithm. Journal of Optimization Theory and Applications. 45(1): 41–51.
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.
Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers & Operations Research. 13(5): 533-549.
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.
Kirkpatrick, S., Gelatt Jr., C.D., & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science. 220(4598): 671–680.
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.
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.
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.
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.
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.
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.
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.