Traveling Salesperson Problem: Design and Analysis Report

This report delves into the Traveling Salesperson Problem (TSP), a critical model in operations research and optimization. It begins with an executive summary, followed by an in-depth exploration of the TSP, including its background, mathematical modeling, and a practical example solution using an Excel spreadsheet. The report then examines the application of the TSP in supply chain design and analysis, highlighting its relevance in vehicle routing, job scheduling, order picking, and crew scheduling. Furthermore, it analyzes and compares several scholarly articles related to the TSP, discussing similarities, differences, and limitations. The report concludes with a summary of findings and a final conclusion, offering a comprehensive overview of the TSP and its significance in various real-world applications. The assignment meets the requirements of a typical model in the Operations Research field which can be applied to a wide range of supply chain problems, demonstrating the student's ability to formulate a solution for problems which have similar structure to a typical 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

TSP 5
different directions in either direction of a city, and ins some cases, the routes do not exist; this
situation forms a directed graph (Cook et al., 2010). Asymmetrical TSP is witnessed in one-way
streets and airfares.
The TSP is very critical in logistics and transportation planning. TSP functions majorly as
an optimization tool in logistics planning, and it can be applied in conjunction with the
Transportation problem to create the most economical and viable logistics strategies. It is used to
formulate the least-cost transportation/logistics routes and is, therefore, a vital tool for strategic
planners and managers.
1.2. Model
Label the cities with the numbers 1, …, n and define:
Taking distance from city i to city j;
Given the data for cities A, B, C, D, E, F below, obtain the optimal route.
Let the cities be represented by numbers 1, 2, 3, 4, 5 and 6 respectively.
The data is as show;
A B C D E F
A 0 12 29 22 13

TSP 6
B 12 19 3 25
C 29 19 0 21 23
D 22 3 21 0 4
E 13 25 23 4 0
F 24 6 28 5 16
1 2 3 4 5 6
1 0 12 29 22 13 24
2 12 0 19 3 25 6
3 29 19 0 21 23 28
4 22 3 21 0 4 5
5 13 25 23 4 0 16
6 24 6 28 5 16 0
3 2 6 4 5 1 1
19 6 5 4 13 0 47
To obtain the solution, the distance matrix is transferred onto an excel spreadsheet. The
intersection between columns representing cities forms a cell in which the value for distance
between them is represented in a numerical value. The values in the spreadsheet are then
converted into absolute values using the Index function. The data is then analyzed using the
solver add-in which captures the different values between cells representing the distances from
each city to the next. The first solution is obtained using random sequence and the route is
optimized by putting in constraints and setting the values to change as the cells at intersections of
columns and rows. The excel solver is then programmed to run through all the possible
combinations and permutations and present as a solutions the minimized solution. The excel

TSP 7
solver add in then attempts all possible combinations of the route process and gives the answer as
the combination with the minimum total distance.
The excel model gives the optimal route as 3-2-6-4-5-1, with a total travel distance of 47.
This translates to an optimal route C-B-F-D-E-A.
The final solution means that the 6 cities can be visited once in a minimum exertion of
travelling a distance representative of 47 which is the coefficient for time and distance
consumed to visit each city once. The solution implies that for minimum distance travelled, the
travelling should commence at city 3, through city 2, then through city 6 followed by city 4, 5
then 1 before returning back too three. In this way each city is visited at least once in the round
trip.
Step 2: LR On Application Of Selected Typical Model In Design And Analysis Of Supply Chain
Application of TSP
Operations, operations research, and optimization have found the most significant number
of applications for the TSP ranging from logistics, job sequencing, transportation, and strategic
planning all of which need to be optimized to ensure that maximum productivity is realized in
the least amount of time and cost (Woche, 2019). Some of the critical applications of TSP, as
documented by scholars, are as discussed below.
1. Vehicle Routing (Vehicle Routing Problem)
Typically, a supplier has a fleet of vehicles that are expected to supply all the clients at a
frequency high enough to ensure that the customers do not run out of stock. In the market places,

