A Comparison of Extended Dijkstra and ACO Algorithm for Shortest Path Problem in Dynamic Networks with Delay Times

Document Type : Research Paper

Authors

School of Industrial Engineering, Islamic Azad University, South Tehran Branch, Tehran, Iran

Abstract

Shortest path problem is a typical routing optimization problem that is generally involved with a multi-criteria decision-making process. Therefore, the main objective of this paper is to find the shortest path in discrete-time dynamic networks based on bi-criteria of time and reliability by considering the effect of delay times that varies according to different departure time scenarios. Firstly, the well-known single-criterion Dijkstra’s algorithm is extended to fit the conditions of a bi-criteria problem. The solutions obtained from the extended Dijkstra was then compared with a proposed ant colony optimization (ACO) algorithm via a set of multi-objective performance metrics including CPU time, error ratio, spacing and diversity metrics. The analysis was made based on three network scales ranged from small (20-100 nodes), to medium (500-1900 nodes) and large (2000-10000 nodes). The computational results obtained from the analysis suggested that the extended Dijkstra’s algorithm has a higher efficiency in medium and large scaled networks. Furthermore, the comparison of the proposed ACO versus Dijkstra’s algorithm proved the preference of ACO for networks with larger-scaled (nodes over 5000), while, for smaller and medium-scaled networks (nodes 20-2000), the extended Dijkstra’s algorithm has a dominantly better performance in CPU time as compared to proposed ACO.

Keywords

