June 1997 • Volume 24 • Number 3

On the Road to Efficiency

The classic traveling salesman problem is a walk in the park compared to the vehicle routing problem. From route capacities to randomness, vehicle routing software developers must contend with myriad technical potholes that the TSP doesn't even consider. A survey of the industry unearths a field ripe for OR/MS applications.

By Randolph W. Hall & Janice G. Partyka

Anyone who's studied networks, combinatorial optimization or integer programming has undoubtedly seen the "traveling salesman problem" (often simply called the TSP). That's the classic problem in which a mythical traveler must find a minimum length cycle through a set of nodes in a completely connected graph. The traveling salesman problem is at the root of computational complexity theory (being one of those exponentially bounded problems). But more important to industry, it is at the root of a burgeoning field of OR/MS application: vehicle routing.

The computer scientist would call the TSP a "hard" problem. But to dispatchers faced with the real problem of routing large fleets, the TSP is positively trivial. Fleet managers must contend with a great many factors that the TSP does not begin to account for, including:

Route Capacities. Each cycle is constrained by the available space in a vehicle, which might be measured in "cube" (cubic volume, to the layman), weight, pieces or floor space (if items are not stackable). A cycle is also constrained by the time in a driver's day, which itself depends on safety regulations, company workrules, and whether the driver has already handled other loads.
Time Windows. Ever schedule a delivery at your home and been offered two choices: "a.m." or "p.m."? To remain competitive, companies today must be much more responsive to their customers' needs and deliver shipments exactly when customers want them. These requirements are expressed as time windows, either as rigid lower and upper bounds, or as soft time windows, which can be violated, with penalty.
Dynamic Routing. The dispatcher doesn't always have the luxury of planning out the stops in advance, as in the TSP. Sometimes, the stops aren't known until the vehicles are in the field, part way into their routes, forcing them to double-back or circulate to finish their tour. On top of this, travel times and costs are time dependent, as vehicles battle the "rush-hours" on the road, or the "rush- hours" at loading docks.
Randomness. On top of all the constraints, nothing is certain. A load that is supposed to have five pieces turns out to have 20, and suddenly there's not enough space to finish the route. Or perhaps a driver is held up for paperwork and doesn't have time to visit the rest of her stops and get back in time to connect with the next flight out.

The companies engaged in the business of developing routing software are keenly aware of these real constraints, and are developing user-friendly packages employing a blend of heuristic and optimization algorithms to assist dispatchers in routing their fleets. Their goal is to create more efficient routes, meaning fewer miles, fewer labor hours and fewer vehicles, not to mention getting stops served on time. Just as important, their goal is to be a part of an integrated system that manages the movement of goods from source to destination, tracks the productivity and quality of drivers and generates information for planning purposes, all in a "paperless" environment.

Industry Overview
In the OR/MS literature, the "vehicle routing problem" (VRP) refers to a capacitated version of the TSP. A fleet of vehicles is available at a single terminal to serve a set of stops. A shipment size is associated with each stop, and a cost is associated with each ordered pair of stops. The objective is to deliver the shipments to all stops at minimum cost in a set of cycles without violating vehicle capacity. If only the world were this simple.

Vehicle routing can be divided into three basic segments: service vehicles, passenger vehicles and freight vehicles. Service vehicles do not move things or people from place to place. They are used to support jobs in the field — vans for the copier repair technician, plows for snow removal or trucks fixing pot holes, to take three examples. Service routes are not constrained by shipment sizes and vehicle capacity, because there are no shipments. Hence, the route lengths are only constrained by the time in the driver's day or shift.

Passenger fleets, on the other hand, are called "carriers," in that they carry something from one place to another. Buses and vans carry people, so the length of their routes are constrained by the number of seats, or possibly by a combination of standing and sitting room. Freight vehicles are also carriers and are also capacity limited. They can include ships, trucks, rail or air, but commercial software is clearly targeted at the trucking segment. Moreover, most commercial software is targeted to one aspect of the freight industry: local pick-up and delivery.

