Transferring Route Plan over Time

Authors: Barıs Kocer, Ahmet Arslan

Abstract:

Travelling salesman problem (TSP) is a combinational optimization problem and solution approaches have been applied many real world problems. Pure TSP assumes the cities to visit are fixed in time and thus solutions are created to find shortest path according to these point. But some of the points are canceled to visit in time. If the problem is not time crucial it is not important to determine new routing plan but if the points are changing rapidly and time is necessary do decide a new route plan a new approach should be applied in such cases. We developed a route plan transfer method based on transfer learning and we achieved high performance against determining a new model from scratch in every change.

Keywords: genetic algorithms, transfer learning, travellingsalesman problem

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072676

References:

[1] Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130.
[2] Hal Daum'eIII and Daniel Marcu. Domain adaptation for statistical classifiers. Journal of Artificial Intelligence Research, 26:101-126, 2006.
[3] H. Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Inference, 90:227-244, 2000.
[4] Thrun, S. B. and Mitchell, T. M. 1993 Lifelong Robot Learning. Technical Report. UMI Order Number: IAI-TR-93-7., University of Bonn.
[5] G.B. Dantzig, D.R. Fulkerson, S.M. Johnson, Solution of a large-scale traveling-salesman problem, Oper. Res. 2 (1954) 393-410.
[6] E. Balas, N. Christofids, A restricted Lagrangian approach to the traveling salesman problem, Math. Program. 21 (1981) 19-46.
[7] M. Grötschel, O. Holland, Solution of large-scale symmetric traveling salesman problems, Math. Program. 51 (1991) 141-202.
[8] F. Glover, Artificial intelligence, heuristic frameworks and Tabu search, Manag. Decis. Econom. 11 (1990).
[9] J.J. Hopfield, D.W. Tank, Neural computation of decisions in optimization problems, Biol. Cybernet. 52 (1985).
[10] P. Jog, J.Y. Suh, D. Van Gucht, The effect of population size, heuristic crossover and local improvement on a genetic algorithm for the traveling salesman problem, in: Proceedings of the Third International Conference on Genetic Algorithms and their Applications, 1989, pp. 110-115.
[11] J.J. Grefenstette, R. Gopal, B. Rosimaita, D. Van Gucht, Genetic algorithms for the traveling salesman problem, in: Proceedings of the International Conference on Genetic Algorithms and their Applications, 1985, pp. 160-168.
[12] H.D. Nguyen, I. Yoshihara, K. Yamamori, M. Yasunaga, Implementation of an effective hybrid GA for large-scale traveling salesman problems, IEEETrans. Syst. Man Cybern. B 37 (2007) 92-99.
[13] B. Roark and M. Bacchiani. 2003. Supervised and unsupervised PCFG adaptation to novel domains. In HLT-NAACL.
[14] R. Florian, H. Hassan, A.Ittycheriah, H. Jing, N. Kambhatla, X. Luo, N. Nicolov, and S. Roukos. 2004. A statistical model for multilingual entity detection and tracking. In of HLT-NAACL.
[15] Chelba and A. Acero. 2004. Adaptation of maximum entropy capitalizer: Little data can help a lot. In EMNLP.
[16] Konidaris, G. and Barto, A. 2007. Building portable options: skill transfer in reinforcement learning. In Proceedings of the 20th international Joint Conference on Artifical intelligence (Hyderabad, India, January 06 - 12, 2007). R. Sangal, H. Mehta, and R. K. Bagga, Eds. Ijcai Conference On Artificial Intelligence. Morgan Kaufmann Publishers, San Francisco, CA, 895-900.
[17] Cohen, P. R., Chang, Y., and Morrison, C. T. 2007. Learning and transferring action schemas. In Proceedings of the 20th international Joint Conference on Artifical intelligence (Hyderabad, India, January 06 - 12, 2007). R. Sangal, H. Mehta, and R. K. Bagga, Eds. International Joint Conference On Artificial Intelligence. Morgan Kaufmann Publishers, San Francisco, CA, 720-725.
[18] Fernández, S., Aler, R., and Borrajo, D. 2007. Transferring learned control-knowledge between planners. In Proceedings of the 20th international Joint Conference on Artifical intelligence (Hyderabad, India, January 06 - 12, 2007). R. Sangal, H. Mehta, and R. K. Bagga, Eds. International Joint Conference On Artificial Intelligence. Morgan Kaufmann Publishers, San Francisco, CA, 1885-1890.
[19] Pratt, L. Y. 1993. Discriminability-Based Transfer between Neural Networks. In Advances in Neural information Processing Systems 5,
[NIPS Conference] (November 30 - December 03, 1992). S. J. Hanson, J. D. Cowan, and C. L. Giles, Eds. Morgan Kaufmann Publishers, San Francisco, CA, 204-211.
[20] Caruana, R., Multitask Learning: A Knowledge-Based Source of Inductive Bias," Proceedings of the 10th International Conference on Machine Learning, ML-93, University of Massachusetts, Amherst, 1993, pp. 41-48.
[21] R. Caruana. Multi-task learning. Machine Learning, pages 41-75, 1997.
[22] Mihalkova, L., Huynh, T., and Mooney, R. J. 2007. Mapping and revising Markov logic networks for transfer learning. In Proceedings of the 22nd National Conference on Artificial intelligence - Volume 1 (Vancouver, British Columbia, Canada, July 22 - 26, 2007). A. Cohn, Ed. Aaai Conference On Artificial Intelligence. AAAI Press, 608-614.
[23] Zheng, V. W., Xiang, E. W., Yang, Q., and Shen, D. 2008. Transferring localization models over time. In Proceedings of the 23rd National Conference on Artificial intelligence - Volume 3 (Chicago, Illinois, July 13 - 17, 2008). A. Cohn, Ed. Aaai Conference On Artificial Intelligence. AAAI Press, 1421-1426.
[24] Gupta, R. and Ratinov, L. 2008. Text categorization with knowledge transfer from heterogeneous data sources. In Proceedings of the 23rd National Conference on Artificial intelligence - Volume 2 (Chicago, Illinois, July 13 - 17, 2008). A. Cohn, Ed. Aaai Conference On Artificial Intelligence. AAAI Press, 842-847.
[25] Ling, X., Xue, G., Dai, W., Jiang, Y., Yang, Q., and Yu, Y. 2008. Can chinese web pages be classified with english data source?. In Proceeding of the 17th international Conference on World Wide Web (Beijing, China, April 21 - 25, 2008). WWW '08. ACM, New York, NY, 969-978.
[26] Sun, Z., Chen, Y., Qi, J., and Liu, J. 2008. Adaptive Localization through Transfer Learning in Indoor Wi-Fi Environment. In Proceedings of the 2008 Seventh international Conference on Machine Learning and Applications (December 11 - 13, 2008). ICMLA. IEEE Computer Society, Washington, DC, 331-336. DOI= http://dx.doi.org/10.1109/ICMLA.2008.53
[27] Thrun, S. B. and Mitchell, T. M. 1993 Lifelong Robot Learning. Technical Report. UMI Order Number: IAI-TR-93-7., University of Bonn.
[28] A. Farhadi, D. Forsyth, and R. White. Transfer learning in sign language.In CVPR, 2007.
[29] A. Quattoni, M. Collins, and T. Darrell. Transfer learning for image classification with sparse prototype representations. In CVPR, 2008.
[30] Koçer, B., Arslan, A. 2010. Genetic Transfer Learning. Expert System with Application vol. 37. 6997 - 7002
[31] Davis, L. (1985). Job shop scheduling with genetic algorithms. In Proceedings of an international conference on genetic algorithms and their applications (pp. 136-140).