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.
[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).
Shojaie, A. A. and Seyedi Bariran, S. E. (2021). A Comparison of Extended Dijkstra and ACO Algorithm for Shortest Path Problem in Dynamic Networks with Delay Times. Advances in Industrial Engineering, 55(1), 1-26. doi: 10.22059/jieng.2021.325262.1773
MLA
Shojaie, A. A. , and Seyedi Bariran, S. E. . "A Comparison of Extended Dijkstra and ACO Algorithm for Shortest Path Problem in Dynamic Networks with Delay Times", Advances in Industrial Engineering, 55, 1, 2021, 1-26. doi: 10.22059/jieng.2021.325262.1773
HARVARD
Shojaie, A. A., Seyedi Bariran, S. E. (2021). 'A Comparison of Extended Dijkstra and ACO Algorithm for Shortest Path Problem in Dynamic Networks with Delay Times', Advances in Industrial Engineering, 55(1), pp. 1-26. doi: 10.22059/jieng.2021.325262.1773
CHICAGO
A. A. Shojaie and S. E. Seyedi Bariran, "A Comparison of Extended Dijkstra and ACO Algorithm for Shortest Path Problem in Dynamic Networks with Delay Times," Advances in Industrial Engineering, 55 1 (2021): 1-26, doi: 10.22059/jieng.2021.325262.1773
VANCOUVER
Shojaie, A. A., Seyedi Bariran, S. E. A Comparison of Extended Dijkstra and ACO Algorithm for Shortest Path Problem in Dynamic Networks with Delay Times. Advances in Industrial Engineering, 2021; 55(1): 1-26. doi: 10.22059/jieng.2021.325262.1773
)