a comparison of extended dijkstra and aco algorithm for shortest path problem in dynamic networks with delay times

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- scale networks (nodes 20-2000), the extended dijkstra’s algorithm has a dominantly better performance in cpu time as compared to proposed aco.