Congestion avoiding heuristic path generation for the proactive route guidance
| Autor: | Enrico Angelelli, Maria Grazia Speranza, Valentina Morandi |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
General Computer Science Linear programming Computer science media_common.quotation_subject 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Proactive route guidance Orders of magnitude (bit rate) Set (abstract data type) 0502 economics and business Enumeration Quality (business) Heuristic path generation Traffic congestion Computer Science (all) Modeling and Simulation media_common 050210 logistics & transportation 021103 operations research Heuristic 05 social sciences Perspective (graphical) |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|