Skip to main content
Top
Published in: Calcolo 1/2018

01-03-2018

A numerical method for solving shortest path problems

Authors: M. H. Noori Skandari, M. Ghaznavi

Published in: Calcolo | Issue 1/2018

Log in

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

search-config
loading …

Abstract

Chebyshev pseudo-spectral method is one of the most efficient methods for solving continuous-time optimization problems. In this paper, we utilize this method to solve the general form of shortest path problem. Here, the main problem is converted into a nonlinear programming problem and by solving of which, we obtain an approximate shortest path. The feasibility of the nonlinear programming problem and the convergence of the method are given. Finally, some numerical examples are considered to show the efficiency of the presented method over the other methods.

Dont have a licence yet? Then find out more about our products and how to get one 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!

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!

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!

Literature
1.
go back to reference Borzabadi, A.H., Kamyad, A.V., Farahi, M.H., Mehne, H.H.: Solving some optimal path planning problems using an approach based on measure theory. Appl. Math. Comput. 170, 1418–1435 (2005)MathSciNetMATH Borzabadi, A.H., Kamyad, A.V., Farahi, M.H., Mehne, H.H.: Solving some optimal path planning problems using an approach based on measure theory. Appl. Math. Comput. 170, 1418–1435 (2005)MathSciNetMATH
2.
go back to reference Canuto, C., Hussaini, Y., Quarteroni, A., Zang, T.A.: Spectral Methods in Fluid Dynamics (Scientific Computation). Springer, New York (1987)MATH Canuto, C., Hussaini, Y., Quarteroni, A., Zang, T.A.: Spectral Methods in Fluid Dynamics (Scientific Computation). Springer, New York (1987)MATH
3.
4.
go back to reference Fahroo, F., Ross, I.M.: Costate estimation by a legendre pseudospectral method. J. Guid. Control Dyn. 24(2), 270–277 (2001)CrossRef Fahroo, F., Ross, I.M.: Costate estimation by a legendre pseudospectral method. J. Guid. Control Dyn. 24(2), 270–277 (2001)CrossRef
5.
go back to reference Fahroo, F., Ross, I.M.: Direct trajectory optimization by a Chebyshev pseudospectral method. J. Guid. Control Dyn. 25(1), 160–166 (2002)CrossRef Fahroo, F., Ross, I.M.: Direct trajectory optimization by a Chebyshev pseudospectral method. J. Guid. Control Dyn. 25(1), 160–166 (2002)CrossRef
6.
go back to reference Freud, G.: Orthogonal Polynomials. Pregamon Press, Elmsford (1971)MATH Freud, G.: Orthogonal Polynomials. Pregamon Press, Elmsford (1971)MATH
8.
go back to reference Gong, Q., Kang, W., Ross, I.M.: A pseudospectral method for the optimal control of constrained feedback linearizable systems. IEEE Trans. Autom. Control 51(7), 1115–1129 (2006)MathSciNetCrossRefMATH Gong, Q., Kang, W., Ross, I.M.: A pseudospectral method for the optimal control of constrained feedback linearizable systems. IEEE Trans. Autom. Control 51(7), 1115–1129 (2006)MathSciNetCrossRefMATH
9.
go back to reference Gong, Q., Ross, I.M., Kang, W., Fahroo, F.: Connections between the covector mapping theorem and convergence of pseudospectral methods for optimal control. Comput. Optim. Appl. 41(3), 307–335 (2008)MathSciNetCrossRefMATH Gong, Q., Ross, I.M., Kang, W., Fahroo, F.: Connections between the covector mapping theorem and convergence of pseudospectral methods for optimal control. Comput. Optim. Appl. 41(3), 307–335 (2008)MathSciNetCrossRefMATH
11.
go back to reference Lu, Y., Yi, S., Liu, Y., Ji, Y.: A novel path planning method for biomimetic robot based on deep learning. Assem. Autom. 36(2), 186–191 (2016)CrossRef Lu, Y., Yi, S., Liu, Y., Ji, Y.: A novel path planning method for biomimetic robot based on deep learning. Assem. Autom. 36(2), 186–191 (2016)CrossRef
12.
go back to reference Ma, Y., Zamirian, M., Yang, Y., Xu, Y., Zhang, J.: Path planning for mobile objects in four-dimension based on particle swarm optimization method with penalty function. Math. Probl. Eng. 2013, 1–9 (2013) Ma, Y., Zamirian, M., Yang, Y., Xu, Y., Zhang, J.: Path planning for mobile objects in four-dimension based on particle swarm optimization method with penalty function. Math. Probl. Eng. 2013, 1–9 (2013)
13.
go back to reference Mortezaee, M., Nazemi, A.: A wavelet collocation scheme for solving some optimal path planning problems. ANZIAM 57, 461–481 (2015)MathSciNetMATH Mortezaee, M., Nazemi, A.: A wavelet collocation scheme for solving some optimal path planning problems. ANZIAM 57, 461–481 (2015)MathSciNetMATH
14.
go back to reference Noori Skandari, M.H., Ghaznavi, M.: Chebyshev pseudo-spectral method for Bratu’s problem. Iran. J. Sci. Technol. Trans. A Sci. 41, 913–921 (2017)MathSciNetCrossRef Noori Skandari, M.H., Ghaznavi, M.: Chebyshev pseudo-spectral method for Bratu’s problem. Iran. J. Sci. Technol. Trans. A Sci. 41, 913–921 (2017)MathSciNetCrossRef
15.
go back to reference Noori Skandari, M.H., Kamyad, A.V., Effati, S.: Generalized Euler–Lagrange equation for nonsmooth calculus of variations. Nonlinear Dyn. 75(1–2), 85–100 (2014)MathSciNetCrossRefMATH Noori Skandari, M.H., Kamyad, A.V., Effati, S.: Generalized Euler–Lagrange equation for nonsmooth calculus of variations. Nonlinear Dyn. 75(1–2), 85–100 (2014)MathSciNetCrossRefMATH
16.
go back to reference Noori Skandari, M.H., Kamyad, A.V., Effati, S.: Smoothing approach for a class of nonsmooth optimal control problems. Appl. Math. Model. 40(2), 886–903 (2016)MathSciNetCrossRef Noori Skandari, M.H., Kamyad, A.V., Effati, S.: Smoothing approach for a class of nonsmooth optimal control problems. Appl. Math. Model. 40(2), 886–903 (2016)MathSciNetCrossRef
17.
18.
go back to reference Otte, M., Correll, N.: C-FOREST: parallel shortest path planning with superlinear speedup. IEEE Robot. Autom. Soc. 29(3), 798–806 (2013) Otte, M., Correll, N.: C-FOREST: parallel shortest path planning with superlinear speedup. IEEE Robot. Autom. Soc. 29(3), 798–806 (2013)
19.
go back to reference Polak, E.: Optimization: Algorithms and Consistent Approximations. Springer, Heidelberg (1997)CrossRefMATH Polak, E.: Optimization: Algorithms and Consistent Approximations. Springer, Heidelberg (1997)CrossRefMATH
20.
go back to reference Shen, J., Tang, T., Wang, L.L.: Spectral Methods: Algorithm, Analysis and Applications. Springer, Berlin (2011)CrossRefMATH Shen, J., Tang, T., Wang, L.L.: Spectral Methods: Algorithm, Analysis and Applications. Springer, Berlin (2011)CrossRefMATH
21.
go back to reference Tohidi, E., Samadi, O.R.N.: Legendre spectral collocation method for approximating the solution of shortest path problems. Syst. Sci. Control Eng. 3, 62–68 (2015)CrossRef Tohidi, E., Samadi, O.R.N.: Legendre spectral collocation method for approximating the solution of shortest path problems. Syst. Sci. Control Eng. 3, 62–68 (2015)CrossRef
22.
go back to reference Trefethen, L.N.: Spectral Methods in MATLAB. Society for Industrial and Applied Mathematics, Philadelphia (2000)CrossRefMATH Trefethen, L.N.: Spectral Methods in MATLAB. Society for Industrial and Applied Mathematics, Philadelphia (2000)CrossRefMATH
23.
go back to reference Wang, Y., Lane, D.M., Falconer, G.J.: Two novel approaches for unmanned under water vehicle path planning: constrained optimisation and semi-infinite constrained optimisation. Robotica 18, 123–142 (2000)CrossRef Wang, Y., Lane, D.M., Falconer, G.J.: Two novel approaches for unmanned under water vehicle path planning: constrained optimisation and semi-infinite constrained optimisation. Robotica 18, 123–142 (2000)CrossRef
24.
go back to reference Zamirian, M., Farahi, M.H., Nazemi, A.R.: An applicable method for solving the shortest path problems. Appl. Math. Comput. 190, 1479–1486 (2007)MathSciNetMATH Zamirian, M., Farahi, M.H., Nazemi, A.R.: An applicable method for solving the shortest path problems. Appl. Math. Comput. 190, 1479–1486 (2007)MathSciNetMATH
25.
go back to reference Zamirian, M., Kamyad, A.V., Farahi, M.H.: A novel algorithm for solving optimal path planning problems based on parametrization method and fuzzy aggregation. Phys. Lett. A 373(38), 3439–3449 (2009)CrossRefMATH Zamirian, M., Kamyad, A.V., Farahi, M.H.: A novel algorithm for solving optimal path planning problems based on parametrization method and fuzzy aggregation. Phys. Lett. A 373(38), 3439–3449 (2009)CrossRefMATH
Metadata
Title
A numerical method for solving shortest path problems
Authors
M. H. Noori Skandari
M. Ghaznavi
Publication date
01-03-2018
Publisher
Springer Milan
Published in
Calcolo / Issue 1/2018
Print ISSN: 0008-0624
Electronic ISSN: 1126-5434
DOI
https://doi.org/10.1007/s10092-018-0256-5

Other articles of this Issue 1/2018

Calcolo 1/2018 Go to the issue

Premium Partner