Transferring Route Plan over Time

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.

Authors:

• Barıs Kocer
• Ahmet Arslan

Keywords:

• genetic algorithms
• transfer learning
• travellingsalesman problem

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).