Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Computing
Published in: Computing 2/2023

07-11-2022 | Regular Paper

Algorithms for path optimizations: a short survey

Authors: S C M S De Sirisuriya, T G I Fernando, M K A Ariyaratne

Published in: Computing | Issue 2/2023

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Path finding is used to solve the problem of finding a traversable path through an environment with obstacles. This problem can be seen in many different fields of study and these areas rely on fast and efficient path finding algorithms. This paper aims to describe and review state of the art optimization techniques that are used on optimized path finding and compare their performances. Moreover, a special attention is paid on the proposed approaches to identify how they are tested on different test cases; whether the test cases are automatically generated or benchmark instances. The review opens avenues about the importance of automatic test case generation to test the different path finding algorithms.
previous article Influence maximization based on SATS scheme in social networks
next article Constraint-based debugging in probabilistic model checking

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Thantulage G, Kalganova T, Fernando WAC(2006) A grid-based ant colony algorithm for automatic 3d hose routing, In: 2006 IEEE International conference on evolutionary computation, pp. 48–55,
2.
Alwis P, Premarathna A, Fonseka Y, Samarasinghe S, Wijayakulasooriya J (2014) Automated printed circuit board (pcb) drilling machine with efficient path planning, 01
3.
Lin CW, Rao L, Giusto P, D’Ambrosio J, Vincentelli A (2014) An efficient wire routing and wire sizing algorithm for weight minimization of automotive systems, 06
4.
Omar R, Gu DW (2010) 3d path planning for unmanned aerial vehicles using visibility line based method. 1(01), pp. 80–85,
5.
Bai J, Lian S, Liu Z, Wang K, Liu D (2018) Deep learning based robot for automatically picking up garbage on the grass. IEEE Trans Cons Electr 64:382–389CrossRef
6.
Thantulage G, Kalganova T, Wilson M (2008) Grid based and random based ant colony algorithms for automatic hose routing in 3d space. Trans Eng, Comp Technol, Int J Appl Sci 14:02
7.
Bonyadi MR, Michalewicz Z (2017) Particle swarm optimization for single objective continuous space problems: a review
8.
Ariyaratne MKA, Pemarathne WPJ (2015) A review of recent advancements of firefly algorithm; a modern nature inspired algorithm
9.
Paulinas M, Ušinskas A (2007) A survey of genetic algorithms applications for image enhancement and segmentation. Info Technol Contr 36:278–284
10.
11.
Cordón García O, Herrera Triguero F, Stützle T (2002) A review on the ant colony optimization metaheuristic: basis, models and new trends. Mathw Soft Comput 9:2–3MATHMathSciNet
12.
Ariyasingha I, Fernando T (2017) Random weight-based ant colony optimisation algorithm for the multi-objective optimisation problems. Int J Swarm Intell 3(01):77CrossRef
13.
Pemarathne WPJ, Fernando TGI (2019) Optimizing the electrical wire routing through multiple points using multi-objective ant colony algorithms for electrical wire routing (moacs-ewr), In: 2019 14th Conference on industrial and information systems (ICIIS), pp. 494–499
14.
Mohammed MA, Ghani M K Abd, Hamed RI, Mostafa SA, Ahmad MS, Ibrahim DA (2017) Solving vehicle routing problem by using improved genetic algorithm for optimal solution. J Computat Sci 21:255–262
15.
Kwaśniewski K, Gosiewski Z (2018) Genetic algorithm for mobile robot route planning with obstacle avoidance. Acta Mechanica et Automatica 12(06):151–159CrossRef
16.
Dewang H, Mohanty P, Kundu S (2018) A robust path planning for mobile robot using smart particle swarm optimization. Procedia Comp Sci 133(01):290–297CrossRef
17.
Nazari M, Oroojlooy A, Snyder LV, Takáč M (2018) Reinforcement learning for solving the vehicle routing problem. Adv Neural Inf Proc Sys 31
18.
19.
Bae H, Gidong K, Kim J, Qian D, Lee S (2019) Multi-robot path planning method using reinforcement learning. Appl Sci 9(07):3057CrossRef
20.
Miki S, Yamamoto D, Ebara H (2018) Applying deep learning and reinforcement learning to traveling salesman problem, pp. 65–70, 08
21.
Abiyev R, Arslan M, Gunsel I, Cagman A (2017) Robot pathfinding using vision based obstacle detection. pp. 1–6, 06
22.
23.
24.
Laghmara H, Boudali M.-T, Laurain T, Ledy J, Orjuela R, Lauffenburger J.-P, Basset M (2019) Obstacle avoidance, path planning and control for autonomous vehicles, pp. 529–534, 06
25.
Xie D, Xu Y, Wang R (2019) Obstacle detection and tracking method for autonomous vehicle based on three-dimensional lidar. Int J Adv Robot Sys 16(03):172988141983158CrossRef
26.
Ganguly S, Das S (2013) A novel ant colony optimization algorithm for the vehicle routing problem. In: Panigrahi BK, Suganthan PN, Das S, Dash SS (eds) Swarm, evolutionary and memetic computing. Springer, Cham, pp 401–412CrossRef
27.
Brand M, Masuda M, Wehner N, Yu X-H (2010) Ant colony optimization algorithm for robot path planning. Int Conf Comp Design Appl 3:V3-436
28.
Ouaarab A, Ahiod B, Yang X-S (2013) Discrete cuckoo search algorithm for the travelling salesman problem. Neur Comp Appl 24:1659–1669CrossRef
29.
Yusof Z, Hong T, Zainal AAF, Salam M, Adam A, Khalil K, Mukred J, Husin N. Shaikh, Ibrahim Z (2011) A two-step binary particle swarm optimization approach for routing in VLSI with iterative RLC delay model, 09
30.
Maire BL, Mladenov V (2012) Comparison of neural networks for solving the travelling salesman problem, 09
31.
Abdel-Moetty S (2010) Traveling salesman problem using neural network techniques, pp. 1–6, 04
32.
Vanneste S, Bellekens B, Weyn M (2014) 3dvfh+: real-time three-dimensional obstacle avoidance using an octomap, 1319, 07
33.
Thantulage G, Kalganova T, Wilson M (2008) Grid based and random based ant colony algorithms for automatic hose routing in 3d space. Int J Comp Info Eng 2(2):510–516
34.
ma X, Iida K, Xie M, Nishino J, Odaka T, Ogura H (2006) A genetic algorithm for the optimization of cable routing,. Sys Comp Japan 37(06):61–71CrossRef
35.
Sandurkar S, Chen W (2000) Gaprus - genetic algorithms based pipe routing using tessellated objects. Comp Ind 38(08):209–223
36.
Khan M, Khiyal S (2004) Obstacle avoidance and self-localization system for autonomous vehicles. IFAC Proceed Vol 37(07):519–524CrossRef
37.
Angus D (2007) Crowding population-based ant colony optimisation for the multi-objective travelling salesman problem, 2007 IEEE Symposium on computational intelligence in multi-criteria decision-making, pp. 333–340
38.
Tan X, Zhuo X, Zhang J (2006) Ant colony system for optimizing vehicle routing problem with time windows (vrptw). In: Huang DS, Li K, Irwin GW (eds) Computational intelligence and bioinformatics. Springer, Berlin and Heidelberg, pp 33–38CrossRef
39.
Pinto D, Barán B (2006) Multiobjective multicast routing with ant colony optimization. In: Gaiti D (ed) Network control and engineering for Qos Security and Mobility. Springer, Boston, pp 101–115CrossRef
40.
Chen SM, Chien C-Y (2011) Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Exp Sys Appl 38(12):14439–14450CrossRef
41.
Shi X, Liang Y, Lee H, Lu C, Wang Q (2007) Particle swarm optimization-based algorithms for tsp and generalized tsp. Infor Process Lett 103(5):169–176CrossRefMATHMathSciNet
42.
43.
Yu B, Yang Z-Z, Yao B (2009) An improved ant colony optimization for vehicle routing problem. Eur J Operat Res 196(1):171–176CrossRefMATH
44.
Honglin Y, Jijun Y (2002) An improved genetic algorithm for the vehicle routing problem
45.
Rego C, Roucairol C (1996) A parallel tabu search algorithm using ejection chains for the vehicle routing problem. Springer, Boston, MA, pp 661–675MATH
Metadata
Title
Algorithms for path optimizations: a short survey
Authors
S C M S De Sirisuriya
T G I Fernando
M K A Ariyaratne
Publication date
07-11-2022
Publisher
Springer Vienna
Published in
Computing / Issue 2/2023
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI
https://doi.org/10.1007/s00607-022-01126-w

Other articles of this Issue 2/2023

Computing 2/2023 Go to the issue

Regular Paper

Constraint-based debugging in probabilistic model checking

Regular Paper

HaSGP: an effective graph partition method for heterogeneous-aware

Regular Paper

Time series-based workload prediction using the statistical hybrid model for the cloud environment

Regular Paper

Community detection algorithms for recommendation systems: techniques and metrics

Regular Paper

Meddal: meeting deadlines and data locality via bin packing in cloud environment

Regular Paper

Microservice compositions based on the choreography of BPMN fragments: facing evolution issues

Premium Partner

    Image Credits