Vehicle routing is undoubtedly one of the most critical elements in managing the global supply chain, so it is no surprise that it has become one of the most important types of supply chain management software. Traditionally, routing software has played three roles: assignment of work (i.e., shipments) to drivers and terminals, sequencing stops on routes and scheduling stops. Sometimes routing software is also used to provide driving directions, though drivers are usually expected to have the knowledge to find their way between stops (some lucky drivers also have navigation computers on-board to keep them from getting lost).

More broadly, routing software is used to manage the flow of resources as they are transported on road vehicles. Routing software supports customer service by ensuring that shipments are delivered on time and, when they are not, determining their whereabouts. Routing software reduces the cost of operating fleets. Software can also be used to add capacity by increasing the productivity of drivers and vehicles, allowing carriers to serve more customers. In a quite separate domain, routing software is also important in supporting the service economy through dispatch and routing of field service works (e.g., repair persons, meter readers, sales force), as well as in routing public transit vehicles.

Integration


Integration has become a code word for progress in vehicle routing. Customers need solutions that combine customer ordering, inventory control and product delivery. They also need the ability to integrate routes and schedules among multiple sites.

According to Michael van Duijn of ORTEC, "Integrated solutions with modules for delivery forecasting, [dynamic] sourcing, dock and load planning will become more important over time. The world is becoming more dynamic and your route planning, dispatch and tracking technology need to support this changing environment in order to stay ahead of the competition."

Integration is also important at ILOG, which has adopted a modular strategy. "In addition to ILOG Dispatcher, ILOG also provides visualization components such as ILOG JViews Maps, and ILOG JViews Gantt, that can be used to create a complete application. ILOG also has connectors to ERP packages like SAP and Oracle," says ILOG's Chris Hane.

At UPS Logistics, Cyndi Brandt sees "movement to larger enterprise systems to facilitate centralized/regionalized routing. Centralization is allowing companies to aggregate data and monitor the overall effectiveness and efficiency in transportation." To a great degree, this capability is being provided through Web-based systems that enable sharing of information and algorithms among multiple sites.

Another trend is toward a combined approach of long-term route planning and day-to-day or even minute-to-minute routing. According to Jane Geary of Paragon Routing Systems, "We will be concentrating on helping customers to integrate the planning and execution phases of the transportation operation more tightly. As distribution operations become more complex, it becomes ever more important to retain planning intelligence in the execution phase so that operational efficiency can be maintained as changes arise."

Cell Phones


James Stevenson of Appian Logistics is not alone is stating that "affordable GPS real-time tracking and reporting" is the number one change in the industry. We are beginning to see routing and scheduling transformed by the ability to track and communicate with drivers via inexpensive cell phones and personal digital assistants (PDAs).

Under Phase II of the Federal Communication Commission's Enhanced 911 rules, wireless carriers are required to relay caller locations to Public Service Answering Points (PSAPs, locations that receive emergency calls and dispatch police and fire) to within 50 to 300 meters. Locations are determined from embedded Global Positioning System (GPS) chips in cell phones, sometimes augmented by triangulation among cell phone towers. While designed for safety applications, the same location technology enables a range of location-based services, including vehicle routing. Add to this improved graphical displays on phones and PDAs, and it is easy to see why hand-held routing applications will explode.

UPS Logistics has offered GPS mobile phone applications since 2002. "We currently have over 15,000 phone devices deployed in the field," says Brandt. "This has been a highly successful extension of our MobileCast product because of the significantly lower cost of a phone over a rugged handheld."

Brandt finds the trend toward more cell phone applications to be strong: "As phone technology progresses, we are also able to continue to introduce more functionality on the phone," she says. "In 2002 it was a simple pick-up and delivery application. Today, it is a sophisticated application that allows far more than just arrivals and departures."

