TSP 2 Traveling Salesperson Problem

TSP 1
Traveling SALESPERSON PROBLEM
By (Name)
Course
Professor’s Name
Institution
Date

TSP 2
Contents
Executive Summary.............................................................................................................3
Step 1: Identification And Solution Of A Typical Problem................................................4
1.1. Background............................................................................................................4
1.2. Model.....................................................................................................................5
Example solution between cities A, B, C, D, E, F..........................................................6
Step 2: LR On Application Of Selected Typical Model In Design And Analysis Of
Supply Chain...................................................................................................................................6
Application of TSP..........................................................................................................6
1. Vehicle Routing (Vehicle Routing Problem).....................................................6
2. Job scheduling (Job Scheduling Problem).........................................................7
3. Order picking in warehouse logistics (Order Picking Problem)........................8
4. Crew scheduling and interview scheduling (Crew Scheduling Problem)..........9
Similarities and differences between scholarly articles...................................................9
Suitability of the TSP.........................................................................................................11
Limitations of the TSP.......................................................................................................11
Critique of the Travelling Salesman Problem...................................................................12
Step 3: Summary Of Findings............................................................................................13
Conclusion.........................................................................................................................13

TSP 3
Executive Summary
This report identifies a common problem experienced in operations research. The report
provides detailed background information on the problem and provides a typical mathematical
model used in the solution of the problem and uses the model to solve an example. The report
analyses five peer-reviewed articles on the traveling Salesperson problem and summarizes the
findings from the materials.

TSP 4
Traveling Salesperson Problem
Step 1: Identification And Solution Of A Typical Problem
The problem chosen for this report is the Travelling Salesperson Problem (TSP).
1.1. Background
The Travelling Salesperson Problem is one of the most studied and experienced problems
in operations research and optimization. The Travelling Salesperson Problem (TSP) is also
referred to as the Travelling Salesperson problem, and it has been generalized in many cases as
the Travelling Purchaser Problem or the Vehicle routing problem. The TSP is applied in many
applications; its formulation is used in planning, logistics, and manufacturing.
The transportation problem seeks and formulates a question to answer the question; “In
the situation of a given number of cities with given distances between each city and the other,
what is the shortest possible route that can be taken to ensure it visits each city exactly once and
reverts to the starting point?’ (Eremeev & Kovalenko, 2017).
TSP can be formulated as a weighted graph problem by making the cities serve as the
vertices of the graphs and the paths to the towns as edges in the chart with a path's distance
represented by the graph’s height. In formulation, the Graph represents a minimization problem
that starts and ends at a particular vertex after visiting each vertex once. The model generates a
complete graph with all every city connected to another by an edge (Aboudi et al., n.d.).
A TSP can be considered in the perspective of whether it is symmetric or asymmetric
(Toriello & Uhan, 2013). In the case of asymmetric TSP, the distance between two cities is the
same in either direction (Antar & Farkhondeh, 2014). This situation reduces the number of
probable solutions by 50% and forms an undirected graph. In asymmetric TSP, paths have