Exploring the Potential of DNA Computing for Complex Big Data Problems: A Case Study on the Traveling Car Renter...

Area of Science:

• Computational Biology
• Operations Research
• Bioinformatics

Background:

• The Traveling Car Renter Problem (TCRP) is an NP-hard optimization problem, a variant of the Traveling Salesman Problem (TSP).
• Traditional computational methods struggle with the complexity of NP-hard problems.
• DNA computing offers a powerful alternative for solving complex computational problems due to its inherent parallelism.

Purpose of the Study:

• To develop and present a DNA algorithm for efficiently solving the Traveling Car Renter Problem (TCRP).
• To minimize cumulative operating costs in TCRP solutions.
• To demonstrate the potential of DNA computing for large-scale, intricate problems.

Main Methods:

• A DNA algorithm based on the Adleman-Lipton model was designed for TCRP.
• The algorithm involves fundamental steps: coding, interaction, and extraction.
• Simulation experiments were conducted to compute and validate TCRP solutions.

Main Results:

• The proposed DNA algorithm achieves a time complexity of O(n^2m) for TCRP with n cities and m car types.
• Simulation results demonstrate the algorithm's effectiveness in finding solutions for TCRP instances.
• The computed solutions were compared favorably with those from alternative algorithms.

Conclusions:

• DNA computing presents a viable and efficient approach for solving the Traveling Car Renter Problem (TCRP).
• The proposed algorithm highlights the potential of DNA computing as a parallel processing paradigm.
• This method can be extended to address more complex and larger-scale optimization challenges.