TSP 8
consumers are located at different places with varying stretches of distance. Delivery trucks start
and end their day at the supplier’s base. Ultimately, an optimal route has to be designed, one in
which the delivery will visit each recipient at least once in every trip to deliver their orders.
Without careful planning, the delivery trucks would travel unnecessary distances and end up
increasing fuel consumption and, consequently, the cost of deliveries (Lahrichi et al., 2015).
The TSP model comes in handy to help eliminate this challenge. Using the TSP, logistics
planners and supply chain managers are able to come up with a schedule and route option that
serves to minimize the distance traveled and the cost of delivery (Lenstra & Kan, n.d.). In such a
situation, the TSP shows the planner the most feasible route and schedule trough, which they can
run their deliveries with minimal efforts. The importance of this vital application is the
minimization of time taken to deliver, cost related to delivery, and to improve resource
utilization of the technical and human resources involved in the delivery of orders (Steinerberger,
2015). A great example of vehicle routing in the case of school busses. The route traveled by
each bus has to be designated in such a way that each bus is not overloaded and does not travel
for any time longer than a certain designated policy.
2. Job scheduling (Job Scheduling Problem)
Production and supply chain operations demand strategic planning, considering the
limited resources. There is always a need to optimize the production process by optimizing
individual processes and jobs on the hop floor. The main constraints in the production process
are machines, manpower, and resources allocated. In machine scheduling, a job is made to wait
for arbitrary periods of time before it moves on to the next machine. The waiting period in
detrimental and constitutes inefficiency, considering that ion the real world, there is limited or no
intermediate storage space (Braekers et al., 2011).

TSP 9
The application of TSP in job scheduling assumes that the objective is to minimize total
processing time under the constraints of limited storage on the shop floor (Dasgupta et al., n.d.).
The TSP model for such a situation assumes that machine orders for all the jobs are identical;
this means that the processing order on each machining stage is similar, and hence the analysis is
simplified. The situation is analyzed and solved using the TSP since the machine order may vary
for each job, and each job goes through each machine at least once, and no passing or
intermediate storage is acceptable/allowed (Lenstra & Kan, n.d.).
3. Order picking in warehouse logistics (Order Picking Problem)
The TSP is common in material handling procedures in warehouses (Schalekamp et al.,
2014). In warehousing, it is assumed that an order for a particular set of items stored in the
warehouse is received. A shipping vehicle has to get all the items in the order and deliver them to
the recipient. The delivery vehicle is loaded using indoor mechanized trolleys and vehicles that
collect individual packages from their respective shelves and carry them to the loading zone. The
TSP immediately comes in handy in the designation of optimal routes to be followed by indoor
vehicles and trolleys to collect items from their different points of storage and move them in the
quickest way possible along the shortest route to the loading zone and into the awaiting shipping
vehicle. The distance between two locations or nodes within the warehouse is given as the time
required for a vehicle to move from the home-node to any location or from one node to another.
The challenge of finding the shortest route for the pick-up vehicle in the shortest route can be
handled by the application TSP models.
4. Crew scheduling and interview scheduling (Crew Scheduling Problem)
Crew scheduling faces the TSP in the form of the need to pick up deposits at branch
banks and return them to a central office via messengers. The problem in this scenario is to

