hrcak mascot   Srce   HID

Stručni rad

SOLVING THE TRAVELLING SALESMAN PROBLEM USING THE BRANCH AND BOUND METHOD

Mirta Mataija   ORCID icon orcid.org/0000-0002-7123-6761 ; Polytechnic of Rijeka, Rijeka, Croatia
Mirjana Rakamarić Šegić ; Polytechnic of Rijeka, Rijeka, Croatia
Franciska Jozić   ORCID icon orcid.org/0000-0002-8691-6698 ; Prometna škola u Rijeci, Rijeka, Hrvatska

Puni tekst: engleski, pdf (184 KB) str. 259-270 preuzimanja: 15.548* citiraj
APA 6th Edition
Mataija, M., Rakamarić Šegić, M. i Jozić, F. (2016). SOLVING THE TRAVELLING SALESMAN PROBLEM USING THE BRANCH AND BOUND METHOD. Zbornik Veleučilišta u Rijeci, 4 (1), 259-270. Preuzeto s https://hrcak.srce.hr/160248
MLA 8th Edition
Mataija, Mirta, et al. "SOLVING THE TRAVELLING SALESMAN PROBLEM USING THE BRANCH AND BOUND METHOD." Zbornik Veleučilišta u Rijeci, vol. 4, br. 1, 2016, str. 259-270. https://hrcak.srce.hr/160248. Citirano 28.10.2020.
Chicago 17th Edition
Mataija, Mirta, Mirjana Rakamarić Šegić i Franciska Jozić. "SOLVING THE TRAVELLING SALESMAN PROBLEM USING THE BRANCH AND BOUND METHOD." Zbornik Veleučilišta u Rijeci 4, br. 1 (2016): 259-270. https://hrcak.srce.hr/160248
Harvard
Mataija, M., Rakamarić Šegić, M., i Jozić, F. (2016). 'SOLVING THE TRAVELLING SALESMAN PROBLEM USING THE BRANCH AND BOUND METHOD', Zbornik Veleučilišta u Rijeci, 4(1), str. 259-270. Preuzeto s: https://hrcak.srce.hr/160248 (Datum pristupa: 28.10.2020.)
Vancouver
Mataija M, Rakamarić Šegić M, Jozić F. SOLVING THE TRAVELLING SALESMAN PROBLEM USING THE BRANCH AND BOUND METHOD. Zbornik Veleučilišta u Rijeci [Internet]. 2016 [pristupljeno 28.10.2020.];4(1):259-270. Dostupno na: https://hrcak.srce.hr/160248
IEEE
M. Mataija, M. Rakamarić Šegić i F. Jozić, "SOLVING THE TRAVELLING SALESMAN PROBLEM USING THE BRANCH AND BOUND METHOD", Zbornik Veleučilišta u Rijeci, vol.4, br. 1, str. 259-270, 2016. [Online]. Dostupno na: https://hrcak.srce.hr/160248. [Citirano: 28.10.2020.]

Rad u XML formatu

Sažetak
The goal of this paper is to optimize delivering of packages at five randomly chosen addresses in the city of Rijeka. This problem is also known as the Travelling Salesman Problem and it is an NP hard problem. To achieve this goal, the concepts of a Hamilton path and cycle, as well as a Hamilton graph are defined. The theoretical basis for the branch and bound method is also given. The use of this method in the process of finding a solution for a problem is provided at the end of this paper.

Ključne riječi
Travelling Salesman Problem; Branch and Bound Method; Hamilton path; Hamilton cycle; NP complete problem; NP hard problem

Hrčak ID: 160248

URI
https://hrcak.srce.hr/160248

▼ Article Information



1. INTRODUCTION

The Travelling Salesman Problem is one of the most studied problems in mathematical optimization. The possibility to apply this problem to various human activities is what it makes one of the most recognizable mathematical problems without an ideal solution so far.

The formulation of the problem is simple. The travelling salesman needs to pass through several towns and return to the starting point of his travel, making the shortest trip possible. Instead of examining the shortest route, one could examine the one that costs the least, one that allows the greatest flow of information, etc.

By its nature, the TSP falls into the category of NP-complete problems; meaning there is no algorithm that would provide a solution for the problem in terms of polynomial time but if the solution appears, one could test it and conclude whether it is an optimal one.

