Travelling Salesperson Problem Assessment Answer

Problem

A delivery man in an e-commerce company delivers products to customers in a defined territory on a daily basis that has been allotted to him. Today he has assigned deliveries in a specified area in such a way that he must visit all of the points given in the territory while incurring the fewest possible expenses for travel. Determine the lowest possible cost of the trip. 

The location where the products are to be dropped off by the delivery man is depicted in the following figure: 

The challenge of the travelling delivery man is to visit all the points in that particular territory while incurring the minimum cost for the whole trip of delivering products to all houses in that territory. 

Let's say the houses are 1, 2, 3, 4 where the cost (C) represents the amount of money needed to start from 1 point and end at 1 point. The problem of the travelling delivery man is to find a path that begins and ends at 1 and visits all of the points while spending the least amount of cost possible. 

Model Used

We are using the Travelling Salesperson Problem (TSP) paradigm to resolve this issue. 

The travelling salesman problem (TSP) is an algorithmic challenge that involves figuring out the shortest path between a number of necessary points and locations. The TSP aims to cover as much ground as possible in the shortest amount of time. The points in the problem specification correspond to the cities that a salesperson might visit. The goal of the salesperson is to reduce the distance travelled and travel costs as much as is practical. (Larranaga et al. 1999) 

Objectives of TSP

The following is a list of the primary objective functions that have been expressed in the literature on the TSP:

(1) To minimise the total distance travelled (or to minimise total travel time spent on the stations). 

(2) To minimise total cost of travelling between the stations and cost of waiting before services.

(3) To minimise total time passed from station to station (tour duration). 

The Traveling Salesman Problem (TSP) refers to the challenge of determining the path that an individual should take given a list of specific destinations in order to travel quickly and effectively. There is a well-known algorithmic challenge that needs to be solved in the fields of computer science and operations research. (Langevin et al. 1990) 

Constraints

The optimal approach is the one that takes the least amount of travel time and cash outlay, and this is a challenge that mathematicians and computer scientists have been working on for decades. 

Solution Of Problem 

Calculation of travel cost between all the points 1 to 4 as per the figure given in the problem: 

You can see in the Table, that the cost from points 1 to 1 denoted as Not Applicable (NA), then travel cost from 1 to 2 is 10, 1 to 3 is 15 and 1 to 4 is 20. Using this criterion, I have made this table to determine which path is efficient for the delivery man that involves minimum cost. 

1. If we start from 1 point, the minimum travel cost to reach another point is 2 = 10. (Highlighted)

Now, select minimum cost area reachable from point 2, which is 4 = 3 (Highlighted). As minimum cost is 10 here but we have to complete all points and then come to 1 point in the end. So we cannot select the 1 point and second minimum point is 4. 

Now, select the minimum cost area reachable from point 4 is 3 = 30 (Highlighted), using the same criterion. 

Now, all points are completed. We have to go again to point 1 from point 3 to complete the journey. The travel cost from point 3 to point 1 is 15 (Highlighted)

To solve this problem we will use Greedy algorithm. A greedy algorithm will always select the option that provides the greatest benefit at the given time. This indicates that it makes a decision that is locally optimal in the expectation that this decision will lead to a decision that is globally optimal. The Greedy algorithm can never go back and change its mind, it only gets one chance to compute the solution that will bring about the best possible outcome. 

The complexity of the greedy algorithm in terms of computing is given as O(N 2 log2(N)). 