When a shipment or passenger is carried from one place to another, it may be transported through a network of terminals connected by various kinds of routes. Take the less-than-truckload (LTL) industry, for example. These trucking companies specialize in shipments that are too large for the package companies (UPS and the like), and too small for "truckload" (TL) carriers, which transport trailers direct from origin to destination.

LTL shipments are typically handled in at least two, and possibly up to four or five, terminals. First, the shipment is retrieved from the origin and taken to a local "end-of-line" terminal. Next, it may be "shuttled" to a regional consolidation center, where it is combined with shipments originating throughout a metropolitan area (or larger). Next comes a "longhaul" route to another consolidation center, near the destination. From there it is shuttled to an end-of-line near the destination, and finally on a delivery route to the destination.

Each segment of the LTL shipment's journey demands a different kind of route and a different kind of routing software. Local pickup is a dynamic problem, requiring flexibility to serve shipments as they are called in. Shuttle routing requires careful driver scheduling, to ensure that workshifts are fully utilized. Linehaul routing requires balancing inter-regional flows to minimize empty equipment miles and to minimize driver and fleet downtime. Only the final segment of the trip — the delivery route —closely matches the VRP formulation.

Breaking the VRP into its Pieces
Solving the VRP, or its variants, amounts to solving four inter-dependent problems. Step one is to calculate the distances between pairs of stops. One way to do this is by approximation. Determine the coordinates of each stop, and calculate the distance "as the crow flies" — or at least as the crow would fly if it could really fly in a straight line. But of course a truck can't drive straight from point to point, so the distance must be adjusted upward by about 15 percent to approximate actual road mileage.

The other way to calculate the distance is through a geographic-information-system (GIS). In a GIS, distances between points are derived from shortest path algorithms applied to very large networks, rather than by simple algebraic calculations. The GIS operates on a map database — a computerized version of your fold-up-map that substitutes arcs and nodes on a CD ROM for printed street segments.

GIS are more exact than approximations (especially when stops are separated by bodies of water or mountains), but not without flaws, especially for trucks. The underlying maps have been painstakingly created through years of human effort translating U.S. Geological Survey and other paper maps into electronic form. Errors can crop up, and sometimes only the experienced truck driver knows that a fast car route is impossible for a semi-tractor negotiating sharp turns. Nevertheless, GIS are an invaluable source of point-to-point distance and time data, especially for shorter length trips where geographical features are more constraining. And GIS are fast enough to be practical.

Step two is answering the "who-does-what" question. The who is a vehicle route, and the what is a set of stops. Conceptually, this amounts to optimally partitioning a service region into districts, where each district represents a feasible collection of stops for a single route. In practice, these districts can overlap in unpredictable ways, especially when time windows are involved or when requests for pick-ups arrive dynamically throughout the day.

The third step is the most familiar. Once a set of stops is assigned to a route, optimizing its cost amounts to solving a traveling salesman problem. But again, time windows and dynamic stop requests complicate matters, resulting in cycles that are not shortest, but instead optimally balance the need to serve customers when they want against the cost of covering the route.

The process concludes with crew assignment (that is, assigning specific drivers to routes). Crew assignment becomes a mathematical problem, instead of just a personnel problem, when routes are shorter than (or longer than) individual work shifts. Shorter routes must be pieced together to form driver tours. Longer tours must be partitioned into shifts, with accommodations made for driver exchange along the way.

These four steps reasonably describe local pickup and delivery routing in the trucking industry. Longhaul truck routing is much more focused on crew assignment issues, along with balancing inter-regional freight flows. The problem is much more akin to Koopman's classic "Transportation Problem" than to the VRP, where the goal is to balance the flow of equipment and drivers in and out of terminals while minimizing empty mileage. This must be solved within the context of routes that can take up to several days to complete, requiring driver or equipment exchanges, or possibly sleeper/driver teams that operate nearly continuously.

Another variation crops up in routing snow plows, meter readers and other vehicles that must visit every point along a block face. Though routes can be created by routing vehicles through nodes on a network, it is more efficient to route vehicles through arcs. This becomes the capacitated version of the "Chinese Postman Problem," the problem of creating a minimum length cycle that covers each arc in a network at least once.

Taxi routing, courier routing and "dial-a-ride" routing also differ from the formula, due to their highly dynamic nature, and due to "loads" that are transported one at a time or at most in small groups. Human judgment plays an even stronger role in such environments, making routing software more of a decision aid than a pure optimizer. Differences also abound among modes of transport. Aircraft routes, for instance, are planned far in advance on rigid schedules. Train routes must account for the pairing of locomotive equipment with railcars. And ship routing must be carefully planned to exploit favorable ocean currents and to avoid hazardous weather systems.

All told, optimal vehicle routing doesn't follow a single "one-size-fits-all" formula. Routing software must usually be customized to reflect the operating environment, customer needs and the characteristics of the transportation mode.

Technology On the Rise
What truly makes automated routing practical today is technology. Prior to GIS, it was easier for the experienced dispatcher to beat the system. Without high-speed personal computers and work stations, it was hard to tackle realistic problems with time windows. And without new on-board equipment, it was difficult to execute automated routing.

Trucking fleets now have several choices for communicating with drivers and relaying routing instructions. The first option is the on-board trip recorder, offered by such companies as Cadec, TripMaster and Xata. These devices both record vehicle speeds and engine vital signs and record driver information to create hours-of-service logs. They can also display route instructions to drivers and upload actual route lengths at the end of the day to compare software estimates against actuals. What's more, some of these products now include Global-Positioning-System (GPS) receivers, so that the state of the vehicle can be correlated with its exact location throughout the day. A GPS equipped system can determine not only how long a driver was on break but where the driver was on break (so drivers better watch out).

Longhaul carriers and other companies that engage in both pickup and delivery have gone one step further through installation of on-board tracking and communication equipment. Qualcomm, HighwayMaster, AMSC and other companies offer systems that continuously display the location of all the vehicles in a fleet back at a base station. A GPS receiver is placed on each vehicle, allowing it to determine its latitude and longitude within 100 feet. The coordinates are then transmitted up to a satellite (or perhaps through a cellular or pager network), back to the tracking company's base station, and then by landline to the trucking company. The communication system can also be used to relay instructions to drivers while they are in the field. Tracking services offer the potential for optimal real-time routing, though as our survey shows, few software companies have come out with products that capture this information.

A last important technology area is the in-vehicle navigation device. Sold by such companies as Alpine, BMW, Oldsmobile and Toyota, and costing about $2,000, navigation devices provide turn-by-turn instructions to destinations through use of GPS receivers, map databases and shortest path algorithms. Some even use voice synthesizers and voice recognition systems, providing a back-seat driver who actually knows where he's going. Navigation devices are most useful for drivers who are unfamiliar with their destinations, which is perhaps why they have not made major in-roads in the trucking industry. Nevertheless, a dependable navigation system could become attractive to fleets, who would no longer be constrained to sending drivers into familiar territory, but instead have greater flexibility to reassign drivers on a day-to-day (or minute-by-minute) basis.

No one yet has come out with a product that integrates routing optimization, navigation and fleet tracking. But with rapidly dropping hardware costs, this is not far off on the horizon. Also not far off are software systems that integrate routing functions with inventory tracking, and perhaps even production scheduling. The end result will be totally integrated logistics software that manage the flow of goods from source to customer.

Survey Results
Our survey was designed to identify the capabilities and market niches of software products, as reported by the software vendors. The survey covered both computational aspects (platform, algorithms, etc.) and integration aspects (interfaces with tracking systems, recorders, GIS, etc.). We also asked the vendors about their most important customers and their target industries, along with special product features. Surveys were faxed to 23 companies, of which 16 responded.

When it comes to computer platforms, the trend can be stated in two words: Microsoft Windows. All but one vendor offers Windows versions of their software, frequently both Windows 95 and Windows NT. Other available operating systems include DOS, UNIX, IBM's OS2 and A/X. As for Mac users, you're out of luck — none of the survey respondents serve your platform.