The goal of this research is to optimize the delivery of packages to appointed addresses in Rijeka. The delivery man has to deliver packages using the most efficient and shortest route moving from the distribution center to which he is required to return to after the delivery of the last package. This is in fact a Travelling Salesman Problem (Bosančić, V. Golemac, A. Vojković T.) and it can be solved using the branch and bound method (Pielić, M).

The paper consists of four parts. The Travelling Salesman Problem as well as the basic definitions of graph theories are provided in the second part. The theoretical basis for the branch and bound method is elaborated in the third part. Along with the theoretical basis, the algorithmic display of the method is provided. In the fourth and final part the method is used on the subject of the research.

2. THE TRAVELLING SALESMAN PROBLEM

In order to use mathematical methods in solving the Travelling Salesman Problem one needs to translate it to the language of a graph theory. The first step is to define several terms (Veljan, D.; Pašagić, H.).

Definition 1.1. Graph zbornik-veleri-4-259-g1.png is an ordered pair zbornik-veleri-4-259-g2.png where zbornik-veleri-4-259-g3.pngis a set of vertices of the graph while zbornik-veleri-4-259-g4.png is a set of edges or arcs of the zbornik-veleri-4-259-g1.png graph.

In line with the definition, the vertices of graphs will be marked with zbornik-veleri-4-259-g6.png, and the edges with zbornik-veleri-4-259-g5.png. Mark zbornik-veleri-4-259-g5.png tells us that the given edge is incident (connected) with the vertices zbornik-veleri-4-259-g6.png and zbornik-veleri-4-259-g7.png.

Definition 1.2. The path in the graph is zbornik-veleri-4-259-g8.png of the string in which all the vertices are different. The cycle is the path in which zbornik-veleri-4-259-g9.png.

Definition 1.3. a Hamilton path (cycle) in graph zbornik-veleri-4-259-g1.png is the path (cycle) that contains all the vertices of graph zbornik-veleri-4-259-g1.png. The graph is called a Hamilton graph if it contains a Hamilton cycle.

Definition 1.4. Weighted graph or a network is a graph in which all the edges have their appointed real numbers. The number zbornik-veleri-4-259-g10.png is appointed to the edge zbornik-veleri-4-259-g5.png and it is called the weight of the edge or simply - weight.

According to the above mentioned definitions one could conclude that the solution for the Travelling Salesman Problem is equivalent to finding the Hamilton cycle with the least weight in the network.

The Travelling Salesman Problem in its core is a problem of binary linear programming. The following codes are introduced (Perić, T.):

  • zbornik-veleri-4-259-g11.png marks the binary variables as follows: zbornik-veleri-4-259-g12.png

  • The distance between the towns i and j is marked with zbornik-veleri-4-259-g10.png.

The Travelling Salesman Problem can be written as follows (Perić, T.):

zbornik-veleri-4-259-g13.png

zbornik-veleri-4-259-g14.png

zbornik-veleri-4-259-g15.png

zbornik-veleri-4-259-g16.png

The objective function is marked with F. The limitation should also be included into the program zbornik-veleri-4-259-g17.png in order to prevent the salesman returning to one of the towns he has already been to before he has visited all the towns. In other words, with these limitations the possibility of the appearance of under-cycles in the network is prevented. Since variables zbornik-veleri-4-259-g11.png can only take a 0 or 1 state, this problem has a finite number of solutions.

3. THE BRANCH AND BOUND METHOD

While solving the Travelling Salesman Problem two approaches can be used. The first one is to find the correct solution, the optimal Hamilton cycle in the graph. Generally speaking, this is not so hard to achieve – first one has to find all the Hamilton cycles and choose the one with the minimal weight (Ivić, M.). However, the problem arises even in the case of a low number of vertices. Namely, the number of Hamilton cycles in the graph is zbornik-veleri-4-259-g18.png where n signifies the number of vertices of the graph. Number of cycles possible for zbornik-veleri-4-259-g19.png is 362880 while the number of cycles for zbornik-veleri-4-259-g20.png equals 121645100408832000.

The complexity of this particular problem is zbornik-veleri-4-259-g21.png and it is virtually useless when the number of vertices (entry data) exceeds 10 (Carić, T.).

The second approach consists of pursuing the “good enough” approximate solution.