Hane has noticed a similar pattern. "We have found that the new lower price point of GPS cell phones and PDAs is raising awareness of routing costs, especially in field service organizations," he says. "The customers of tracking services are naturally expanding the market for route optimization."

van Duijn has also seen the need for real-time interaction. "A couple of years ago, route planning and tracking/tracing were more or less separate domains," he notes. "Slowly companies began integrating real-time communication into their dispatch environment to compare planned versus actual. In today's environment, real-time optimization and re-optimization of routes is possible, leveraging wireless technology to communicate schedule changes to and from drivers or field workers using PDAs."

Basic Software Features


The routing software surveyed in this article provide a common set of basic capabilities:

• geocoding addresses, i.e., locating the latitude and longitude by matching the address against data contained in a digital map database;
  
  
• determining the best paths through street networks between pairs of geocoded points;
  
  
• solving vehicle routing problems, entailing an assignment of stops to routes and terminals, sequencing stops and routing vehicles between pairs of stops; and
  
  
• displaying the results in both graphical and tabular forms in such a way that dispatchers can guide the solution process and communicate results to drivers, loaders and other personnel.

Applications differ according to their target market, special features and integration capabilities, as discussed in the following section.

This Year's Survey


A total of 17 software vendors participated in this year's routing software survey. Our questionnaire was divided into sections covering platform, algorithmic capabilities, interfaces and features, applications, system integration and background information. All responses are self-reported and unverified.

Platform. All products surveyed operate in the Windows environment, and about a third also operate in Linux and UNIX. Growth has occurred in the availability of Web-based routing solutions, often implemented through Active Server Pages (ASP), now available from about half of the vendors. This is especially valuable when multiple locations share information, such as in multi-terminal operations. Apple remains a niche market — only two vendors report Mac versions of their software.

From a hardware perspective, vendors generally recommend a high-end PC operating in the 2-3 GHz range, combined with 1 to 2 Gb in memory and up to 100 Gb in hard disk space. All of these figures have doubled in the last two years, reflecting the increased availability, and reduced cost, of high-end personal computers.

Algorithmic capabilities. The algorithms underlying routing products are generally proprietary, though typically involve a combination of integer programming methods and heuristics. GEOCOMtms and Carmen Systems were more specific, reporting use of genetic algorithms and column generation methods, respectively. Vendors generally claim unlimited problem size for their software, but from a practical perspective, computation time, memory size and disk space bound product performance, so it is important to test software on actual problems. In this regard, most vendors claim computation times in the two- to 10-minute range for an average-sized problem, described as the time to solve a problem with 50 routes, 1,000 stops and two-hour hard-time windows. (Keep in mind that computation times are provided by the vendors and have not been verified.) These times are similar to two years ago, despite increases in processor speed.

Fast computation times are particularly important in real-time applications, such as when deliveries are scheduled while the customer is on the phone, or when stops are inserted and scheduled while vehicles are in the field. Researchers in vehicle routing are well aware that route-length approximations can be very effective at producing good solutions in a short amount of time. Unfortunately, vendors indicate that they do not utilize approximations and that approximations are proprietary.

Node routing is the capability to assign and sequence discrete stops, and arc routing is the capability to assign and sequence street segments. The former is needed more often and occurs when the driver visits 100 or fewer locations per day. We believe it is available on all products. Arc routing is more specialized and occurs when vehicles visit every (or most) address on block segments, as in meter reading, mail delivery and garbage pickup. A bit more than half of the vendors now claim they can do both of these, along with real-time routing, daily routing and route planning. However, it should be borne in mind that a single routing package is unlikely to be adept at all of these functions.

Most vendors claim the ability to solve routing problems with soft-time windows, but only ILOG and Appian clearly identify a soft-time window approach based on time penalties. Other vendors appear to approach the problem by enlarging the size of a hard-time window beyond normal.

