Traveling Salesman Problem: A Case Study
INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGYPublished 1 August 2012Open access
Leena Jain, Mr. Amit Bhanot
Citations45
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This linear problem solved by open source software is presented for solving traveling salesman problem and assignment based integer linear formulation presented.
Abstract
In this paper assignment based integer linear formulation presented for solving traveling salesman problem. Unfortunately, the assignment model can lead to infeasible solutions. Infeasibility removes by introducing additional constraints. Then this linear problem solved by open source software.
Keywords
Computer ScienceDecision SciencesEngineering
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
Genetic Algorithms in Search, Optimization and Machine Learning
17,773 Citations1988David E. Goldberg, David Robson
OmegaThe multiple traveling salesman problem: an overview of formulations and solution procedures
1,114 Citations2005Tolga Bektaş
Artificial Intelligence ReviewGenetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators
820 Citations1999Pedro Larrañaga, C.M.H. Kuijpers +3 more
This paper presents crossover and mutation operators, developed to tackle the Travelling Salesman Problem with Genetic Algorithms with different representations such as: binary representation, path representation, adjacency representation, ordinal representation and matrix representation.
Transportation ScienceTime Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms
536 Citations1992Chryssi Malandraki, Mark S. Daskin
Mixed integer linear programming formulations of the TDVRP and the TDTSP are presented that treat the travel time functions as step functions that preclude modification of most of the algorithms that have been developed for the vehicle routing problem.
European Journal of Operational ResearchAn efficient genetic algorithm for the traveling salesman problem with precedence constraints
238 Citations2002Chiung Moon, Jong-Soo Kim +2 more
European Journal of Operational ResearchA restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
170 Citations1996Chryssi Malandraki, Robert B. Dial
A restricted DP heuristic (a generalization of the nearest neighbor heuristic) is presented that can include all the above considerations but solves much larger problems but cannot guarantee optimality.
GENETIC ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM USING SEQUENTIAL CONSTRUCTIVE CROSSOVER
137 Citations2010Zakir Hussain Ahmed
Experimental results show that the new crossover operator, Sequential Constructive crossover (SCX), is better than the ERX and GNX for some benchmark TSPLIB instances.
Tsinghua Science & TechnologyTwo-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs
110 Citations2007Chao Ding, Cheng Ye +1 more
Test results demonstrate that the clustering TLGA for large TSPs is more effective and efficient than the classical genetic algorithm.
Computers & Operations ResearchA genetic algorithm with a mixed region search for the asymmetric traveling salesman problem
101 Citations2003Inchan Choi, Seong-In Kim +1 more
It is shown in the article that the size of the infeasible region defined by solutions with subtours dominates that of a feasible region in the asymmetric traveling salesman problem.
Applied OpticsOptical solution for bounded NP-complete problems
63 Citations2007Natan T. Shaked, Stéphane Messika +2 more
A new optical method for solving bounded (input-length-restricted) NP-complete combinatorial problems, chosen to demonstrate the method with an NP- complete problem called the traveling salesman problem (TSP).
Zenodo (CERN European Organization for Nuclear Research)Enhanced Traveling Salesman Problem Solving By Genetic Algorithm Technique (Tspga)
54 Citations2008Buthainah Fahran Al-Dulaimi, Hamza Ali
A software system is proposed to determine the optimum route for a Traveling Salesman Problem using Genetic Algorithm technique that starts from a matrix of the calculated Euclidean distances between the cities to be visited by the traveling salesman and a randomly chosen city order as the initial population.
Transportation ScienceHeuristic Bounds and Test Problem Generation for the Time-Dependent Traveling Salesman Problem
34 Citations1995Russ J. Vander Wiel, Nikolaos V. Sahinidis
A new mixed-integer linear programming (MILP) formulation for the Time-Dependent Traveling Salesman Problem is presented and it is demonstrated that the heuristics can achieve optimal or very good near-optimal solutions on a variety of problem classes with minimal computational effort.
Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004.New operators of genetic algorithms for traveling salesman problem
33 Citations2004Siddheswar Ray, Sanghamitra Bandyopadhyay +1 more
An application of a genetic algorithm to the traveling salesman problem is described and a new knowledge based multiple inversion operator and a neighborhood swapping operator are proposed.
arXiv (Cornell University)The traveling salesman problem: A Linear programming formulation
28 Citations2006Moustapha Diaby
A polynomial-sized linear programming formulation of the Traveling Salesman Problem (TSP) is presented and the proposed linear program is a network flow-based model.
Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators
19 Citations1999P. Larrañaga, C. M. H. Kuijpers +3 more