Sunday Times E-Paper

Efficient Delivery of Food

During the lockdown period, food transport providers would have had to attend to deliveries covering a wide range of locations. To cover all required locations and get back to the food outlet, the driver has to take the shortest route, as going even 1 km more than necessary may add to the cost of transportation

Finding the best possible route is well known to mathematicians, and it is known as the ‘Travelling Salesman Problem’. It deals with the following question: “Given a list of sites and the distances between each pair of sites, what is the shortest possible route that visits each site exactly once and returns to the origin site?” This problem said to be formulated in 1930 has commanded much attention because it is easy to describe but

The problem can be solved by considering all routes to determine the shortest one. However, as the number of destinations increases, the corresponding number of routes also increase exponentially.

With 10 destinations, there can be more than 300,000 routes to consider and with 15 destinations, it could exceed 87 billion.

Consider the following diagram indicating the sites by dots.

The next diagram is a possible solution.

This is a well-known algorithmic Research, which is a branch of mathematics and computer science. Three popular approaches are given below:

1. The Nearest Neighbour Method

This algorithm can be summarized as follows:

(i) Select a random city as the starting city.

(ii) Find the nearest unvisited city and go there.

(iii) Mark the current city as visited. (iv) Are there any unvisited cities? If yes, go back to (ii).

(v) Return to the starting city.

2. Brute-Force Method

The Brute Force approach calculates and compares all possible permutations

of routes or paths to determine the shortest unique solution.

3. Greedy Algorithm Method

A greedy algorithm works in phases. At each phase, you take the best you can get, without regard for future consequences. The idea is that by choosing a local optimum at each step, you will end up at a global optimum.

The Travelling Salesman Problem has several applications such as planning, logistics, and the manufacture of it appears as a sub-problem in many areas, such as DNA sequencing.

In fact, you may be taking this approach in your own life. If you have a series of errands to accomplish, you route to make each stop, minimizing time and energy.

FUNDAY TIMES

en-lk

2021-11-28T08:00:00.0000000Z

2021-11-28T08:00:00.0000000Z

https://sundaytimes.pressreader.com/article/283442079742116

Wijeya Newspapers