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 اصل مقاله (912.74 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jieng.2021.325262.1773 | ||
| نویسندگان | ||
| Amir abbas Shojaie* ؛ Seyed Esmail Seyedi Bariran | ||
| School of Industrial Engineering, Islamic Azad University, South Tehran Branch, Tehran, Iran | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| shortest path problem؛ Ant colony؛ Dijkstra؛ delay time؛ dynamic network | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 1,109 تعداد دریافت فایل اصل مقاله: 879 |
||