Chittaranjan Mallick

Department of Basic Science (Mathematics), Parala Maharaja Engineering College (Govt.), Berhampur 761003, Odisha, India

Sourav Kumar Bhoi

Department of Computer Science and Engineering, Parala Maharaja Engineering College (Govt.), Berhampur 761003, Odisha,

Chitta Ranjan Mohanty

Department of Civil Engineering, Parala Maharaja Engineering College (Govt.), Berhampur 761003, Odisha, India

Abstract

In this work, we applied the Travelling Salesman Problem Technique is to optimize the shortest route for visiting different tourist places in Berhampur city of Odisha in India with minimum transportation cost. The tourist knows the distance (cost) between every pair of tourist places of a city. The problem is to select a possible route that begins from the starting point (tourist place) of a city and passes through each place only once and return to the starting point by using the shortest possible distance. Suppose n tourist places are there in a city then (n-1)! routes are possible. At present, the best option to solve such types of problems is by using assignment techniques. Here, we have to focus optimum route (path) where the total distance or cost is minimum. In this problem, the tourist started from Gopalpur Beach and ended at Rambha Chilika point by passing through all tourist places once. Therefore, the tourist uses different techniques of Travelling Salesman Problem (TSP) solving methods to solve this problem. The methods used are Branch & Bound (Penalty) Method, Diagonal Completion Method and Nearest Neighbor method, to find the initial feasible solution (IFS). From this case study, it is found that the minimum transportation cost achieved is 166 Km for Branch & Bound (Penalty) Method as compared to other methods.

Keywords- Tourist Service, Optimum route, Assignment problem, Branch & Bound Method, Diagonal Completion Method, Nearest Neighbor Method.