Congestion avoiding heuristic path generation for the proactive route guidance

The benefits in reducing traffic congestion of system optimum with respect to user equilibrium traffic assignments are well-known. Recently a linear programming based approach was proposed that aims at achieving a compromise between the system perspective, namely eliminating congestion, and the user perspective, that is minimizing individual travel times. The approach, called proactive route guidance, assigns to users paths that increase the travel times by at most a given percentage, called Maximum allowed travel inconvenience. The approach requires the enumeration of all feasible paths that may be memory and time consuming, especially when large networks and/or high values of the Maximum allowed travel inconvenience are considered. In this paper a heuristic is presented to generate a subset of all feasible paths that is based on the iterative search of improving paths. Computational experiments show that the number of paths generated by the heuristic is smaller with respect to the complete set by one or two orders of magnitude on small instances and by higher orders of magnitude when the size of the instances increases. On instances with 150 nodes, where the complete enumeration takes an acceptable computational time, the results show that the quality of the heuristic solutions is very close to that of the optimal ones.