du.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimal Path Searching through Specified Routes using different Algorithms
Dalarna University, School of Technology and Business Studies, Computer Engineering.
2009 (English)Independent thesis Advanced level (degree of Master (Two Years))Student thesis
Abstract [en]

To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes. To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook

Place, publisher, year, edition, pages
Borlänge, 2009. , 37 p.
Keyword [en]
Routing problem, Shortest Path, Greedy Algorithm, Simulated Annealing, Exhaustive Search, Travelling Salesman Problem, Combinatorial Optimization
Identifiers
URN: urn:nbn:se:du-4530OAI: oai:dalea.du.se:4530DiVA: diva2:518793
Uppsok
Technology
Supervisors
Available from: 2010-02-11 Created: 2010-02-11 Last updated: 2012-04-24Bibliographically approved

Open Access in DiVA

fulltext(646 kB)427 downloads
File information
File name FULLTEXT01.pdfFile size 646 kBChecksum SHA-512
f16e4a3b1b1b001ca1415c5c2b04d2868e47c93eba35f52bd0e96ad3d930d363fc9f0985fad6bf54fa1dcfd7dbcc72e8fada670328970c9973d2545a6689af95
Type fulltextMimetype application/pdf

By organisation
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 427 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 537 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf