Open Access
H. Fathima
T. Vadivel
- Assistant Professor K.S.R College of Engineering Tamil Nadu India
- Assistant Professor K.S.R. College of Arts and Science Tamil Nadu India
Abstract
The term “vehicle routing problem” (VRP) refers to optimization issues in the transportation, distribution, and logistics industries. They primarily concentrate on supplying a large number of customers with a variety of cars. Function of vehicle routing problem VRP is Determine the best path from a starting point to a road map destination using route planning tools. Because road traffic circumstances (e.g., congestion level, road incidents, etc.) can change during a car trip, the best route should be re-evaluated as soon as fresh traffic data becomes available. A significant difficulty for any transportation application is selecting an acceptable route planning method from the literature to use in real-world road networks.The Simulation of Urban Mobility (SUMO) package and TRACI were used to simulate the behaviour of these algorithms during runtime. The most well-known shortest route algorithm, Dijkstra, was the first SUMO algorithm to be implemented. We use TRACI to re-apply the algorithm and adapt a car’s route in response to any changes in traffic conditions that affect the current best route. My goal is to replicate various algorithms and assess how well they perform based on the quality of the best route found.
Keywords: Vehicles’ Routing Problem, Shortest Path, Dijkstra Algorithm, Bellman-Ford-Moore,Topological Ordering.
References
1. F. Zhan, Three fastest shortest path algorithms on real road networks: Data structures and procedures, Journal of Geographic Information and Decision Analysis, vol. 1, no. 1, pp. 70-82, 1997
2. H. Kanoh, Dynamic route planning for car navigation systems using virus genetic algorithms, International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 11, pp. 65-78, Jan. 2007.
3. H. Kanoh and K. Hara, Hybrid genetic algorithm for dynamic multi objective route planning with predicted traffic in a real-world road network, in Proceedings of the 10th annual conference on Genetic and evolutionary computation – GECCO 08, (New York, NY, USA), p. 657, ACM Press, July 2008.
4. M. Behrisch, L. Bieker, J. Erdmann, and D. Krajzewicz, SUMO – Simulation of Urban Mobility – an Overview, in SIMUL 2011, The Third International Conference on Advances in System Simulation, (Barcelona, Spain), pp. 55-60, 2011.
5. G. Ghiani, F. Guerriero, G. Laporte, and R. Musmanno, Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies, European Journal of Operational Research, vol. 151, pp. 1- 11, Nov. 2003.
6. M. Fu, J. Li, and Z. Deng, A practical route planning algorithm for vehicle navigation system, in Fifth World Congress on Intelligent Control and Automation, vol. 6, pp. 5326-5329, IEEE, 2004.
7. F. B. Zhan and C. E. Noon, Shortest Path Algorithms: An Evaluation Using Real Road Networks, Transportation Science, vol. 32, pp. 65-73, Feb. 1998.
8. R. E. Korf, Real-time heuristic search, Artificial Intelligence, vol. 42, pp. 189-211, Mar. 1990.
9. B. Tatomir, L. J. M. Rothkrantz, and A. C. Suson, Travel time prediction for dynamic routing using ant based control, in Winter Simussslation Conference, pp. 1069-1078, Dec. 2009
10. T.-Y. Liao and T.-Y. Hu, An object-oriented evaluation framework for dynamic vehicle routing problems under real-time information, Expert Systems with Applications, vol. 38, pp. 12548-12558, Sept. 2011.
| Volume | |
| Received | March 20, 2022 |
| Accepted | April 4, 2022 |
| Published | January 4, 2023 |