The branch and bound method provides a correct solution for the given problem. It is suitable for use when the number of vertices of graphs does not exceed 60, which is sufficient when it comes to problems such as package delivery.

This method is based on the idea that the sets are divided into two disjoint subsets at every step of the process - branching. Furthermore, one subset contains the path between the two selected towns and the other subset does not. For each of these subsets the lower restriction (bound) is calculated for the duration or for travel expenses. Finally, the subset which exceeds the estimated lower bound is eliminated.

The procedure of branching is represented by a tree where the top is marked by the branching points of the set of solutions, and the edges mark the path between the two contiguous vertices in the graph which are used to model the problem and inside which the shortest Hamilton cycle is pursued.

The knots in the branching tree are labelled with the “etiquettes” which represent the lowest binding point for the objective function.

“Weightings” are assigned to the edges and they mark with zbornik-veleri-4-259-g22.png the routes that are travelled or with zbornik-veleri-4-259-g23.png those bypassed.

A way to represent and use this method with data tables is demonstrated since they are clearly suitable for any future computer applications (Perić, T.).

The steps of the algorithm for the Travelling Salesman Problem using the bound and branch method are as follows:

Step 1: Drawing a table

A table of distance between the given vertices is drawn. The distance between the vertices i and j are marked with zbornik-veleri-4-259-g10.png. If the two vertices are not contiguous they are marked with zbornik-veleri-4-259-g24.png. The zbornik-veleri-4-259-g25.png mark to signify and prevent the algorithm to choose the path zbornik-veleri-4-259-g26.png is also appointed.

Step 2: The reduction of the table

In every row of the table, the smallest element is located and marked with zbornik-veleri-4-259-g27.png:

zbornik-veleri-4-259-g28.png

The smallest elements in columns are calculated using the following formula:

zbornik-veleri-4-259-g29.png

The reduction of the table is calculated with the formula:

zbornik-veleri-4-259-g30.png

Step 3: The calculation of the lower boundary

The lower boundary of the duration of the travel is calculated

zbornik-veleri-4-259-g31.png

and assigned, which bounds to the knots of the branching tree as etiquette.

Step 3': The calculation of the lower boundary

zbornik-veleri-4-259-g55.png is equalized with the etiquette of the knot in which the branching is performed.

Step 4: Branching

The top from which the branching will start is chosen. All the addresses in the reduced table are found, the zbornik-veleri-4-259-g32.png paths, for which we can state that zbornik-veleri-4-259-g33.png. For each of these, the “penalty” for not utilizing the trajectory zbornik-veleri-4-259-g32.png is calculated. The penalty is calculated with the formula: zbornik-veleri-4-259-g34.png

The branching is initiated with the trajectory which is assigned the maximum “penalty”.

zbornik-veleri-4-259-g35.png

zbornik-veleri-4-259-g36.png are used to mark the route with the maximum penalty.

Step 5: Etiquette calculating

The etiquette of the knot contiguous to the edge which has a “weighting” zbornik-veleri-4-259-g36.png is calculated. In the reduction table zbornik-veleri-4-259-g37.png is assigned to signify the restriction towards the traveller, preventing him from returning from town q to town p. Furthermore, all the possibilities of closing the cycle prior to passing all the vertices of the graph need to be blocked. The next step is to remove the p line and q column from that table and repeat steps 2 and 3. The sum of the reduced elements is marked with zbornik-veleri-4-259-g56.png.

Step 6: Drawing the branching tree

In the branching tree, we assign the b etiquette to the knot from which the branching started. The edges that exit this knot are assigned with “weightings” zbornik-veleri-4-259-g36.png and zbornik-veleri-4-259-g38.png. The contiguous knot to the zbornik-veleri-4-259-g38.png edge is assigned with the zbornik-veleri-4-259-g39.png etiquette. The contiguous knot to the zbornik-veleri-4-259-g36.png edge is on the other hand assigned with the zbornik-veleri-4-259-g40.png etiquette.

Step 7: Locating the knot with the smallest etiquette

One should try to pinpoint the knot with the smallest etiquette in the branching tree and repeat the procedure – steps 1-6 are the same with the exception of step3 which is replaced with step 3'.

The algorithm is completed when the table contains only routes which, if not used, lead to the solution that is the trajectory of infinite duration.