Interfaces and features. As a starting point, basic features offered by most include an ability to display routes and stops on maps and edit these routes with the "drag-and-drop" feature (i.e., click on a stop, and move it to whichever route you desire). This enables the dispatcher to modify the algorithm-produced routes and is needed in practice to satisfy customer constraints. To make these features work, products need digital maps, such as the commercial products from Navigation Technologies, TeleAtlas and GDT, as well as the low-cost Tiger maps, available from the U.S. government. Maps, which are not inexpensive, are often sold separately and are chosen by customers according to their requirements, with regard to accuracy, pricing and coverage.

Integration interfaces with software systems — order-entry and inventory management — have become particularly important for retailers and distributors. Less-expensive products tend to work better as stand-alone products; those designed for integration with business systems cost more. In larger firms in particular, routing is just one component of an end-to-end system. Interfaces with bar-code systems (used in inventory control), supply chain management and customer order processing systems are available in about half of the products and are particularly important for private carriers. Other important features include forecasts for delivery requirements, generation of load manifests and load planning.

Applications. Whereas vendors generally claim that their products are designed to serve a broad range of applications, most specialize in an industry sector. Specialization is largely driven by interface requirements, both in terms of presenting information in a manner that is useful to the target user, and in terms of interfacing with business software systems and hardware devices. Police, taxi and emergency vehicle dispatch, for instance, each demand special requirements that differ from the traditional market of private fleets. They fall in the realm of niche markets, even though in theory they are just variations of vehicle routing.

Vendors that are more experienced in an industry will be better prepared to consult on software installation, and more likely to have relevant features, leading to a higher likelihood of success. The optimization code might also be different to account for the particular network structure, for instance the hub-and-spoke design of LTL networks.

Edgar and VersaTrans, for example, have specialized in bus routing — Route Match in para-transit routing and SAITech in less-than-truckload. The most common market, however, is private fleets for distribution of food, beverage and other commercial products, which is the focus of most vendors. MicroAnalytics (TruckSTOPS) and ESRI (ArcLogistics Route) have gone after a broader market with more generic and lower-priced products. And ILOG has provided a library of solvers that are sold both to end-users and to software developers. In terms of pure size, measured in number of customers, UPS Logistics and MicroAnalytics remain the market leaders with more than a thousand customers each. It should also be noted that vehicle routing is truly an international market. The base of operations for the majority of vendors in our survey is outside the United States, including several European countries and Canada.

General information. The accompanying directory provides contact information and product names for the vendors. Pricing is available for some vendors (in many cases, prices are negotiable and depend on fleet size). Expect to pay $10,000 or more for the software alone. Higher-priced products generally offer more customized service, a larger array of features and interface capabilities, and specialized experience in a particular industry. Price structures do vary, so be sure to compare the full installed cost before making a choice, including license fees, installation and maintenance costs, hardware and digital maps.

Selecting a Product


Before purchasing a product, fleet managers should first develop a set of requirements to answer questions such as: How big of a problem will be solved, measured in vehicles, stops and terminals? How frequently will the solution be updated, and how quickly must the software generate a solution? Who will use the software, how is the information best presented to the user, and are the users distributed among many locations? Who will install and maintain the software? What software systems must the routing system interact with? Vendors should demonstrate that they are experienced serving other fleets with similar requirements, and they should provide references so that you can verify claims.

The academic community should recognize that most products are designed for use by actual fleets and are not intended for research. ILOG is an exception. It provides solvers that can be integrated into other software, and therefore might be used in research, in fleet applications and as a component of other software products. ESRI's Network Analyst also provides general purpose features built on a GIS, providing a convenient software solution for many academic projects.

The 2006 Vehicle Routing Software Survey



Randolph Hall is vice provost for research advancement and a professor in the Epstein Department of Industrial and Systems Engineering at the University of Southern California.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2006 by the Institute for Operations Research and the Management Sciences. All rights reserved.


Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com


Web Site © Copyright 2006 by Lionheart Publishing, Inc. All rights reserved.