CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

DNA Algorithm Employing Temperature Gradient for Multiple Traveling Salesperson Problem

by B.S.E.Zoraida, Michael Arock, R.Ponalagusamy
journal cover thumbnail
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 1 - Number 22
Year of Publication: 2010
Authors: B.S.E.Zoraida, Michael Arock, R.Ponalagusamy
10.5120/441-674

B.S.E.Zoraida, Michael Arock, R.Ponalagusamy . DNA Algorithm Employing Temperature Gradient for Multiple Traveling Salesperson Problem. International Journal of Computer Applications. 1, 22 ( February 2010), 59-65. DOI=10.5120/441-674

@article{ 10.5120/441-674,
author = { B.S.E.Zoraida, Michael Arock, R.Ponalagusamy },
title = { DNA Algorithm Employing Temperature Gradient for Multiple Traveling Salesperson Problem },
journal = { International Journal of Computer Applications },
issue_date = { February 2010 },
volume = { 1 },
number = { 22 },
month = { February },
year = { 2010 },
issn = { 0975-8887 },
pages = { 59-65 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume1/number22/441-674/ },
doi = { 10.5120/441-674 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T19:47:50.141148+05:30
%A B.S.E.Zoraida
%A Michael Arock
%A R.Ponalagusamy
%T DNA Algorithm Employing Temperature Gradient for Multiple Traveling Salesperson Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 1
%N 22
%P 59-65
%D 2010
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The biological Deoxyribo Nucleic Acid (DNA) strand is found to be a promising computing unit. An attempt has been made to solve symmetric Multiple Travelling Salesperson Problem (MTSP) with single depot using DNA. In this paper, the thermodynamic properties of DNA have been utilized along with other bio-chemical operations to obtain the optimal solution. Actual distance values are possible to be represented using the thermodynamic properties of DNA. Moreover, the proposed approach can be adopted in solving more real-life applications like Vehicle Routing problems and Scheduling problems, with necessary modifications. In this work, an instance with seven cities and three salespersons is solved using DNA computing. This method exhibits the ability to solve NP-complete problems using molecular computing.

References
  1. Tolga Bektas, 2006. The multiple traveling salesperson problem: an overview of formulations and solution procedures, Omega the International journal of Management Science, 2006, Vol.34, 209 – 219.
  2. Saman Hong and Manfred W. Padberg, 1977. A note on the symmetric multiple traveling salesman problem with fixed charges, JSTOR: Operation Research, Vol. 25, No.5, 871-874.
  3. Donald Sofge, Alan Schultz, Kenneth Dejong, 2002. Evolutionary Computational Approaches to Solving the Multiple Traveling Salesman Problem Using a Neighborhood Attractor Schema, Lecture Notes In Computer Science; Proceedings of the Applications of Evolutionary Computing on EvoWorkshops 2002 EvoCOP, EvoIASP, EvoSTIM/EvoPLAN, Vol. 2279, 153-162.
  4. Pan Junjie, and Wang Dingwei, 2006. An Ant Colony Optimization Algorithm for Multiple Traveling Salesman Problem, Proceedings of the first International conference on innovative computing, Information and Control (ICICIC), IEEE.
  5. Nishanth Chandran, T.T. Narendran, and K. Ganesh, 2006. A clustering approach to solve the multiple traveling salesmen problem, International Journal of Industrial and Sytems Engineering, Vol 1, No. 3, 372-387.
  6. Carter Arthur E., and Ragsdale Cliff T., 2006. A new approach to solving the multiple traveling salesperson problem using genetic algorithms, European journal of operational research, vol. 175, 246-257.
  7. Kenneth C. Gilbert Ruth B. Hofstra, 2007. A New Multiperiod Multiple Traveling Salesman Problem with Heuristic and Application to a Scheduling Problem,Decision sciences, , Vol. 23, Issue 1, pp. 250-259.
  8. Adleman, L., 1994 Molecular computation of solutions to combinatorial problems, Science, vol. 266, 1994, 1021-1029.
  9. Narayanan, A., Zorbalas, S., 1998. DNA algorithms for computing shortest paths, Proceedings of the genentic programming, 718-723.
  10. Yamamoto, M., Kameda, A., Matsuura, N., Shiba, T., Kawazoe, Y., and Ahochi, A., 2002. A separation method for dna computing based on concentration control, New Generation computing, Vol. 20, 251-262
  11. Yamamoto, M., Kameda, A., Matsuura, N., Shiba, T., Kawazoe, Y., and Ahochi, 2002. A., Local search by concentration-controlled DNA computing, International journal of computational intelligence and applications, Vol. 2, 447-455
  12. Lee, J. Y., Shin, S. Y., Park, T.H., Zhang, B.T., 2004 Solving traveling salesman problem with DNA molecules encoding numerical values, Biosystems, Vol. 78, 39-47.
  13. Ibrahim, Z., Tsuboi, Y., Ono, O., Khalid, M., Direct-proportional length-based DNA computing for shortest path problem, International journal of computer science and applications, Vol. 1, 46-60.
  14. Aili Han, 2006. DNA computing model for the 0/1 Knapsack problem, Proceedings of the sixth international conference on Hybrid Intelligent Systems (HIS’06), IEEE.
  15. Zoraida, B.S.E., Arock, M., Ronald, B.S.M., Ponalagusamy. R., 2008. A DNA-based algorithm for Multiple travelling salesperson problem, Proceedings of SCMIS, pp. 559-566.
  16. MC (2009). Molecular Computing. Obtained through the Internet: http://ls11-www.cs.uni-dortmund.de/molcomp/downloads/. [accessed 20/6/2009).
  17. OPC (2009). Oligonucleotide Properties Calculator. Obtained through the Internet: http://www.unc.edu/~cail/biotool/oligo/. [accessed 23/6/2009]
Index Terms

Computer Science
Information Sciences

Keywords

Multiple travelling salesperson DNA computing optimal path DNA operations

Powered by PhDFocusTM