一种基于阿德尔曼-利普顿模型求解带容量车辆路径问题的新型生物启发式计算算法。
A novel bio-heuristic computing algorithm to solve the capacitated vehicle routing problem based on Adleman-Lipton model.
作者信息
Wang Zhaocai, Ren Xiaomin, Ji Zuwen, Huang Wei, Wu Tunhua
机构信息
College of Information, Shanghai Ocean University, Shanghai 201306, PR China.
State Key Laboratory of Simulation and Regulation of River Basin Water Cycle, China Institute of Water Resources and Hydropower Research, Beijing 100048, PR China.
出版信息
Biosystems. 2019 Oct;184:103997. doi: 10.1016/j.biosystems.2019.103997. Epub 2019 Jul 29.
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(n) time complexity. We enrich the application scope of biocomputing, reduce computational complexity, and verify practicability of DNA parallel algorithms through simulations.
作为解决复杂计算问题的潜在手段之一，DNA计算是一个跨学科研究的新领域，涉及计算数学、并行算法、生物信息学。容量受限车辆路径问题是著名的NP难问题之一，该问题包括确定一组相同车辆为一组客户服务的路径，同时使总运输成本最小化。本文基于生物启发式计算模型和DNA分子操作，提出了用于解决容量受限车辆路径问题的并行生物计算算法。我们适当地使用不同的生物链来表示顶点、边、权重，并采用适当的生物操作以O(n)的时间复杂度搜索问题的解。我们拓宽了生物计算的应用范围，降低了计算复杂度，并通过模拟验证了DNA并行算法的实用性。
Zotero 插件