Algorithms to Find Shortest Paths with Added Constraint on Travel Fuel Consumption for Transportation Networks

摘要

In this work, the shortest path (SP) Dijkstra algorithm is re-visited and modified so that the modified Dijkstra algorithm can perform the task of finding the shortest path (SP) with an added constraint on fuel consumption, which is assumed to be linearly related to the CO2 emissions. For the SP with added constraint problem, the "traditional, classical" Dijkstra algorithm is not suitable, thus 4 different algorithms/strategies are proposed, such as (a) finding the k-th successive SP, (b) the lagrange multipliers, (c) linear integer programming (LIP) formulation, and (d) based on using the genetic algorithm (GA). Several small-scale (academic) networks, as well as real-life (large-scale) networks, are used to study the numerical performance of 4 proposed algorithms. Numerical results have indicated that (using reliability and efficiency as first and second criteria, respectively) LIP, k-th successive SP, GA, and Lagrange multipliers can be ranked as 1st, 2nd, 3rd, and 4th, respectively.