Optimal N-Paths Generation Algortihm for Euclidean Distances

Nishant S P


The Optimal Route Generation algorithm is designed to solve the problem of vehicle routing for real life scenarios. It is used to obtain
the set of n minimal routes from a single source to a set of destination points thus forming an optimal n paths network. The Vehicle
routing problem (VRP) is an optimal route generation problem seeking to service a number of customers with a fleet of vehicles. Since
the optimization of the distance traversed is considered in, the vehicle routing problem reduces to a Hamiltonian path problem for
Euclidean instances. The real life need for such an algorithm is great. Traditional algorithms which solve the Hamiltonian path problem
are NP complete algorithms and cannot be used on large data sets. Hence there is a pressing need for an algorithm which can find a
solution to the Hamiltonian path problem in a vehicle routing context in polynomial time so that large number of passengers can be
deployed on vehicles which traverse pre determined optimal routes that cover all destination points. This would enable the vehicle
operators to save time and fuel which would automatically translate into saving in operating costs and hence increase in their profits.


Hamiltonian path, Vehicle routing problem, Dynamic route changing, Travelling Salesman problem, optimal route generation algorithm

Full Text:



  • There are currently no refbacks.