Modeling and analysis of the coordinated vehicle routing problem
Roger Mailler, Melanie Smith · 2011
Traffic congestion is a widespread epidemic that continually wreaks havoc in urban areas. Traffic jams, car wrecks, construction delays, and other causes of congestion can turn even the biggest highways into a parking lot. In attempts to mitigate this problem, thee U.S. Department of Transportation (DoT) spends a large portion of its budget attempting to communicate with drivers about upcoming traffic delays. DoT hopes that drivers will receive the road status information and subsequently adapt their travel plans to reduce their delay by taking an alternate route, leaving at a different time, or using a different mode of transportation. With the emergence and wide-spread popularity of GPS (Global Positioning System) technology, drivers are no longer limited by their familiarity of an area to find a detour around congestion since GPS devices provide maps and directions. This work focuses specifically on intelligent route planning and replanning, combining advanced GPS capabilities with a multi-agent systems approach to not only guide drivers based on map data, but also based on known congestion information and the knowledge of what other vehicles are planning to do. The major contributions of this work will include: a formal definition of the Coordinated Vehicle Routing Problem (CVRP); a novel mesoscopic traffic modeling environment that accounts for heterogeneous vehicle populations; a dynamic decision making model for routing and rerouting vehicles using congestion data; a simulation environment for testing and comparing different approaches to solving the CVRP; and experimentation with different problem solving techniques that vary the degree of centralization.