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
Calcolo
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.
previous article An extended nonsymmetric block Lanczos method for model reduction in large scale dynamical systems

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!

inform 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
Literature
1.
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.
Canuto, C., Hussaini, Y., Quarteroni, A., Zang, T.A.: Spectral Methods in Fluid Dynamics (Scientific Computation). Springer, New York (1987)MATH
3.
4.
Fahroo, F., Ross, I.M.: Costate estimation by a legendre pseudospectral method. J. Guid. Control Dyn. 24(2), 270–277 (2001)CrossRef
5.
Fahroo, F., Ross, I.M.: Direct trajectory optimization by a Chebyshev pseudospectral method. J. Guid. Control Dyn. 25(1), 160–166 (2002)CrossRef
6.
Freud, G.: Orthogonal Polynomials. Pregamon Press, Elmsford (1971)MATH
7.
8.
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.
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
10.
11.
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.
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.
Mortezaee, M., Nazemi, A.: A wavelet collocation scheme for solving some optimal path planning problems. ANZIAM 57, 461–481 (2015)MathSciNetMATH
14.
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.
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.
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.
Otte, M., Correll, N.: C-FOREST: parallel shortest path planning with superlinear speedup. IEEE Robot. Autom. Soc. 29(3), 798–806 (2013)
19.
Polak, E.: Optimization: Algorithms and Consistent Approximations. Springer, Heidelberg (1997)CrossRefMATH
20.
Shen, J., Tang, T., Wang, L.L.: Spectral Methods: Algorithm, Analysis and Applications. Springer, Berlin (2011)CrossRefMATH
21.
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.
Trefethen, L.N.: Spectral Methods in MATLAB. Society for Industrial and Applied Mathematics, Philadelphia (2000)CrossRefMATH
23.
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.
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.
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

OriginalPaper

Optimal vorticity accuracy in an efficient velocity–vorticity method for the 2D Navier–Stokes equations

OriginalPaper

Some error analysis on virtual element methods

OriginalPaper

Nonlinear Galerkin methods for a system of PDEs with Turing instabilities

OriginalPaper

On the dense unbounded divergence of interpolatory product integration on Jacobi nodes

OriginalPaper

Iterative methods for zeros of a monotone variational inclusion in Hilbert spaces

OriginalPaper

An inexact Newton method for solving complementarity problems in hydrodynamic lubrication

Premium Partner

    Image Credits