Optimum Route to All Seven Emirates: A Travelling Salesman Approach
Received Date: Aug 03, 2017 / Accepted Date: Oct 31, 2017 / Published Date: Nov 07, 2017
United Arab Emirates has seven emirates namely Abu Dhabi (capital), Dubai, Sharjah, Ajman, Umm al Quwain, Ras al Khaimah and Fujairah (Al Ain being counted within Abu Dhabi). This limited number of emirates though small in number but pose a great challenge when transportation among all the emirates is a task to be done optimally. Our study focuses on an application of Travelling salesman problem using assignment technique (operations research) which considers all the seven emirates including Al Ain as a separate emirate only for experiment reasons since the large distance between Al Ain and other emirates is not negligible. If there are n cities through which a salesman has to pass without passing any of the cities twice, there are (n-1)! ways through all the cities but there is one and only one optimum solution to it which has the minimum cost associated with it as well as the distance is the least among all the other routes. Similarly, these eight emirates give us (8-1)!=5040 ways to find the optimum route with minimum cost to travel between all emirates without visiting any emirate twice.
Keywords: Route; Travel management; Time; Cost; Technique
Travelling Salesman Problem, also known as TSP, is a mathematical problem that has been experimented over for many years through numerous techniques and approaches. It consists of formulating the shortest route possible to connect all the nodes of a certain place. In this research study, the optimal route is found through Assignment technique of Operations Research. Through this technique, all possible routes are listed down in a matrix and the values are reduced optimally until the minimised route is obtained.
Alazab et al.  used the technique of Geographic Information System (GIS), a real time traffic technology, to analyse the traffic congestion at a certain place and to plot a shortest possible route. It was found out that total costs, vehicle usage and driver productivity were the variables that were mostly affected through traffic congestion. The outcomes of changing parameters of traffic at a place were also analysed in the research. A further exploration of the combination of GIS and Decision Support System (DSS) was studied in the research of Ramamoorthy and Sabarigiri , which provided an optimum route through Spatial Decision Support System (SDSS). Decision Support System (DSS) is a system used to solve the problems by making effective decisions. SDSS is a combination of Geographic Information System and Decision Support System. The research concluded by finding an effective route through the data that was available in GIS.
Dorigo and Gambardella  has studied the concept of the ants finding the shortest path to their food. It consists of the ants maintaining a pheromone trail towards the food, which is prone to obstacles. Once an obstacle is introduced, the ants somehow again manage to find the optimum route. The ants and food are replaced by the agents and final destination in the study and the pheromone trail by the shortest route. Quadratic Assignment Problem (QAP), which consists of allocating facilities to the various locations for optimizing time, is combined with the behaviour of ant colonies and developed in the research of Maniezzo and Colorni . Voudouris and Tsang  use techniques of Guided Local Search (GLS) and Fast Local Search (FLS), mostly used in optimization problems. It was concluded that GLS with FLS-2Opt was considered as an ideal practical technique. Algorithms for planning the routes are used in the research of Nikolova et al.  by analysing the speed and reliability of a certain route. An optimal departure time and the optimal path to it are found through the research. Further enquiry into the researches of Chakroborty, Lenstra and Huang et al. [7-9] is made, where genetic algorithm and graphical plotting of nodes are used.
Rexford  has put down a research where the shortest route to a particular destination is found out through protocols and domain in IP. An effective bus transit route was derived through genetic algorithm and simulated annealing in the study of Fan et al. .
In this paper, TSP for UAE will be studied under Assignment Technique, unlike other researches.
Since, the distance (or time or cost) between every pair of emirates is dependent of the direction of travel, this problem is said to be an asymmetrical Travelling salesman problem. Initially, we create a distance matrix in kilometers among all the emirates which is a 8 × 8 matrix. This distance matrix forms a basis to derive a cost matrix from the former by assuming Dhs 28/km as fuel charges which varies slightly for light vehicles but our analysis considers a van as it is the most preferred vehicle for transportation of parcels and couriers. Our objective after deriving the cost matrix is to minimize the total cost using assignment technique. An assignment problem links the number of origin points to its respective equal number of destinations which is associated with a cost or profit. Hence, the formulated matrix will be a square matrix. If the given matrix is a cost matrix, our objective will be to minimize whereas if it is the latter, the objective shifts to maximization. Thus the travelling salesman problem can be put in the form of an assignment problem as shown below (Table 1).
Infinite cost (∞) is assigned as penalty for traveling from a city to the same city to avoid inter-city transport. This cost matrix is solved using assignment technique by generating zeroes in all rows and columns for the purpose of striking them with minimum number of lines so as to reach the optimal solution if the number of crossed lines is equal to the order of the matrix (striking of lines for zeroes can be either vertical or horizontal but cannot be angled other than 0 or 90 degrees). If not so, we have to revise the first feasible solution by a special technique used in assignment to reach second feasible solution. We revise the cost matrix until we reach the optimal solution which has the minimum number of lines equal to the order of the matrix covering all zeroes within the table.
We solve TSP problem for United Arab Emirates in two different periods, one at the peak hours and the other at non-peak hours. Hence, there will be variations in timings, distances if a different route is taken to avoid traffic which has an effect on the total cost.
The parent matrix for peak hours includes four factors namely, distance, time, average speed and cost to travel from one emirate to other (Table 2).
We extract the cost information from the above table and employ it under assignment technique to minimize the cost. An assignment problem by default has to be converted to from a maximization problem to a minimization one before we start with the optimization process. Our problem in hand has the objective to minimize cost, hence we skip conversion to minimization problem (Table 3).
Step1: We create zeroes in all rows by performing row operation (deducting the smallest value in each row from all the other values and with itself (Table 4).
Step 2: If the row operation generates at least a single zero in each column as well, then there is no need to perform column operation or else we proceed with column operation which is deducting the least value in each column with all the other values in their respective columns and the number itself.
After completing generating zeroes in rows and columns, we try to cover all zeroes by minimum number of 0 degree lines or a 90 degree lines. This process is a trial and error technique which has to be tried with all combinations of striking lines so as to employ minimum number of line to do the job (Table 5).
Step 3: If the minimum number of lines used to cover all zeroes is equal to the order of matrix which in this case is 8 × 8, then we have reached the optimal solution, if not, we go ahead with further process of optimization. This process involves selecting the least uncovered element and deducting it with all the uncovered elements including itself, but it has to be added to the elements at the intersection. And repeat the process of covering all the zeroes with minimum number of lines (Table 6).
Step 4: Repeat step 3 until you have the number of covered lines equal to the order of the matrix (Tables 7a, and 7b).
Step 5: We finally have our optimized matrix with minimum number of covered lines equal to the order of the matrix (Table 8).
Step 6: We start with the process of assigning, i.e. connect the destinations of “From” ( Row wise) to “To” (Column wise) (Table 9).
Calculation For Non-Peak Hours
The cost data in the below matrix was extracted at non peak hours (Table 10).
Step 1: We adopt the similar process as we used in peak hour calculations and move ahead with the optimization process (Tables 11 and 12a-12c).
We have the shortest route to all seven emirates at peak and nonpeak hours which are as follows:
Fujairah>RAK>UAQ>Ajman>Sharjah>Dubai>Abu Dhabi>Al Ain.
Via Rugaylat Rd/E99 and Gragrah-Ghub Rd/E87>via Sheikh Mohammed Bin Zayed Rd/E311>via Al Shohadaa Rd/Truck Road>via Al Ittihad St/E11>via Sheikh Maktoum Bin Rashid St/Sheikh Zayed St and E11>via E11>via Abu Dhabi-Ghweifat International Hwy/E11 and Abu Dhabi-Al Shahama Rd/Sheikh Zayed Bin Sultan St/E10>via Abu Dhabi-Al Ain Rd/E22.
Total cost=DHS 210 (excluding tolls)
Total distance: 580 kms.
This data can be exploited by firms in the business of transportation in all seven emirates on a day to day basis. For example: Al Ain dairy has to transfer milk and dairy products almost daily in all the seven emirates. This study not only helps in giving the shortest distance but further classifies it under peak and non-peak hours. Many other business entities like DHL, Aramex, FedEX, can take benefit out of this research as a standard to beat traffic at peak hours and accomplish their task at minimum cost and least time.
The network diagram below represents a complex web of all possible combinations to travel seven emirates (Figure 1).
The above complex web of chaotic network diagram represents the infinite number of combinations possible initially. Network simplifies to the shortest distance after our optimization process using Assignment technique as shown below (Figure 2).
Scope And Limitations Of This Research
Similar methodology was used to find the least distance between all emirates at non-peak hours but the results were not practical since there were more than one route between emirates at non-peak hours. Also, this shows the limitation of assignment technique in solving near optimal solutions.
Different techniques such as heuristics or Vogel’s Approximation Method can be utilized in solving this as a travelling salesman problem.
We would like to thank our mentor and guide Mr. Mohamed Irfan Shaikh, (Assistant Professor, Birla Institute of Technology, RAK, UAE) who helped us in creating this research paper without whose help it would be a difficult task to complete. Also, we would like to thank our classmates who helped us in verifying some of the route congestion at peak and non peak hours.
- Alazab A, Venkatraman S, Abawajy J, Alazab M (2012) “An Optimal Transportation Routing Approach using GIS-based Dynamic Traffic Flows”, 3rd International Conference on Information and Financial Engineering, Singapore, pp: 172-178.
- Ramamoorthy HV, Sabarigiri B (2013) “An Optimal Route Determining Methodology Based on Decision Support System”. Journal of Global Research in Computer Science 4: 20-24.
- Dorigo M, Gambardella LM (1997) “Ant Colonies for Travelling Salesman Problem”, Biosystems 43: 73-81.
- Vittorio Maniezzo, Alberto Colorni (1999) “The Ant System Applied to the Quadratic Assignment Problem”, IEEE Transactions on Knowledge and Data Engineering 11: 769-778.
- Voudouris C, Tsang E (2010) “Guided Local Search and its application to the Travelling Salesman Problem”, International Series in Operations Research & Management Science 146: 321-361.
- Nikolova E, Brand M, Karger DR (2006) “Optimal Route Planning under Uncertainity”. Proceeding ICAPS'06 Proceedings of the Sixteenth International Conference on International Conference on Automated Planning and Scheduling, pp: 131-140.
- Chakroborty, “Optimal Routing and Scheduling in Transportation: Using Genetic Algorithm to Solve Difficult Optimization Problems”. pp: 29-40.
- Lenstra JK, Rinnooy Kan AHG (1975) “Some Simple Applications of Travelling Salesman Problem”. A. J Oper Res Soc 26: 717-733.
- Huang J, Hu L, Gu Z-Q, Yang Y, Song X (2008) “Research and Realization of optimum route planning in Vehicle Navigation Systems based on a hybrid genetic algorithm”. Institute of Mechanical Engineering 222: 757-763.
- Rexford J (2006) “Route Optimization in IP Networks”. Handbook of Optimization in Telecommunications. Springer, Boston, MA, pp: 679-700.
- Fan W, Machemehl RB, Lownes NL (2008) “Some Computational Insights on the Optimal Bus Transit Route Network Design Problem”. Journal of the Transportation Research Forum 4: 61-75.
Citation: Fernando MM, Prasad V, Shaikh MI (2017) Optimum Route to All Seven Emirates: A Travelling Salesman Approach. Arabian J Bus Manag Review 7: 326.
Copyright: © 2017 Fernando MM, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Select your language of interest to view the total content in your interested language
Share This Article
- Total views: 1387
- [From(publication date): 0-2017 - Dec 09, 2019]
- Breakdown by view type
- HTML page views: 1307
- PDF downloads: 80