4. PROBLEM SOLUTION

The aim of this research paper is to optimize the delivery of packages to the appointed addresses in Rijeka. This is in fact a Travelling Salesman Problem and it can be solved using the branch and bound method (Pielić, M). This method is useful when the number of addresses does not exceed 60. In this case the appointed number of addresses is 5 and the method can be applied without the use of computers, as it is shown in the research.

The branch and bound method is used to optimize the package delivery to five addresses in the town of Rijeka. These are the following addresses:

  • Kršinićeva

  • Giuseppe Carabine

  • Antuna Kosića Rike

  • Simonettieva

  • Crnčićeva

The distance between them in meters is provided in Table 1. (Jozić, F.)

The algorithm described in the previous section is used to calculate the optimal route to deliver the packages to these addresses.

Step 1

Table 1. Distance between the streets
addresses12345
1zbornik-veleri-4-259-g41.png600100019001100
2600zbornik-veleri-4-259-g41.png190019001500
310001900zbornik-veleri-4-259-g41.png17001200
4190019001700zbornik-veleri-4-259-g41.png1900
51100150012001900zbornik-veleri-4-259-g41.png

Source: authors

Step 2

Table 2. Locating the minimal elements in lines
addresses12345zbornik-veleri-4-259-g27.png
1zbornik-veleri-4-259-g41.png600100019001100600
2600zbornik-veleri-4-259-g41.png190019001500600
3.10001900zbornik-veleri-4-259-g41.png170012001000
4190019001700zbornik-veleri-4-259-g41.png19001700
51100150012001900zbornik-veleri-4-259-g41.png1100

Source: authors

The minimal element in the i-row, i = 1,…, 5, calculated using the formula:

zbornik-veleri-4-259-g42.png

Table 3. Locating the minimal elements in columns
addresses12345zbornik-veleri-4-259-g27.png
1zbornik-veleri-4-259-g41.png600100019001100600
2600zbornik-veleri-4-259-g41.png190019001500600
3.10001900zbornik-veleri-4-259-g41.png170012001000
4190019001700zbornik-veleri-4-259-g41.png19001700
51100150012001900zbornik-veleri-4-259-g41.png1100
zbornik-veleri-4-259-g44.png000700200

Source: authors

The minimal element in the j-row, j = 1,…, 5, calculated using the formula:

zbornik-veleri-4-259-g43.png - zbornik-veleri-4-259-g27.png ).

Table 4. Reduced table
addresses12345zbornik-veleri-4-259-g27.png
1zbornik-veleri-4-259-g41.png0400600300600
20zbornik-veleri-4-259-g41.png1300600700600
3.0900zbornik-veleri-4-259-g41.png001000
42002000zbornik-veleri-4-259-g41.png01700
50400100100zbornik-veleri-4-259-g41.png1100
zbornik-veleri-4-259-g44.png000700200

Source: authors

The reduction of the table is done using the formula: zbornik-veleri-4-259-g30.png.

Step 3

In step 3, the lower boundary of the duration of the travel route is calculated using the formula zbornik-veleri-4-259-g46.png and the result is:

zbornik-veleri-4-259-g47.png

Step 4

The top from which the branching will commence is found. “Penalty” for not using the route i-j is calculated using the formula:

zbornik-veleri-4-259-g48.png

The branching commences with the route that carries the maximum “penalty“ provided by the formula 𝜋=zbornik-veleri-4-259-g49.png.

In this case, the maximum “penalty” is appointed for not using the 2-1 route and it is 600 meters:

zbornik-veleri-4-259-g50.png , zbornik-veleri-4-259-g51.png

Step 5

The second row and first column are removed from the starting table given the fact that the route 2-1 has the maximum penalty. This table is then repeatedly used through steps 2 and 3 producing Table 5. In this table, the elements from column zbornik-veleri-4-259-g27.png and row zbornik-veleri-4-259-g44.png are aggregated. Their sum is marked with σ. When σ is aggregated with the lower boundary b calculated in step 2, the lower boundary of the route i-j, in this case 2-1, is calculated.

Table 5. Table without the second line and first column
addresses2345zbornik-veleri-4-259-g27.png
1zbornik-veleri-4-259-g41.png400600300300
3.900zbornik-veleri-4-259-g41.png000
42000zbornik-veleri-4-259-g41.png00
5400100100zbornik-veleri-4-259-g41.png100
zbornik-veleri-4-259-g44.png200000

