DNA computing, as one of potential means to solve complicated computational problems, is a new field of interdisciplinary research, including computational mathematics, parallel algorithms, bioinformatics. Capacitated vehicle routing problem is one of famous NP-hard problems, which includes determining the path of a group same vehicles serving a set of clients, while minimizing the total transportation cost. Based on the bio-heuristic computing model and DNA molecular manipulations, parallel biocomputing algorithms for solving capacitated vehicle routing problem are proposed in this paper. We appropriately use different biological chains to mean vertices, edges, weights, and adopt appropriate biological operations to search the solutions of the problem with O(n2) time complexity. We enrich the application scope of biocomputing, reduce computational complexity, and verify practicability of DNA parallel algorithms through simulations.
Keywords: Adleman–Lipton model; Capacitated vehicle routing problem; DNA computing; NP-hard problem.
Copyright © 2019 Elsevier B.V. All rights reserved.