We are focussed on developing a comprehensive vehicle routing system that adapts to the particularities of urban scheduling. Our powerful model for vehicle scheduling in cities operates according to the following conditions:
There are two important components that need to be tackled in developing our comprehensive vehicle scheduling system:
snapshot" of the current roadway situation, computing a near optimal schedule is
extremely hard. Moreover, such a schedule has to be computed quickly; otherwise new events such as new jobs,
changes in road conditions, etc. make the schedule unrealistic. We have used the local search technique
coupled with an approach based on column generation to find a near optimal schedule.
While this general philosophy is applicable in various routing and scheduling problems, the quality and
efficiency of the approach depends on the ability to generate appropriate columns which in turn reduces to
another optimization problem. Because of the additional restrictions in our applications and the context in
which the column generation is used, a practically viable column generation method for our problems
needs much more sophistication than straightforward adaptations of the method.
The calculation of these travel times is different from the calculation of travel times for intercity transportation. We are interested in monitoring the road conditions for any events that might affect the traffic in some parts of the city. Our approach of collecting road information from GPS tracking data will form the basis of our future work.
We are working on a set of algorithms that will predict, with a high degree of accuracy, the travel
time of a vehicle in any city road network at any given time. This requires a tremendous amount of data and data
processing. The result will be a real-time tool, which will estimate travel time based on actual observed
speeds by time of day on the roads ahead. Currently, the system allows the user to change the road network
characteristics manually. Once the changes are made, the system then computes travel times on the fly.
In the comprehensive routing systems, this process will be handled by the system.
Next Generation Transportation System
Developments in wireless communications, anywhere accessibility of the Internet, hand-held devices,
sensor networks, and geographic information systems (GIS) have been paving way for novel applications
in the field of road transportation. Road networks and vehicles, equipped with communication
infrastructures and computing capabilities and connected to the Internet, are commonly referred to as
intelligent transportation systems (ITS) [22]. For example, radio and TV channels provide periodic
updates on road and traffic conditions on major highways, tolls are collected by using overhead sensors
and cameras, and GPS (global positioning system) assisted routing with onboard computers is slowly
gaining popularity. The COMPASS system of the Ministry of Transportation of Ontario, the RESCU system of
city of Toronto, the Electronic Toll Road (ETR) 407 in Ontario, and numerous GPS-based navigation systems
in the market amply demonstrate the potential of ITS systems and applications. In the COMPASS system, data
from the sensors, which are deployed underneath the pavement, are transmitted to a central site via a
wired network, and verified by human observers on a closed-circuit TV network. Travel information from the
central site is delivered to drivers via overhead displays and radio/TV channels. Mexico City, Lisbon, Bordeaux,
and Beijing use a real-time centralized system called GERTRUDE to control intersections and give priority
to public transports [25]. Governments, auto makers, standardization bodies, and researchers have been
making a concerted effort to develop novel ITS systems. Among applications, advanced traveler information
systems (ATIS), novel traffic light control systems, automatic toll collection systems, navigation systems,
and driver warning systems are on the rise. Less congestion, less travel time and distance, and availability
of safety information are important to drivers.
Literature Review
A. Traffic Control Algorithms: The key ideas in traffic control are as follows: (i) in normal conditions,
enable cars to move at their free-flow speeds; (ii) when incidents occur, minimize their impacts.
Researchers have studied and evaluated traffic control algorithms using the following metrics:
waiting time [56], delay [41], travel time [41],
percentage of stopped cars [24], density of cars [45], global flow [2], and
fairness [41]. Those reports do not address environmental impacts. A key concept in vehicle routing
and traffic control is automatic detection of incidents and congestion. Though an ITS system can be
manually updated with incidents, researchers have shown the feasibility of automated detection by
means of VANETs [20].
B. Estimation of Traffic Congestion
The estimation of traffic congestion is central to developing routing algorithms for a variety of metrics,
such as shortest time, shortest distance, and minimum fuel and emission costs. Pattara-tikom, et al. [47]
propose a congestion prediction technique based on the cell dueling time (CDT) of the mobile phones
of users.
Their study suggests that CDT duration can be used to estimate the degree of congestion with an accuracy level
up to 85%. Chen, et al. [19] propose a congestion modeling technique based on GPS based vehicle
tracking.
Average velocities of road links are calculated and distributed to related links. By integrating all
the
velocity contributions on each road link, traffic states are determined along rolling time periods.
Furtlehner, et al. [23] show how the idea of belief propagation, a concept developed
for intelligent systems - can be applied to traffic prediction using probe vehicles equipped with
GPS devices [21]. Zhang, et al. [59] present a design of a wireless mesh network for efficient
and
scalable communication with probe vehicles. Kuriyama, et al. [39] propose a method for finding non-congested
routes by sharing route information among users and a schedule to alleviate congestion at specific places.
A mathematical model of the probe vehicle sample size is given in [21], and it has been validated in [54].
Proposed Research Plan
We have identified the following topics which have direct relevance to the proposed vehicle routing system.
Objective 1: Congestion modeling and prediction:
Occurrence of congestion is a dynamic phenomenon.
In the COMPASS system, drivers are merely warned of occurrences of congestions via overhead CMS (Changeable
Message System) display boards. It is important to have two capabilities: first, model congestion by considering
the past and present pattern of traffic; second, develop a technique to predict congestion in the short-term,
up to one hour. A lead time in congestion prediction will allow us to take actions to diffuse the intensity of
congestion. For example, techniques such as early warning for all drivers and traffic flow balancing hold much
potential in diffusing the intensity of congestion.
Methodology:
For modeling and predicting congestion, we will have a system to collect data about
individual vehicles, such as location, speed, and destination. Such data can be easily collected by
replacing the current
induction-loop" technique with an IP (Internet Protocol)
message-based technique utilizing wireless communication. We will develop algorithms for forecasting
congestion, similar to short-term weather forecasting and financial forecasting. Soft and evolutionary
computing techniques, such as fuzzy logic, genetic algorithms, and neural networks, will be applied to
develop efficient heuristics. We have completed literature review to know the state-of-art in congestion
detection. We will focus on low-cost, accurate modeling of congestion based on historical traffic and current
traffic. The capabilities of vehicular ad hoc networks (VANETS) will be utilized in gathering data in a cost-effective manner for this purpose.
Objective 2: Soft Infrastructure for ITS Applications [53]:
We will develop communication
architecture, protocols, and algorithms for urban vehicle flow control to optimize the following
performance metrics: travel time, travel distance, congestion, fuel consumption, GHG emissions
and quality of travel experience (QOTE). Effective vehicle routing is key
to the success of an ITS system, because drivers and the transportation ministries are interested in
sustaining the free-flow of vehicles. The above stated performance metrics naturally follow from the
free-flow requirement. Traffic congestion occurs during peak hours due to a large number of vehicles
being on the road, and at any time if there are road-related incidents. Incidents tend to reduce the
available capacity of certain road segments, thereby causing resource bottlenecks. It is important to
identify and process real-time parameters of road networks to generate a balanced flow, and disseminate the
information to control points and drivers.
Methodology:
A road network is
often modeled as a dynamic network (i.e., graph), where a node models a road
intersection and a directed edge
represents a road segment. The
cost" of an edge will be modeled by a vector of
time varying metrics, namely, length, travel time, fuel cost of travel, and emission cost.
Travel time will be modeled as a function of a new parameter called
degree of congestion," whereas fuel and
emission costs will be modeled as functions of instantaneous speeds and accelerations [48].
The degree of congestion will be modeled as functions of instantaneous speeds and accelerations - this will be
new in our work. The progress made in computing city distances in this project will form the basis to develop
shortest-time routes in a dynamic network.