Products were divided between those that placed no bounds on problem size and those that limited problems to no more than 1,000 to 4,000 stops (sufficient for most practical problems). However, our survey did not allow for comparison of computation times or memory requirements, just hard limits, so beware.

Most vendors had several common features: an interface with one or more GIS (ArcInfo and GDT being most common), the ability to perform node routing and accept rigid time windows, and a graphical user interface that allows the user to alter routes and estimate changes in route length or cost (described as a "drag-and-drop" interface by Shipcons II, RIMMS and Route Pro). Some products could perform both node and arc routing, and one more specialized product (RouteSmart Neighborhood) was only capable of arc routing. Many could accept both hard and soft time windows.

Other common product features included assignment of drivers to routes and ability to generate turn-by-turn route instructions. Less common was the ability to generate load manifests. With respect to system interfaces, most companies had some experience with order-entry systems and trip-recorders. Others are capable of interfacing, though the vendor may not have any actual experience doing so.

More unique features were offered by several vendors. Roadnet 5000 can model rush hours. OVERS allows multiple time periods, and can also be used to position terminals. Shipcon has a shipment rating capability. And Taylor II has several unusual features, including design of experiments and advanced statistics modules along with 3-D animation.

Vendors were close-lipped about embedded algorithms. Those that did reveal their methods cited general-purpose integer programming methods, such as branch-and-bound, set partitioning, lagrangean relaxation and clustering heuristics. One product (Tesys) uses fuzzy logic. Unfortunately, based on vendor responses, no product seems capable of modeling randomness beyond "what-if" type analysis. And its unclear from responses whether any product is well suited for real-time routing, where vehicle routes must be altered and updated when they're in the field. Though many stated that their product is intended for real-time routing, most indicated that the product could not in fact update routes when vehicles are in the field, and most did not have experience interfacing with real-time tracking systems (two exceptions are OVERS and Tesys).

The vendors' "significant installations" tells the story of who's buying vehicle routing systems. The list looks like a who's who for the food and beverage industry — Anheiser Busch, Coca Cola, Frito Lay and Nabisco, to name a few. Clearly, the bread-and-butter business has been here, along with other private carriers, principally for local deliveries. However, the biggest single customer seems to be Canada Post with 15,000 routes, served by GIRO Enterprise's GeoRoute 5.

How to Pick a Vendor
Picking a software package is a little like selecting kitchen cabinets. Even though many parts are pre-built, making them fit exactly right requires customization. The right choice depends on the product's flexibility to meet your particular needs, along with your confidence in the vendor to provide the personal support that will be needed to make it work.

With so many products available, it is worth shopping around, and being especially sure that the product will work in your environment. In this regard, it is important to look for a vendor that has experience with similar installations. And it is always important to make sure you are comfortable with the user interface and the programs time-window features, along with the run-time, memory requirements and cost.

Faculty should bear in mind that none of the products is specifically intended for academic purposes. However, TransCAD is most likely to meet educational needs, offering a variety of optimization methods, low price (discounted price of $995) and turnkey operation. For a full industrial installation, expect to pay $40,000 and up, though TruckStops can be bought for significantly less (starting at $6,000 without installation support).

Overall, the vehicle routing software industry has made tremendous strides in recent years, due to quicker processors, GIS and Windows interfaces. Expect to see more improvements soon, especially in the area of interfaces with other programs and tracking systems, and in real-time routing.

Randolph W. Hall is an associate professor of Industrial and Systems Engineering at the University of Southern California. Janice G. Partyka is president of JGP and Associates of La Canada, Calif., a technology consulting firm for the trucking industry.
For more information, put the number 6 in the appropriate space on the
Reader Service Form

E-mail to the Editorial Department of OR/MS Today: orms@lionhrtpub.com

Lionheart Publishing, Inc.
2555 Cumberland Parkway, Suite 299, Atlanta, GA 30339 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com