The heuristics and algorithms

STP Model 1
TSP MODEL
by Student’s Name
Code + Course Name
Professor’s Name
University Name
City, State
Date

STP Model 2
TSP Model
Step one: Identification and solution of a typical problem
1.1 Background
The Traveling Salesperson Problem refers to the challenge of determining the shortest
routes that visit a given set of customers in an area and returns to the initial starting point. The
TSP was formulated or the first time in the year 1930 and is ranked among the most intensive
problems that are studied when it comes to optimization (Brucato 2013). The problem of TPS is
considered very difficult by many people, although there are a number of exact algorithms and
heuristics that have been coined to help in the provision of its solution. The heuristics and
algorithms have been highly instrumental in helping salesmen to solve traveling problems when
they have very many cities to consider (Stanek, Greistorfer, Ladner and Pferschy 2018). The TSP
has, however, proved to be highly instrumental and effective because it has many applications
even when considered in its purest formulation. For instance, it is applicable in logistics,
planning, and also the manufacturing process of microchips (Matai, Singh, and Mittal 2010).
After slight modification, the TSP also qualifies as a sub-problem in other fields of application,
such as DNA sequencing and astronomy (Mo and Xu 2010). Thus the TPS is a critical problem
that is important to understand and advance combinatory optimization problems.
1.2 Model
The proposed model for the Travelling Salesperson Problem (TSP) is the Integer Linear
Programming (ILP) model. The Integer Linear Programing model is a feasibility program, or
mathematical optimization programs where all the variables that are applied are utilized are
restricted to be integers (Ganian, and Ordyniak 2019). The other constraints apart from the
integer constraints in the ILP model and the objective functions are linear. The ILP model is

STP Model 3
particularly used to solve problems in various areas such as vehicle routing, process scheduling,
network hub location, and packaging, among other areas (Pferschy and Staněk 2017). It is thus a
highly effective model that makes it very relevant in addressing the traveling Salesperson
Problem. One unique feature of the ILP model that makes it perfect for the Travelling
Salesperson Problem is that it is NP-complete (Vali and Salimifard 2017). Currently, many
scholars have invested time in understanding and advancing the model more to enhance its
performance. Some of the aspects regarding the model that have been better understood in
contemporary times include restrictions of the number of variables or constraints (Salvador
2010). One of the notable scholarly advancement of the ILP model in the recent past has been the
carried out is the systematic study of the sophistication of ILP through the view of variable
constraints interaction (Ganian and Ordyniak 2019).
In the ILP model, the decision variables, which are a representation of the solution of the
problem, are represented by mathematical symbols. The constraints, the operational
requirements, and the strategic business requirements are modeled using a linear combination of
decision variables in the ILP model (Wiener and Tenbrink 2008). The ILP model utilizes the
objective function, which is a special linear combination of decision variables to model the
specific aspect that the business aims to optimize. The objective functions are optimized in the
ILP model using solutions of inequalities and equations which are obtained using ILP solvers
such as FICO XpressMP (Carroll and Keenan 2019). In the ILP model, the constraints can be
referred to as the limitations that exist on the decision variable. The constraints in the ILP model
are important considerations because they play the role of limiting the decision variables. The
ILP model is, therefore, a good model that can be applied in addressing the TSP (Margot 2010).

STP Model 4
1.3 Solving an example
USING THE ILP (INTEGER LINEAR PROGRAMMING) MODEL
Example
A bread distributor has to distribute bread to six different shops in six different towns and
then go back to his place. The distance from one town to another has been recorded and tabulated
below. It is noted that there is a direct connection from one to any other town of the six, and
every town is visited once during the delivery (Rasmussen 2011). The distributor uses a
motorcycle, which he believes has been consuming a lot of fuel during the previous deliveries.
We wish to calculate the shortest distance that the distributor will use to reduce distance
coverage, thus reducing transportation costs.
Distance between towns, (7 is a replica of 1)
Town(To,
From) 1 2 3 4 5 6
7
0 0 0 0 0 0 0 0
1 0 34 45 24 31 32 0
2 34 0 21 15 34 30 0
3 45 21 0 33 34 24 0
4 24 15 33 0 19 25 0
5 31 34 34 19 0 35 0
6 32 30 24 25 35 0 0
7 0 32 30 24 25 35 0