Source: authors

zbornik-veleri-4-259-g52.png

Step 6

In the branching tree, the top is marked with 1 and the edges that stem from it have “ponders” (2,1) or rather non(2,1) depending on the usage of the route 2-1 for package delivery. The edges end with points 2 and 3. A mark is assigned to each point representing the lower boundary of the route depending on the use or non-use of the given route.

zbornik-veleri-4-259-g53.png

Step 7

The branching is continued in any of the knots, 2 or 3, since their etiquettes have equal values. The calculation is continued in knot 2.

After applying the described procedure four (4) times, Table 6 is provided:

Table 6. The end of the algorithm
addresses34zbornik-veleri-4-259-g27.png
3.zbornik-veleri-4-259-g41.png00
50zbornik-veleri-4-259-g41.png0
zbornik-veleri-4-259-g44.png00

Source: authors

The complete branching tree is represented in Picture 1.

Picture 1. Branching Tree
zbornik-veleri-4-259-g54.png

Source: authors

It is concluded that 1 – 5 – 3 – 4 – 2 – 1 is the optimal route for the travelling salesman delivering to appointed addresses. Duration of the route is 6500 meters.

5. CONCLUSION

In this paper we have shown a way to solve the Travelling Salesman Problem by using data tables and the branch and bound method which have given the correct solution to the problem and have proven to be effective in up to 60 data entries. The method to solve the specific problem of package delivery to certain addresses knowing the exact distance between these addresses is used in this example.

By using this method, the optimal package delivery route as well as the duration of this route in meters is calculated. This research has demonstrated that a method to calculate optimal routes, used in this manner and without the use of computers and software packages, can be efficient.

In the context of competitive market it is important to rationalize every business segment by using mathematical methods such as this one. Rationalization by calculation of optimal routes of delivery is very simple to use and it reduces business costs considerably.

The Travelling Salesman Problem can be used widely in many human activities. One of the more important ones could be organizing the production and locating the most optimal sequence of operations and tasks. The sequence of implementing certain automated operations like drilling holes in printed circuit boards is one of the most important ways of optimizing the production process with the Travelling Salesman algorithm.

The branch and bound method is suitable for working with computer applications and it is considered to be one of the possible ways to encourage further exploration of this problem.

REFERENCES

1 

Bosančić, V., Golemac, A. Vojković, T. (2012)Kako pomoći trgovačkom putniku, Osijek: Osječki matematički list 12.

2 

Carić, T. (2014) Optimizacija prometnih procesa (nastavni tekst) (Transport optimization), Zagreb: Sveučilište u Zagrebu, Fakultet prirodnih znanosti.

3 

Ivić, M. (2009) Hamiltonov ciklus i Eulerova tura (Hamilton cycle and Euler tour), završni rad, Osijek: Sveučilište J. J. Strossmayera u Osijeku, Odjel za matematiku, http://www.mathos.unios.hr/~mivic//zavrsni.pdf (09.2014).

4 

Jozić, F. (2014) Rješavanje problema trgovačkog putnika metodom grananja i ograđivanja (Solving travelling Salesman Problem using Branch and Bound Method), specijalistički završni rad, Rijeka: Veleučilište u Rijeci.

5 

Pašagić, H. (1998) Matematičko modeliranje i teorija grafova, Zagreb: Sveučilište u Zagrebu, Fakultet prometnih znanosti.

6 

Perić, T. (2014) Problem trgovačkog putnika (Travelling Salesman Problem), http://web.efzg.hr/dok/mat/svlah/PROBLEM%20TRGOVA%C4%8CKOG%20PUTNIKA.pdf (09.2014.) .

7 

Pielić, M. (2008) Rješavanje problema trgovačkog putnika uz pomoć genetskih algoritama, Završni rad, Zagreb: Sveučilište u Zagrebu, Fakultet elektronike i računarstva.

8 

Veljan, D. (2001) Kombinatorika i diskretna matematika (Combinatorics and discrete mathematics), Zagreb: Algoritam.


This display is generated from NISO JATS XML with jats-html.xsl. The XSLT engine is libxslt.

[hrvatski]

Posjeta: 16.165 *