Solving the clustered traveling salesman problem with d-relaxed priority rule
The Clustered Traveling Salesman Problem with a Prespecified Order on the Clusters, a variant of the well-known traveling salesman problem is studied in literature. In this problem, delivery locations are divided into clusters with different urgency levels and more urgent locations must be visited before less urgent ones. However, this could lead to an inefficient route in terms of traveling cost. This priority-oriented constraint can be relaxed by a rule called d-relaxed priority that provides a trade-off between transportation cost and emergency level. Our research proposes two approaches to solve the problem with d-relaxed priority rule. We improve the mathematical formulation proposed in the literature to construct an exact solution method. A meta-heuristic method based on the framework of Iterated Local Search with problem-tailored operators is also introduced to find approximate solutions. Experimental results show the effectiveness of our methods.
Code (1)
Tasks
Traveling Salesman ProblemSimilar Papers 제목 키워드 기반
Solving the Clustered Traveling Salesman Problem via TSP methods
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…
Traveling Salesman ProblemSolving Traveling Salesman Problem by Marker Method
In this paper we use marker method and propose a new mutation operator that selects the nearest neighbor among all near neighbors solving Traveling Salesman Problem.
Traveling Salesman ProblemNew mechanism of combination crossover operators in genetic algorithm for solving the traveling salesman problem
Traveling salesman problem (TSP) is a well-known in computing field. There are many researches to improve the genetic algorithm for solving TSP. In this paper, we propose two new crossover operators and new mechanism of …
Traveling Salesman ProblemAMR-to-text generation as a Traveling Salesman Problem
The task of AMR-to-text generation is to generate grammatical text that sustains the semantic meaning for a given AMR graph. We at- tack the task by first partitioning the AMR graph into smaller fragments, and then gener…
AMR-to-Text GenerationText GenerationTranslationTraveling Salesman ProblemSteiner Traveling Salesman Problem with Quantum Annealing
The Steiner Traveling Salesman Problem (STSP) is a variant of the classical Traveling Salesman Problem. The STSP involves incorporating steiner nodes, which are extra nodes not originally part of the required visit set b…
Traveling Salesman Problem