References

  • [1] Q. V. Martins, "On a multicriteria shortest path problem," European Journal of Operational Research, vol. 16, pp. 236-245, 1984.
  • [2] Skutella, "An introduction to network flows over time," in Research Trends in Combinatorial Optimization, ed: Springer, 2009, pp. 451-482.
  • [3] Ford and D. R. Fulkerson, Flows in networks vol. 1962: Princeton Princeton University Press, 1962.
  • [4] E. Aronson, "A survey of dynamic network flows," Annals of Operations Research, vol. 20, pp. 1-66, 1989.
  • [5] Kotnyek, "An annotated overview of dynamic network flows," 2003.
  • [6] A. Aloul, B. Al-Rawi, and M. Aboelaze, "Routing in Optical and Non-Optical Networks using Boolean Satisfiability," JCM, vol. 2, pp. 49-56, 2007.
  • [7] Dwivedi, R. Srivastava, P. Kalra, and Y. Singh, "Simplified neural network architecture for shortest path planning in optical network," in TENCON 2008-2008 IEEE Region 10 Conference, 2008, pp. 1-4.
  • [8] Erlebach and S. Stefanakos, "Wavelength conversion in shortest-path all-optical networks," Lecture notes in computer science, pp. 595-604, 2003.
  • [9] B. A. Teixeira, C. T. Batista, A. J. F. Cardoso, and J. d. S. Araújo, "A Genetic Algorithm Approach for Static Routing and Wavelength Assignment in All-Optical WDM Networks," in Portuguese Conference on Artificial Intelligence, 2017, pp. 421-432.
  • [10] Bhanja and D. Mishra, "Quality of service aware fuzzy dynamic routing and wavelength assignment technique in all optical networks," Photonic Network Communications, pp. 1-15, 2017.
  • [11] Gajendran, M. Pradeep, and S. B. Prabhu, "Systematic Analysis of Congestion Control in WDM Mesh Networks," Asian Journal of Applied Science and Technology (AJAST), vol. 1, p. 1, 2017.
  • [12] K. Pradhan, S. Keshri, K. Das, and T. De, "A heuristic approach based on dynamic multicast traffic grooming in WDM mesh networks," Journal of Optics, vol. 46, pp. 51-61, 2017.
  • [13] Ford Jr and D. R. Fulkerson, "Solving the transportation problem," Management Science, vol. 3, pp. 24-32, 1956.
  • [14] Bellman, "On a routing problem," DTIC Document1956.
  • [15] Brumbaugh-Smith and D. Shier, "An empirical investigation of some bicriterion shortest path algorithms," European Journal of Operational Research, vol. 43, pp. 216-224, 1989.
  • [16] J. Skriver and K. A. Andersen, "A label correcting approach for solving bicriterion shortest-path problems," Computers & Operations Research, vol. 27, pp. 507-524, 2000.
  • [17] Warburton, "Approximation of Pareto optima in multiple-objective, shortest-path problems," Operations research, vol. 35, pp. 70-79, 1987.
  • [18] Hassin, "Approximation schemes for the restricted shortest path problem," Mathematics of Operations research, vol. 17, pp. 36-42, 1992.
  • [19] H. Lorenz and D. Raz, "A simple efficient approximation scheme for the restricted shortest path problem," Operations Research Letters, vol. 28, pp. 213-219, 2001.
  • [20] Hao, D. Zhang, and X. Feng, "Model and algorithm for shortest path of multiple objectives," Journal of Southwest Jiaotong University, vol. 42, pp. 641-646, 2007.
  • [21] Y. Chen, W. H. Lam, A. Sumalee, Q. Li, and M. L. Tam, "Reliable shortest path problems in stochastic time-dependent networks," Journal of Intelligent Transportation Systems, vol. 18, pp. 177-189, 2014.
  • [22] Kwon, T. Lee, and P. Berglund, "Robust shortest path problems with two uncertain multiplicative cost coefficients," Naval Research Logistics (NRL), vol. 60, pp. 375-394, 2013.
  • [23] L. Chen and K. Tang, "Finding the Kth shortest path in a time‐schedule network," Naval Research Logistics (NRL), vol. 52, pp. 93-102, 2005.
  • [24] K. Cheung, "Iterative methods for dynamic stochastic shortest path problems," Naval Research Logistics (NRL), vol. 45, pp. 769-789, 1998.
  • [25] Murthy and S. S. Her, "Solving min‐max shortest‐path problems on a network," Naval Research Logistics (NRL), vol. 39, pp. 669-683, 1992.
  • [26] Tufekci, "Decomposition algorithms for finding the shortest path between a source node and a sink node of a network," Naval Research Logistics Quarterly, vol. 30, pp. 387-396, 1983.
  • [27] K. Ahuja, "Network flows," TECHNISCHE HOCHSCHULE DARMSTADT, 1993.
  • [28] Batta and S. S. Chiu, "Optimal obnoxious paths on a network: transportation of hazardous materials," Operations Research, vol. 36, pp. 84-92, 1988.
  • [29] R. Current, "Multiobjective design of transportation networks," 1981.
  • [30] Current and M. Marsh, "Multiobjective transportation network design and routing problems: Taxonomy and annotation," European Journal of Operational Research, vol. 65, pp. 4-19, 1993.
  • [31] Liu, H. Mu, H. Luo, and X. Li, "A simulated annealing for multi-criteria network path problems," Computers & Operations Research, vol. 39, pp. 3119-3135, 2012.
  • [32] Huang and S. Gao, "Optimal paths in dynamic networks with dependent random link travel times," Transportation Research Part B: Methodological, vol. 46, pp. 579-598, 2012.
  • [33] M. Nie and X. Wu, "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, vol. 43, pp. 597-613, 2009.
  • [34] C. Bezerra, E. F. Goldbarg, L. S. Buriol, and M. C. Goldbarg, "Grace: A generational randomized ACO for the multi-objective shortest path problem," in Evolutionary Multi-Criterion Optimization, 2011, pp. 535-549.
  • [35] Abbasi and S. Ebrahimnejad, "The cross-entropy method for solving bi-criteria network flow problems in discrete-time dynamic networks," Optimization Methods and Software, pp. 1-19, 2014.
  • [36] B. Reinhardt and D. Pisinger, "Multi-objective and multi-constrained non-additive shortest path problems," Computers & Operations Research, vol. 38, pp. 605-616, 2011.
  • [37] Nasrabadi and S. M. Hashemi, "Minimum cost time-varying network flow problems," Optimization Methods & Software, vol. 25, pp. 429-447, 2010.
  • [38] Maniezzo, M. Dorigo, V. Maniezzo, and A. Colorni, "Ant System: An Autocatalytic Optimizing Process," 1991.
  • [39] Dorigo and M. Birattari, "Ant colony optimization," in Encyclopedia of machine learning, ed: Springer, 2010, pp. 36-39.
  • [40] Dorigo, M. Birattari, and T. Stützle, "Ant colony optimization," Computational Intelligence Magazine, IEEE, vol. 1, pp. 28-39, 2006.
  • [41] Ekmen, Elçin Duygu. "A Study on Performance Evaluation of Optimization Algorithms in the Shortest Path Problem." PhD diss., Ankara Yıldırım Beyazıt Üniversitesi Fen Bilimleri Enstitüsü, 2020.
  • [42] Li, Xuan, Xiaofei Ye, and Lili Lu. "Dynamic Programming Approaches for Solving Shortest Path Problem in Transportation: Comparison and Application." In Green, Smart and Connected Transportation Systems, pp. 141-160. Springer, Singapore, 2020.
  • [43] Kumawat, Sunita, Chanchal Dudeja, and Pawan Kumar. "An Extensive Review of Shortest Path Problem Solving Algorithms." In 2021 5th International Conference on Intelligent Computing and Control Systems (ICICCS), pp. 176-184. IEEE, 2021.
  • [44] Hughes, Michael S., Brian J. Lunday, Jeffrey D. Weir, and Kenneth M. Hopkinson. "The multiple shortest path problem with path de-confliction." European Journal of Operational Research 292, pp.818-829, no. 3 (2021).
Advances in Industrial Engineering
Volume 55, Issue 1
January 2021
Pages 1-26

Files

Share

How to cite

Statistics