TSP 10
determine the route that incurs minimal cost and can be solved by modeling the scenario onto a
TSP model (Laporte, 2010). The interview challenge applies a modified form of TSP abbreviated
as RTSP, and it handles interviews of tour brokers with vending agents in tourism. Each tour
broker is the equivalent of a salesperson who must visit a number of specific vending booths
represented by a number of cities (Shen & Zhao, 2008).
Similarities and differences between scholarly articles
The articles considered in this section are;
i. (Schalekamp, et al., 2014).
ii. (Battarra, et al., 2010).
iii. (Lenstra & Kan, n.d.).
iv. (Matai, et al., 2010)
v. (Lahrichi, et al., 2015).
The articles all converge on the fact that TSP is very critical in operations management.
The authors present similar data on the application of TSP in linear programming, Order picking
problems, interview planning problem, transportation problem, drilling of 3D circuit boards,
crystallography, computer wiring, vehicle routing, clustering data arrays, and job shop
scheduling, (Matai et al., 2010; Lahrichi et al., 2015; Lenstra & Kan, n.d.; Battarra et al., 2010;
Schalekamp et al., 2014).
The authors present similar examples that prove the application of TSP in problem-
solving in situations involving strategic planning, and the use of limited resources to perform
optimally with minimal struggle gives an easy solution (Matai et al., 2010; Lahrichi et al., 2015;

TSP 11
Lenstra & Kan, n.d.; Battarra et al., 2010; Schalekamp et al., 2014). The articles all agree that
TSP is an easy modeling technique to obtain solutions for practical problems.
The articles agree on the possibility and feasibility of using computers to perform this
modeling and obtain optimal solutions for TSP modeling and solutions. They propose and
support the use of programs to obtain solutions for formulated TSP models (Matai et al., 2010;
Lahrichi et al., 2015; Lenstra & Kan, n.d.; Battarra et al., 2010; Schalekamp et al., 2014).
The authors have presented the main problems and challenges that can be solved by the
application and solution of TSP models. According to the five articles, TSP finds application in
main sectors such as logistics, scheduling, shop floor planning, routing and deliveries (Matai et
al., 2010; Lahrichi et al., 2015; Lenstra & Kan, n.d.; Battarra et al., 2010; Schalekamp et al.,
2014).
Lenstra and Rinnoy, in their article, have focused on the simplistic application of the
TSP. Their paper has used an approach of simple but rather unrelated problems that can be
solved and have been solved through the application of TSP. They mean to prove that the
formulation does not have to be used as it is, rather it can be modified and twisted to fit
whichever situation planners deem appropriate. Matai, in his article, insists on having several
versions of the TSP, which are; asymmetric TSP (aTSP), symmetric TSP (sTSP), and multi-TSP
(mTSP). The variation in modeling and formulation gives the TSP more widespread application
while allowing it to be easily tweaked for application in different situations and fields. The
article further details the application of TSP in engineering and computing technology that
further expounds and opens up windows for extended application of the TSP. Although the
different articles present the TSP in varying approaches, they all acknowledge the crosslink and

TSP 12
communication between the different approaches (Matai et al., 2010; Lahrichi et al., 2015;
Lenstra & Kan, n.d.; Battarra et al., 2010; Schalekamp et al., 2014).
Suitability of the TSP
The traveling salesman is a suitable model for handling supply chain problems majorly
because of its wide application and the viability of the solutions and strategies that it bears.
Solutions arrived at using the Travelling Salesman model are always feasible as long as the
planner is careful not to have any inherent errors. Its suitability lies in the fact that its solutions
are already optimized, and no extra effort needs to be put in to optimize the strategies.
The TSP modeling gives an optimal strategy in which limited resources can be managed
to reach each point of need at least once. The end result is the maximization of productivity
accompanied by the minimization of costs and expenditure.
Limitations of the TSP
The TSP is very much time-consuming. Without a computer program, it could take a lot
of time to come to a solution (Mo, 2010). One needs to take time to create a model and a solution
algorithm in which they insert the values to come up with the final solution.
The TSP, when applied in solving real-life situations, will always give the shortest and
cheapest method in theory (Han et al., 2015). In practice, the projected values could vary due to
other factors and inefficiencies on the ground. In addition, the shortest and cheapest method is
not always the best (Ghiani et al., 2012).

TSP 13
Critique of the TSP
The TSP was created with the purpose of standardizing solutions for logistics and supply
chain challenges. However, the modeling has found more applications in more areas than it was
ever anticipated. The field of engineering, Biology chemistry, physics, and computer science has
benefited more than operations research.
The application of TSP and its modeling assumes a perfect world, which is never the case
when it comes to practicality; as such, the applicants of the modeling have found and
implemented tweaks on the modeling to accommodate the realities of the corporate and social
world.
Step 3: Summary Of Findings
Despite the wide range of applications of TSP, there some inherent characteristics of the
same that form a set of advantages and disadvantages. The TSP is comparatively efficient,
especially for few nodes whose TSP can be solved exhaustively, but TSPs are complicated for
many nodes. TSPs performed better in comparison to other models. TSPs can be applied in
varying scenarios, their convergence is definite, but the convergence timing is never certain.
Conclusion
The TSP is a very efficient analytical tool and one that can be applied in very many
scenarios as such. However, it needs modifications and tweaks to be applied if it is to e of any
use to some situations.

TSP 14