Given a two-dimensional matrix denoted by tsp[][, in which each row contains an array of the distances from the household identified by the index to all of the other cities, and where a value of 0 indicates that there is no possible route between the two cities identified by the index. The mission is to print the lowest possible cost using the TSP cycle. 

To solve this TSP problem, we will use a greedy strategy: 

tsp[][] = {{-1, 10, 15, 20},  
{10, -1, 35, 25},  
{15, 35, -1, 30},  
{20, 25, 30, -1}};  

Using a greedy strategy, the minimum travel cost =

1 -> 2 = 10  
2 -> 4 = 25  
4 -> 3 = 30  
3 -> 1 = 15  
(All the costs are taken from the given 2D Array)  

= 1-2-4-3 = 10+25+30+15 = 80 

Literature Review

The TSP is notable not only due to the fact that it can be applied in the real world, but also due to the fact that over the course of the past few decades, study into the TSP has been the impetus for numerous major advances in the theory of optimization. (Dahiya et al.2018) The transportation scheduling problem was generalised into the vehicle routing problem (VRP), which required the use of numerous different routes due to the limits that were introduced into the problem (TSP). 

The TSP mandates that the origin and destination of the route with the shortest distance through n nodes be the same city. Each node can only be reached by following this path in its entirety. Academics in supply chain management, operations research, computer science, and a variety of other subjects, among others, have focused a significant amount of their research efforts on the Travelling Salesman Problem (TSP). It is quite possible that the world's most well-known combinatorial optimization problem is this one. (Laporte et al. 1990) 

Given a list of cities to visit and the distance that separates each pair of cities, the goal of the travelling salesman issue is to determine the route that will cover all of the cities in the shortest period of time before bringing the salesperson back to the starting point. Even if describing the problem is easy, finding a solution to it is a lot more difficult. It is believed that the Travelling Salesman Problem is an optimization issue that is NP-hard, which means that it cannot be solved in a polynomial amount of time. The search space for this problem is quite large. It is a problem that, in this day and age, the field of computer science can consider to be one of the most fundamental problems. (Padberg et al. 1991) The concept of the "travelling salesman dilemma" is being utilised in a diverse assortment of contexts at the present time. It has a wide variety of uses, some of which include vehicle routing, chip fabrication, GSM packet routing, drilling printed circuit boards, and other processes similar to those mentioned. To put it another way, let us assume that we have a collection of n cities and that we are able to determine n minus one different routes that connect all of those n cities. Finding the path that covers the shortest amount of ground might be challenging for salesmen who are always on the road. 

To review more about TSP, I go through various research papers like Flexibility analysis in Supply chain Management – Application to the TSP (Di Pretoro et al. 2021), The travelling-salesman problem-Operations research (Flood et al. 1956), Vehicle routing: application of TSP in a diary (Palhares et al. 2018), Some simple applications of TSP (Lenstra et al. 1975) and Dynamic treatment of TSP (Bellman et al. 1962). 

The travelling salesman problem (TSP) is an algorithmic problem that demands identifying the shortest path between a number of necessary points and locations. This problem is also known as the travelling salesman problem. The travelling salesman problem, or TSP for short, is another name for it (TSP). The goal of the TSP is to achieve as much success as is physically possible in as little time as is reasonably achievable. The different cities that a salesperson might go to are reflected in the points that are provided in the problem specification. 

Because of its focus on optimization, TSP is frequently used in the domains of operations research, theoretical computer science, and supply chain management. This is due to the fact that TSP was developed in these fields. The goal is to figure out which of the possible routes connecting the various nodes and delivery places will result in the greatest amount of productive movement so as to achieve the target. (Mosheiov et al.1994) The stations are responsible for determining, among other things, which routes are the most economical and offer the shortest travel distances. Mathematicians from Ireland named W.R. Hamilton and the United Kingdom named Thomas Kirkman were the first to describe it in the 1800s. Both men were from their respective countries. They accomplished this by developing a game in which victory could be won by finding a path that is known as a Hamilton cycle and that does not cross any of the game's nodes at any point in time. 

The Travelling Salesman Problem is a key challenge that businesses in the logistics and supply chain industries are now attempting to overcome. TSP is becoming a more competitive and harder to join organisation as it grows in terms of the amount of physical sites, trucks, and sales employees. It becomes more difficult for salespeople to communicate with their clients in an effective manner when the TSP is not addressed, which in turn has a negative influence on the revenues of organisations because of the poor impact on customer interactions. 

Over the course of several decades, research has been conducted into TSP; throughout this period, a great number of hypotheses and potential solutions have been suggested. Investigating each and every available choice is the action that requires the least amount of effort and the least amount of time, but it will also take the greatest amount of time and cost the most amount of money. (Dorigo et al. 2007) TSP places a greater emphasis, in most cases, on locating the response with the lowest possible cost as opposed to concentrating on locating the strategy that would result in the greatest possible outcomes. This is because locating the response with the lowest possible cost allows for greater savings. The presence of a significant number of variables within TSPs makes it possible that determining the shortest path will prove to be a challenging endeavour. As a consequence of this, it is becoming an increasingly desirable goal to create approximation solutions that are speedy and affordable at the same time. 

TSP has gained a lot of attention due to the fact that, despite being easy to understand, it is extremely difficult to solve. This paradoxical quality contributes to the difficulty of the problem. In point of fact, the Travelling Salesman Problem is categorised as a member of the NP-complete class, which is consisting of problems involving combinatorial optimization. This class is recognised for being impossible to solve completely. This demonstrates that TSP is categorised as an NP-hard problem because it does not have a solution that is "quick," and the difficulty of determining the optimal route will increase as more destinations are added to the equation. Additionally, there is no known algorithm that can solve this problem. Furthermore, there is no method to fix the problem in a manner that is both effective and efficient. (Claus et al. 1984) 

The issue can be resolved by investigating all of the potential ways to get back to the starting point in order to identify the path that will take the fewest amount of hours overall. However, as the number of destinations increases, so does the number of roundtrips, to the point where even the most powerful computers are unable to process the information rapidly enough to keep up with the growth in the number of destinations. If there are ten distinct locations to visit, for instance, there are more than 300,000 distinct permutations and combinations that could be employed. There are possibly more than 87 billion possible routes that one may take to reach their objective if they travelled between these 15 different locations. 

Summary Of Findings

The solution to the Travelling Salesman Problem (TSP), which is also commonly known as the travelling salesman problem, is to figure out the quickest route possible to various cities or locations and then return to the place where you started. This is the answer to the Travelling Salesman Problem (TSP). (Bryant et al. 2000) 

Drawbacks

The Travelling Salesman Problem is a major challenge for logistics and supply chain management. TSP's growth in locations, vehicles, and salespeople makes it harder to join. Failure to find a TSP solution makes it harder for supply chain specialists to reach clients effectively, reducing company profitability. The traveller's issue can be solved by determining the fastest route for each trip inside a city. This makes solving the problem easier than it seems. This makes finding a solution more likely, which makes it easier. Manually solving the Travelling Salesman Problem becomes harder as the number of cities increases. When ten cities are involved, many permutations and combinations are possible. It is quite evident that TSP is an issue that occurs in the real world as a consequence of all of these constraints. No amount of physical effort will solve this issue. This problem is unsolvable.

To properly deal with TSP, it's important to use current technology. They must employ proper technologies to overcome these challenges. This is because the routes that are travelled are associated with a variety of obstacles. The significance of the role that artificial intelligence (AI) plays in assisting businesses in overcoming route inefficiencies and addressing TSP difficulties is growing to the point where it is becoming increasingly necessary. 

References: 

Dahiya, C. and Sangwan, S., (2018) Literature review on travelling salesman problem. International Journal of Research, 5(16), pp.1152-1155. 

Palhares, R.A. and Araújo, M.C.B., (2018) December. Vehicle routing: application of travelling salesman problem in a dairy. In 2018 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) (pp. 1421-1425). IEEE. 

Flood, M.M., (1956) The traveling-salesman problem. Operations research, 4(1), pp.61-75. 

Di Pretoro, A., Negny, S. and Montastruc, L., (2021) Flexibility Analysis in Supply Chain Management: Application to the Traveling Salesman Problem. In Computer Aided Chemical Engineering (Vol. 50, pp. 1721-1726). Elsevier. 

Lenstra, J.K. and Kan, A.R., (1975) Some simple applications of the travelling salesman problem. Journal of the Operational Research Society, 26(4), pp.717-733. 

Bellman, R., (1962) Dynamic programming treatment of the travelling salesman problem. Journal of the ACM (JACM), 9(1), pp.61-63. 

Dorigo, M. and Gambardella, L.M., (1997) Ant colonies for the travelling salesman problem. biosystems, 43(2), pp.73-81. 

Larranaga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I. and Dizdarevic, S., (1999) Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial intelligence review, 13(2), pp.129-170. 

You Might Also Like:-

Personal Reflection - Accounting and Finance Assignment Sample

How do I Create an Assignment in Salesforce?

Accounting And Finance Assignment Help