The Traveling Salesman Problem (TSP): A Spatial Navigation Task for Rats.
Ontology highlight
ABSTRACT:
SUBMITTER: Blaser RE
PROVIDER: S-EPMC8276063 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP) arising from a number of real-life applications. In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP. For this purpose, we first investigate a technique to convert a CTSP instance to a TSP and then apply powerful TSP solvers (including exact and heuristic solvers) to solve the resulting TSP instance. We want to answer the following questions: How do state-of-the-art TSP solvers perform on clustered instances converted from the CTSP? Do state-of-the-art TSP solvers compete well with the best performing methods specifically designed for the CTSP? For this purpose, we present intensive computational experiments on various benchmark instances to draw conclusions.
| S-EPMC9202618 | biostudies-literature
Project description:Regarding climate change and energy resource problems, cargo movement in the urban environment is essential to shift to a more sustainable mode. As cities seek to slash transport-related emissions and tackle traffic congestion, the cargo bike is showing itself to be an attractive and versatile last-mile delivery alternative. To this end, this article presents a series of datasets for the Electric Capacitated Travelling Salesman Problem (EC-TSP). This problem has been built for modeling and solving the e-cargo bike parcel distribution problem in urban environments. For the design of these datasets, real geographical data have been used that are in the city centers of Athens, Thessaloniki, Patra, and Larisa in Greece. These datasets have been used for the assessment of e-cargo bikes versus typical delivery vans in terms of operational efficiency and CO2e emissions. The entire benchmark is composed of 9 instances comprised of 14-29 nodes each. The datasets are publicly available for use and modification.
| S-EPMC10430151 | biostudies-literature
Project description:The Standard Genetic Code (SGC) is robust to mutational errors such that frequently occurring mutations minimally alter the physio-chemistry of amino acids. The apparent correlation between the evolutionary distances among codons and the physio-chemical distances among their cognate amino acids suggests an early co-diversification between the codons and amino acids. Here we formulated the co-minimization of evolutionary distances between codons and physio-chemical distances between amino acids as a Traveling Salesman Problem (TSP) and solved it with a Hopfield neural network. In this unsupervised learning algorithm, macromolecules (e.g., tRNAs and aminoacyl-tRNA synthetases) associating codons with amino acids were considered biological analogs of Hopfield neurons associating "tour cities" with "tour positions". The Hopfield network efficiently yielded an abundance of genetic codes that were more error-minimizing than SGC and could thus be used to design artificial genetic codes. We further argue that as a self-optimization algorithm, the Hopfield neural network provides a model of origin of SGC and other adaptive molecular systems through evolutionary learning.
| S-EPMC6816573 | biostudies-other
Project description:The fruit fly optimization algorithm (FOA) is a newly developed bio-inspired algorithm. The continuous variant version of FOA has been proven to be a powerful evolutionary approach to determining the optima of a numerical function on a continuous definition domain. In this study, a discrete FOA (DFOA) is developed and applied to the traveling salesman problem (TSP), a common combinatorial problem. In the DFOA, the TSP tour is represented by an ordering of city indices, and the bio-inspired meta-heuristic search processes are executed with two elaborately designed main procedures: the smelling and tasting processes. In the smelling process, an effective crossover operator is used by the fruit fly group to search for the neighbors of the best-known swarm location. During the tasting process, an edge intersection elimination (EXE) operator is designed to improve the neighbors of the non-optimum food location in order to enhance the exploration performance of the DFOA. In addition, benchmark instances from the TSPLIB are classified in order to test the searching ability of the proposed algorithm. Furthermore, the effectiveness of the proposed DFOA is compared to that of other meta-heuristic algorithms. The results indicate that the proposed DFOA can be effectively used to solve TSPs, especially large-scale problems.
| S-EPMC5094794 | biostudies-literature
Project description:In the process of solving the Traveling Salesman Problem (TSP), both Ant Colony Optimization and simulated annealing exhibit different limitations depending on the dataset. This article aims to address these limitations by improving and combining these two algorithms using the clustering method. The problems tackled include Ant Colony Optimization's susceptibility to stagnation, slow convergence, excessive computations, and local optima, as well as simulated annealing's slow convergence and limited local search capability. By conducting tests on various TSPLIB datasets, the algorithm proposed in this article demonstrates improved convergence speed and solution quality compared to traditional algorithms. Furthermore, it exhibits certain advantages over other existing improved algorithms. Finally, this article applies this algorithm to logistics transportation, yielding excellent results.
| S-EPMC10557949 | biostudies-literature
Project description:As of May 2014 there were more than 100,000 patients on the waiting list for a kidney transplant from a deceased donor. Although the preferred treatment is a kidney transplant, every year there are fewer donors than new patients, so the wait for a transplant continues to grow. To address this shortage, kidney paired donation (KPD) programs allow patients with living but biologically incompatible donors to exchange donors through cycles or chains initiated by altruistic (nondirected) donors, thereby increasing the supply of kidneys in the system. In many KPD programs a centralized algorithm determines which exchanges will take place to maximize the total number of transplants performed. This optimization problem has proven challenging both in theory, because it is NP-hard, and in practice, because the algorithms previously used were unable to optimally search over all long chains. We give two new algorithms that use integer programming to optimally solve this problem, one of which is inspired by the techniques used to solve the traveling salesman problem. These algorithms provide the tools needed to find optimal solutions in practice.
| S-EPMC4311855 | biostudies-other
Project description:Humans need to solve computationally intractable problems such as visual search, categorization, and simultaneous learning and acting, yet an increasing body of evidence suggests that their solutions to instantiations of these problems are near optimal. Computational complexity advances an explanation to this apparent paradox: (1) only a small portion of instances of such problems are actually hard, and (2) successful heuristics exploit structural properties of the typical instance to selectively improve parts that are likely to be sub-optimal. We hypothesize that these two ideas largely account for the good performance of humans on computationally hard problems. We tested part of this hypothesis by studying the solutions of 28 participants to 28 instances of the Euclidean Traveling Salesman Problem (TSP). Participants were provided feedback on the cost of their solutions and were allowed unlimited solution attempts (trials). We found a significant improvement between the first and last trials and that solutions are significantly different from random tours that follow the convex hull and do not have self-crossings. More importantly, we found that participants modified their current better solutions in such a way that edges belonging to the optimal solution ("good" edges) were significantly more likely to stay than other edges ("bad" edges), a hallmark of structural exploitation. We found, however, that more trials harmed the participants' ability to tell good from bad edges, suggesting that after too many trials the participants "ran out of ideas." In sum, we provide the first demonstration of significant performance improvement on the TSP under repetition and feedback and evidence that human problem-solving may exploit the structure of hard problems paralleling behavior of state-of-the-art heuristics.
| S-EPMC2912227 | biostudies-literature
Project description:We studied two problems called the Traveling Repairman Problem (TRPTW) and Traveling Salesman Problem (TSPTW) with time windows. The TRPTW wants to minimize the sum of travel durations between a depot and customer locations, while the TSPTW aims to minimize the total time to visit all customers. In these two problems, the deliveries are made during a specific time window given by the customers. The difference between the TRPTW and TSPTW is that the TRPTW takes a customer-oriented view, whereas the TSPTW is server-oriented. Existing algorithms have been developed for solving two problems independently in the literature. However, the literature does not have an algorithm that simultaneously solves two problems. Multifactorial Evolutionary Algorithm (MFEA) is a variant of the Evolutionary Algorithm (EA), aiming to solve multiple factorial tasks simultaneously. The main advantage of the approach is to allow transferrable knowledge between tasks. Therefore, it can improve the solution quality for multitasks. This article presents an efficient algorithm that combines the MFEA framework and Randomized Variable Neighborhood Search (RVNS) to solve two problems simultaneously. The proposed algorithm has transferrable knowledge between tasks from the MFEA and the ability to exploit good solution space from RVNS. The proposed algorithm is compared directly to the state-of-the-art MFEA on numerous datasets. Experimental results show the proposed algorithm outperforms the state-of-the-art MFEA in many cases. In addition, it finds several new best-known solutions.
| S-EPMC10280250 | biostudies-literature
Project description:In this work, we proposed a hybrid pointer network (HPN), an end-to-end deep reinforcement learning architecture is provided to tackle the travelling salesman problem (TSP). HPN builds upon graph pointer networks, an extension of pointer networks with an additional graph embedding layer. HPN combines the graph embedding layer with the transformer's encoder to produce multiple embeddings for the feature context. We conducted extensive experimental work to compare HPN and Graph pointer network (GPN). For the sack of fairness, we used the same setting as proposed in GPN paper. The experimental results show that our network significantly outperforms the original graph pointer network for small and large-scale problems. For example, it reduced the cost for travelling salesman problems with 50 cities/nodes (TSP50) from 5.959 to 5.706 without utilizing 2opt. Moreover, we solved benchmark instances of variable sizes using HPN and GPN. The cost of the solutions and the testing times are compared using Linear mixed effect models. We found that our model yields statistically significant better solutions in terms of the total trip cost. We make our data, models, and code publicly available https://github.com/AhmedStohy/Hybrid-Pointer-Networks.
| S-EPMC8670669 | biostudies-literature
Project description:Improving the effectiveness of route planning, especially in road transport deliveries is a challenge we need to face in the context of advancing climate change and the sustainable development goals. The main aim of the paper is to demonstrate the above average and utilitarian significance of the multiple probabilistic traveling salesman problem (MPTSP) in the coordination and modeling of sustainable product transportation, which is a novelty at the theoretical, conceptual, methodological and empirical level. We propose a new, hybrid algorithm of solving MPTSP instances (it connects harmony search, k-means and 2-opt), which can be successfully used in economic practice for coordination and modeling of Industry 4.0. The effectiveness of proposed approach is tested using a case study of drugs distribution services and datasets obtained from the transportation enterprise located in Poland. The study focuses on the issue of planning routes, with particular emphasis on the changing demand of customers. It should be stressed that this work may be of interest to researchers but also to management practitioners. The value added of this research lies in the innovative modeling the coordination of sustainable drug transportation as an instance of MPTSP and proposing an effective method to solve it. The main research results confirm that proposed method contributes to overall sustainability of studied supply chain.
| S-EPMC7993843 | biostudies-literature