TSP 15
References
Aboudi, R. et al., n.d. A mathematical programming model for the development of petroleum
fields and transport systems. European Journal of Operational Research, 43(1), pp. 13-25.
Andez-Salda˜, H. H., 2010. A Sociophysical Application of TSP: The Corporate Vote. In: D.
Davendra, ed. Traveling Salesman Problem, Theory, and Applications. s.l.:InTech, pp. 283-297.
Anon., n.d. Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming). [Online]
Available at: https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/[Accessed 12
March, 2020].
Antar, B. & Farkhondeh, S., 2014. ON THE NEAREST-NEIGHBOR ALGORITHM FOR THE
MEAN-FIELD TRAVELING SALESMAN. Journal of Applied Probability, 51(1), pp. 106-117.
Batara, M., Erdoǧan, G., Laporte, G. & Vigo, D., 2010. The Traveling Salesman Problem with
Pickups, Deliveries, and Handling Costs. Transportation Science, 44(3), pp. 383-399.
Breakers, K., Janssens, G. K. & Caris, A., 2011. Challenges in Managing Empty Container
Movements at Multiple Planning Levels. Transport Reviews, 31(6), pp. 671-708.
Cook, W. J., Espinoza, D. G. & Goycoolea, M., 2010. Generalized Domino-Parity Inequalities
for the Symmetric Traveling Salesman Problem. Mathematics of Operations Research, 35(2), pp.
479-493.
Cvetković, D., Dražić, Z., Kovačević-Vujčić, V. & Čangalović, M., 2018. THE TRAVELING
SALESMAN PROBLEM. Bulletin, Volume 43, pp. 17-26.
Dasgupta, S., Vazirani, U. & Papadimitriou, C., n.d. Dynamic programming. In: Algorithms.
New York: McGraw-Hill Higher Education, pp. 169-199.

TSP 16
Eremeev, A. V. & Kovalenko, Y. V., 2017. ON SOLVING TRAVELLING SALESMAN
PROBLEM WITH VERTEX REQUISITIONS. Yugoslav Journal of Operations Research,
27(4), pp. 415-426.
Ghiani, G., Manni, E. & Thomas, B. W., 2012. A Comparison of Anticipatory Algorithms for the
Dynamic and Stochastic Traveling Salesman Problem. Transportation Science, 46(3), pp. 374-
387.
Han, H.-J., Yu, J.-M. & Lee, D.-H., 2015. Mathematical model and solution algorithms for
selective disassembly sequencing with multiple target components and sequence-dependent
setups. International Journal of Production Research, 51(16), pp. 4997-5010.
Lahrichi, N. et al., 2015. Strategic analysis of the dairy transportation problem. The Journal of
the Operational Research Society, 66(1), pp. 44-56.
Laporte, G., 2010. A Concise Guide to the Traveling Salesman Problem. The Journal of the
Operational Research Society, 61(1), pp. 35-40.
Lenstra, J. K. & Kan, A. H. G. R., n.d. Some Simple Applications of the Travelling Salesman
Problem. Operational Research Quarterly.
Mo, Y.-. B., 2010. The Advantage of Intelligent Algorithms for TSP. In: D. Davendra, ed.
Traveling Salesman Problem, Theory, and Applications. Guangxi, China: InTech, pp. 26-45.
Schalekamp, F., Williamson, D. P. & Zuylen, A. v., 2014. 2-Matchings, the Traveling Salesman
Problem, and the Suntour LP: A Proof of the Boyd- Carr Conjecture. Mathematics of Operations
Research, 39(2), pp. 403-417.

TSP 17
Shen, Z. & Zhao, Y., 2008. Niche Pseudo-Parallel Genetic Algorithms for Path Optimization of
Autonomous Mobile Robot - A Specific Application of TSP. In: F. Greco, ed. Traveling
Salesman Problem. s.l.: In Tech, pp. 174-182.
Steinberger, S., 2015. NEW BOUNDS FOR THE TRAVELING SALESMAN CONSTANT.
Advances in Applied Probability, 47(1), pp. 27-36.
Toriello, A., Haskell, W. B. & Poremba, M., 2014. A Dynamic Traveling Salesman Problem
with Stochastic Arc Costs. Operations Research, 62(5), pp. 1107-1125.
Toriello, A. & Uhan, N. A., 2013. Technical Note—On Traveling Salesman Games with
Asymmetric Costs. Operations Research, 61(6), pp. 1429-1434.
Woche, C., 2019. Model and solution of the Traveling Salesman Problem with Python and
Pyomo. [Online]
Available at:
https://optimization.mccormick.northwestern.edu/index.php/Traveling_salesman_problems[Acce
ssed 12 March, 2020].