 |
|
|
by Max Stevens-Guille
Excerpted from Transportation Technology Today, July 2001
Transportation costs typically constitute more than half of the total logistics spend in today's business environment. This share has been on a steady increase, as smaller, more frequent and more on time shipments are required. Demand has come from a number of different fronts including increased variability in consumer demand, a quest for TQM (total quality management), lower inventory levels in the supply chain and increased competition. All transportation companies, from TL to local delivery, have to continually improve their processes to deal with these additional costs.
Decreasing transportation costs can be achieved through better utilization of resources such as people and vehicles. Recently, a number of technologies have converged, resulting in new services that aim to utilize vehicles more efficiently. The goal of these new systems is to enable transportation companies to meet their customer time commitments while deploying their fleet through the road network in the most efficient manner.
Convergence
The advent of affordable GPS, low-cost wireless communications, better models of the road network and more powerful algorithms have converged to provide a new generation of vehicle scheduling systems. While the products coming to the market vary in their capabilities, they are all built around the road network. This article provides a brief overview of the issues involved in creating the infrastructure to support services built on top of the road network.
Transportation Routing
The transportation market is broad, though it can, for routing purposes, be segmented into a number of different markets. The long distance Truckload carrier market is looking for door-to-door routes, integrated, optimal point-of-interest searching (to reduce out-of-route miles while visiting weigh scales, rest stops, fuelling networks, etc.) and information about traffic conditions along their route. LTL carriers are looking for the optimal sequence to visit multiple destinations and frequently change their route as new opportunities arise. Local delivery companies and service companies tend not to travel far, but have very dynamic schedules as customer orders change, tasks take longer than anticipated, and traffic impedes their progress. The chart below highlights the difference between the three segments.
While each market has a different set of requirements, each is trying to deploy their fleet while optimizing one of three interdependent variables: Time, Space, Cost. While interdependent, one variable must be chosen as dominant. Solving for fastest time may involve traveling on different classes of road, perhaps even toll roads that involve additional cost. Solving for shortest distance (the space variable) may involve traveling on slower secondary roads that may take longer to traverse than faster, but longer, primary roads. Solving for minimal operational cost may result in missing customer commitments. Because there is no 'right answer', routing systems need to accept guidance as to the types of tolerable compromises in every given situation.
Basic Structure
At the core of any system that offers services built around the road network is - not surprisingly - a database of the road network. Depending on how much of the world is modeled, it can be an immense amount of data. There are, after all, more than 26 million kilometers of road network in the world according to Peter Johnson, a Professor of Engineering at the University of Sydney. In the United States alone, there are more than 40 million road segments and over 8 million uniquely named streets. Using advanced algorithms one can model the road network as a very large mathematical graph. The nodes of the graph are street intersections, the edges are road segments.
The road network itself is very useful, but it is even more compelling when additional information is associated with it. Postal and regional boundary information can be used to find locations using partial information. Real-time traffic and weather enables drivers to avoid problem areas. Information about points of interest such as depots, fueling networks, truck stops and the like can be used with proximity searching services to find the nearest location along the route.
Most routing systems provide a common set of foundation services. Address matching services can take street names and return the coordinates-and conversely a set of coordinates and return the associated street address. Given a coordinate there are services to render maps. Using two or more coordinates one can calculate the optimal way to route through the street network. Finally, from a route, one can create a set of directions.
Street Network Data
High quality data is required for a routing system to be effective. In order to calculate a route, the street network must be properly connected. Not so long ago, it was common to find street data from which maps could be generated, but the roads were not properly attributed or connected thereby rendering them incapable of supporting a routing system. Sourcing a routeable street network is still a challenge in areas outside of North America.
A routeable street network maintains many attributes for each street segment including the road name, the class of road, the address ranges on the road, weight and hazardous material restrictions, lane widths, lane restrictions, bridge heights, tunnels, time-based turn restrictions, toll roads etc. Given the huge challenge of acquiring all these attributes, multiple data sources are required to provide adequate coverage. Stitching together data sets from different sources is a significant challenge as datasets frequently vary in their formats, projection, naming conventions and accuracy.
Addresses - Defining where you want to go
All routing systems provide some form of 'geocoding' or addresses matching. Given addressing information such as a street name, an intersection, a city, a region, a country, or a postal code, a geocoder can determine not only the coordinates of the address, but also the street segment that it's on. Some geocoders can even return which side of the street and roughly where on the segment it is located. To perform this feat, a large amount of data is required. Obviously, information about the road network and its coordinates is required. In addition, regional data is required to define neighborhoods, cities, municipal boundaries etc. Postal information can help determine an address when only partial information is available.
The goal of any geocoding system is to provide the best answer given the information provided, and at hand. In this way, a geocoding engine behaves very much like a text-search engine. Consider an imprecise query: perhaps a dispatcher types in an ambiguous address such as 205 Queen, Toronto, Ontario. A good geocoder will prompt them whether they meant 205 Queen St West, East or 205 Queens Quay. A query for 199 Queen Street on the other hand, should only return 199 Queen Street East, as there is no 199 Queen Street West or 199 Queens Quay in the city. Clearly, the more intelligent your geocoder the better, as the penalties involved in delivering to the wrong address can be significant.
Routing Services
There are many routing systems on the market. Some work against a small subset of the data to provide fast city-to-city routing through the highway network. Of the systems that provide door-to-door routing, two primary approaches are used. Hybrid systems use a model of the local road network to route from the origin to the nearest point in a second routing layer that contains the highway network. The routing system then performs a fast city-to-city route dropping back to the local road network layer to route to the destination when it finds the destination city. The quality of the resulting route depends in large part on how many linkages there are between the local road layer and the highway layer.
Systems without enough linkages may result in routes that take a driver out of their way while routing them to the highway network. Pure door-to-door systems use a single routing layer and aggressive algorithms that seek to find the fastest class of road as quickly as possible, finding the optimal way to the destination. These single layer systems will always generate more optimal routes than hybrid systems.
In calculating a route, the routing algorithm searches the entire space looking for the path between two points that has the lowest impedance or cost. The routing engine needs to take into account the type of vehicle, the cargo (including weight and HazMat restrictions), the degrees of business freedom allowed (such as whether toll roads can be used), and the start time of the journey. The routing engine then biases the costs of each segment in the network so that, depending on the business goals, certain types of roads are not taken while others are. For instance, a road that has a tight turn may be difficult to navigate while pulling a 53' trailer. A higher cost can be associated with a left-hand turn onto this segment, resulting in the routing system selecting a route that approaches the road from another direction. As another example, metropolitan roads frequently have time-based turn restrictions. Respecting such restrictions requires an accurate understanding of when a vehicle will depart on its journey.
Data quality plays a significant role in providing accurate and effective routes. Poorly constructed data often suffers from digitizing errors and topological problems, such as roads that are represented as intersecting when they shouldn't. This is frequently a problem when roads run under one another and elevation isn't modeled. Given this incorrect data, a routing algorithm will naively suggest that it is valid to turn off from one road on to the other, unaware that such a move might result in 20' drop!
Sophisticated routing systems are able to calculate the optimal way to visit a number of destinations. While certain types of tasks do not have any temporal constraints applied to them, most do. Customers have restrictions on when their loading docks are open. Items aren't always ready to be picked up at the beginning of a day. Calculating the optimal sequence to visit customers given these temporal constraints is a significant challenge. Calculating them quickly has, until recently, been impossible. The advent of new algorithms and fast computers has enabled the creation of a new generation of routing engines that can calculate, in seconds, the optimal way to visit multiple locations while minimizing distance or time. These systems are fast enough to support the demands of the courier, pickup and delivery, and service markets. The ability to dynamically assign new jobs as they come in and reassign tasks on the fly while minimizing distance traveled allows transportation companies to rethink how they manage their resources.
In some ways, routing systems can be viewed as simply a system for calculating cost factors for a job assignment system. Consider a situation where there are more jobs than can be performed by a single driver. A job assignment can use cost estimates from the underlying routing system to assign the jobs to multiple drivers, while optimizing for cost, time or distance. The latest routing solutions provide both routing and job assignment, allowing trucking companies to link their solutions seamlessly.
Real-time Traffic
There are a number of different approaches to modeling traffic conditions in the network. Historical traffic information is available for various cities, from which a model of the road's speed over the course of the day can be constructed. When integrated into the road network, historical information enables routing systems to provide a better time estimates. Real-time traffic information, on the other hand, associates a time-limited incident with a specific road segment, supporting everything from scheduled road closures to temporary lane closures and traffic accidents.
Historically, traffic reporters relied on civilians, police reports, traffic helicopters and, more recently, traffic cameras, for information. Increasingly, operators of major road systems are equipping their road beds with sensors to monitor the instantaneous flow of traffic. A number of Eastern States have begun implementing this through an outsourced arrangement with Traffic.com, in partnership with the U.S. Federal Department of Transportation.
Modeling real-time traffic is a significant challenge. First and foremost is the sheer volume of information involved. A gigabyte of data is an immense amount. A gigahertz processor - about the best available today - takes a second just to read from the first byte to the billionth. Updating the many gigabytes of data in a global road network with real-time information is obviously not a straight-forward process. And this is just the beginning of the challenges involved in modeling a real-time road network. Responding intelligently to a traffic blockage is another challenge entirely. By dynamically modifying the attributes of the road network, the routing system can calculate routes that avoid incidents.
Routing doesn't always result in a set of directions. Frequently, the goal is to calculate a time estimate. Given the current location of a vehicle, how long will it take to reach its destination? Using the location captured through the network and the route costing services, trucking companies are able to answer such questions as 'when will the service person arrive?' Historical traffic information can tell us how the road network is impeded at various times of the day. Determining a time estimate for a 1000 mile trip that may skirt major cities must take into account the vehicle's start time so as to apply the correct traffic information to the estimation.
Directions Services
From a route, a set of directions can be generated. The type of directions provided is determined by the type of route that is calculated. Directions are most useful when they are easy to follow. One of the most straight-forward ways to make a set of directions easy to follow is to minimize the number of decisions that a driver must make. Intelligent algorithms now exist that search for the "near optimal" route that has easier directions to follow. Direction formatting depends on the medium in which it is displayed. Directions that are deployed in a vehicle's MDT may be more terse than those displayed on a computer terminal or printed on paper. Directions can also incorporate information that may affect vehicle progress such as traffic, weather, and events.
Conclusion
As wireless data and GPS technology costs continue to drop, more and more vehicles will be equipped with in-cab, location-aware, data terminals. The challenge facing the transportation system today is pulling together all the elements of a successful routing system that fulfills the requirements of both the management and drivers on the road. High quality information about the road network, real-time traffic, transportation quality routing, and support for new devices are now being brought to market that are capable of dynamically deploying a fleet to maximize customer satisfaction while minimizing operating costs.
Author
Max Stevens-Guille is a co-founder and SVP of Marketing of Maptuit Corporation, an eGeo Services ASP, focusing on the transportation market. Max has an MSc in Computer Science and over 12 years of experience in various segments of the technology industry.
|
|
|
|
