The TSP problem

The paper "Analysing shortest route problem in Petaling Jaya: A case study" presents a current method to construct the solution on shortest route in Petaling Jaya district area for research staff doing a survey tour. Integer linear programming (ILP), heuristic method and Google Maps were used to analyse the travelling salesman problem (TSP). Result shows that it has agreement with theoretical predictions and significant improvement over previous efforts by researchers.

6p longtimenosee07 29-03-2024 4 2   Download

Lecture Software process improvement: Lesson 45 provide students with knowledge about: review from mid-term to final; software problems; software processes; characteristics of software processes; factors that foster toxic team environment;... Please refer to the detailed content of the lecture!

60p hanlamcoman 26-11-2022 7 1   Download

Theory of Computation: Lecture 33. The main topics covered in this lesson include: TSP problem; polynomial time algorithm; the subset sum problem; NP-completeness; multi-set of positive integers;...

28p andromedashun 26-05-2022 5 1   Download

Theory of Computation: Lecture 34. The main topics covered in this lesson include: three versions of the TSP problem; an approximation algorithm for the TSP problem; space complexity; polynomial time algorithm; the euclidean TSP;...

33p andromedashun 26-05-2022 9 1   Download

Theory of Computation: Lecture 35. The main topics covered in this lesson include: Traveling Salesman Problem (TSP); the metric TSP; approximation algorithm and an approximation algorithm for the TSP problem; space complexity; the PCP theorem and hardness of approximation;...

25p andromedashun 26-05-2022 10 1   Download

In this research, we combine both traveling salesman problem and parcel lockers to increase efficiency in LMD. This method will help to answer the question of how to deliver faster, cheaper cost, more convenient to pick up and be environmentally friendly. The results prove clearly that salesman could reduce 57,8% of total distance, customers to pick-up e-purchased goods from designated 24 hour and we reduces the number of traffic jams and noise associated with transport, and thus reduces emissions.

11p alucardhellsing 04-05-2022 12 2   Download

The Multi-stripe Travelling Salesman Problem (Ms-TSP) is an extension of the Travelling Salesman Problem (TSP). In the q-stripe TSP with q ≥ 1, the objective function sums the costs for traveling from one vertex to each of the next q vertices along the tour. To solve medium to large-sized instances, a metaheuristic approach is proposed. The proposed method has two main components, which are construction and improvement phases. The construction phase generates an initial solution using the Greedy Randomized Adaptive Search Procedure (GRASP).

18p nguathienthan9 08-12-2020 13 2   Download

Order picking in conventional warehouse environments involves determining a sequence in which to visit the unique locations where each part in the order is stored, and thus is often modeled as a traveling salesman problem. With computer tracking of inventories, parts may now be stored in multiple locations, simplifying replenishment of inventory and eliminating the need to reserve space for each item. In this environment, order picking requires choosing a subset of the locations that store an item to collect the required quantity.

17p cherry2708 10-06-2020 31 2   Download

This paper introduces a novel practical variant, namely an open close multiple travelling salesmen problem with single depot (OCMTSP) that concerns the generalization of classical travelling salesman problem (TSP).

16p tohitohi 22-05-2020 25 1   Download

The proposed approach is based on a modified genetic algorithm, which generates an initial population with heuristic solutions obtained from the well-known (LKH) heuristic algorithm for the TSP together with the solution of a mathematical model for the shortest path problem. In addition, two recombination methods and a mutation operator are considered. Computational experiments on benchmark instances show that the proposed algorithm can obtain high-quality solutions within short computing times.

18p toritori 11-05-2020 17 0   Download

The paper discusses the application of hyper populated ant colonies to the well-known traveling salesman problem (TSP). The ant colony optimization (ACO) approach offers reasonably good quality solutions for the TSP, but it suffers from its inherent non-determinism and as a consequence the processing time is unpredictable. The paper tries to mitigate the problem by a substantial increase in the number of used ants.

15p vititan2711 13-08-2019 20 1   Download

A hypothetical problem which we call a “buried treasure problem” is presented where the objective is to locate m objects among N fixed equi-spaced caches in order to minimize a measure of the risk of loss. The general problem is shown to be NPhard. However, a sub problem may be solved as a special class of TSP in O (N log N) time. Several applications are noted.

10p vinguyentuongdanh 20-12-2018 19 0   Download

An efficient decoding algorithm is a crucial element of any statistical machine translation system. Some researchers have noted certain similarities between SMT decoding and the famous Traveling Salesman Problem; in particular (Knight, 1999) has shown that any TSP instance can be mapped to a sub-case of a word-based SMT model, demonstrating NP-hardness of the decoding task. In this paper, we focus on the reverse mapping, showing that any phrase-based SMT decoding problem can be directly reformulated as a TSP.

9p hongphan_1 14-04-2013 56 4   Download

In this paper we consider a combinatorial optimization problem that is similar to the bottleneck traveling salesman problem. We show that an optimal tour for this problem is pyramidal tour (1, 3, 5,…, n,…, 6, 4, 2) or consists of some pyramidal subtours. The above 7methods can be extended to complete bipartite graphs. 1. Problem statement It is well-known that the traveling salesman problem (TSP) is strongly NP-hard (cf. [1], p. 353). But for some special cases of the TSP can be solvable in polynomial time. ...

5p tuanlocmuido 19-12-2012 62 3   Download

This book is a collection of current research in the application of evolutionary algorithms and other optimal algorithms to solving the TSP problem. It brings together researchers with applications in Artificial Immune Systems, Genetic Algorithms, Neural Networks and Differential Evolution Algorithm. Hybrid systems, like Fuzzy Maps, Chaotic Maps and Parallelized TSP are also presented.

0p cucdai_1 22-10-2012 94 6   Download