Today, mapping has moved to the center of the Internet explosion. Mapquest, Google Earth and a plethora of specialized tools, ranging from real estate appraisal to restaurant look-ups, have made geographic-focused sites favorite places for any Internet user's browser. Computerized point-to-point routing is so commonplace that "mapquest" has entered the lexicon as a verb to describe how we find our way to destinations.

Perhaps the biggest sign of the emergence of digital mapping was last year's bidding wars for NAVTEQ and TeleAtlas, the two largest companies in the industry. Cell phone giant Nokia acquired NAVTEQ in October for $8.1 billion, and was soon followed by TomTom's (the global positioning system device company) acquisition of TeleAtlas for $4.2 billion.

It should be no surprise then that digital maps have migrated to mobile phones, personal digital assistants (PDAs) and other portable devices. Spurred on by regulations requiring mobile carriers to provide geo-coordinates of 911 callers, mobile phones have become the platform for location-based-services, vehicle routing being no exception. While still an emerging technology, one can imagine one day that the mobile phone will not only help a driver navigate along streets, but also on foot through office complexes right to the loading dock or desk of the recipient. Mobile devices can also be used to record pick-ups and deliveries, tracking the preferences of individual customers, and to re-route drivers when needed.

Mobility


Most of the respondents in our survey have experience integrating their software with mobile phones, PDAs or other portable devices. As summed up by Jane Geary at Paragon, wireless connections enable fleets to "link routing optimization with satellite navigation and proof of delivery."

UPS Logistics Technologies developed "MobileCast" for communicating route critical information to and from mobile phones. MobileCast was released in the late 1990s and was initially exclusively based on hand-held devices such as Symbol (now Motorola) and Intermec devices. At present, mobile phones outnumber hand-helds by a six-to-one margin because of their much lower cost. While hand-helds are still needed for signature capture, Cyndi Brandt at UPS Logistics Technologies states that in the future "the Windows mobile environment will provide much more memory and processing speed and open the door on a new generation of phone-based routing." For instance, they are working on embedding Garmin or TeleAtlas to support navigation. Brandt goes on to state that the "problem today with navigation is that since the application doesn't reside on the phone, when you lose coverage the navigation closes down, and then you have to bring it back up and that takes time."

We spoke with a MobileCast customer, Pat Mullally at Landauer Metropolitan, a distributor of durable medical equipment and respiratory products and services to 70,000 patients annually. Landauer utilizes 60 drivers, performing around 1,100 deliveries a day in the northeastern United States. These drivers carry a Motorola i355 GPS cell phone from Sprint-Nextel. The phone is ruggedized and has a proprietary Java application (from UPS Logistics Technologies) as an interface.

"Before the system was implemented, drivers were given a random stack of 25 to 35 delivery tickets and had to spend precious time trying to manually figure out how to best sort and deliver them," Mullally says. The dispatch office did not know where the drivers were once they left the building for the day. Customers spent many minutes on hold while the customer service representative attempted to contact the dispatch office (who then had to contact the driver) to find out a delivery status. Today, he says their drivers are able to get on the road as soon as the truck is loaded, and late deliveries have been virtually eliminated. The dispatch office knows where the drivers are located. Customers have to spend less time on the phone waiting for a delivery status.

The phone uses GPS technology to track the driver's location. Once the driver logs into the application, the phone is programmed to ping every three minutes or every mile traveled. The MobileCast server (provided by UPS Logistics Technologies) is a database and communication server hosted at Landauer Metropolitan. This server sends and receives messages from the phones throughout the day and stores the information in the database.

Mullally appreciates the flexibility of using a mobile phone instead of a device that is tethered to the vehicle, or the old way of using printed instructions. For instance, "If a truck breaks down and is not available, another vehicle can be used without requiring a new installation," he says. The device can also be carried with the driver to the actual stop and used for voice communication.

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 somewhat according to their target market, special features and integration capabilities, as discussed in the following section, but even here we saw greater convergence than in prior surveys.

V.R. Software Trends


Although routing software has reached a high level of maturity, customer requirements constantly change. Jane Geary of Paragon Routing notes that fleets are looking more at the carbon footprint of their operations, striving to be more "green." In a recent study for a United Kingdom brewery, "Paragon identified savings of more than 2.5 million miles a year as a result of more efficient routing and depot allocation — representing a saving in the region of 3,700 tons of CO2 per year."

Saitech, a routing software provider, has developed a special feature to estimate carbon emissions within its software. According to Saitech's Yoshiro Ikura, "The formula is based on a few parameters, such as the capacity of the truck, the loading factor, the fuel type and the estimated mileage of the vehicle." Ikura goes on to state, "This feature has been developed mainly due to some requests from our customers in Japan. The Japanese government recently mandated ... companies to reduce the CO2 emission by 1 percent a year for next several years to meet the Kyoto protocol."

On a more technical level, Vincent Mayer of DNA Evolutions has promoted the development of Web-based service platforms for routing software. He notes that their JOpt.ASP has been "designed for enterprise applications and web based solutions"; these are based on ASP.NET. Other recent innovations include continuous background optimization at Descartes, continuous performance enhancement at MJC2 Limited and Internet order tracking at Prophesy.

This Year's Survey


Sixteen 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. Windows remains the dominant platform for routing software and is available for nearly all software packages. While no vendor in the survey offers a Mac version of their software, there is an increasing trend toward Web-enabled platform independent applications. Networked software, connecting multiple users through the Internet or local networks, is enabled by ASP (Active Server Page) and J2EE (Jave2 Enterprise Edition) technologies at several vendors.

From a hardware perspective, vendors generally recommend a high-end PC operating in the 2-4 GHz range, combined with 1 to 4 Gb in memory and up to 60 Gb in hard disk space. These figures have not changed much in the last two years, perhaps reflecting that powerful routing software is becoming easier to run on one's desktop.

Algorithmic capabilities. The algorithms underlying routing products are generally proprietary, though typically involve a combination of integer programming methods and heuristics. DNA Evolutions was more specific, reporting use of genetic algorithms while Spatial Decision Support reports use of simulated annealing. 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 one- 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. Ortec reports use of truncation and search space bounding as a method for approximating solutions, and DNA Evolutions permits the user to set convergence criteria. Other vendors state that approximations are not used (which is unlikely to be a good solution strategy), or that their 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 most 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, and it important to select a vendor that has experience in the planned application.

Most vendors claim the ability to solve routing problems with soft time windows. However, when asked for specifics, some simply indicate that they represent a range of time or maximum allowed delay, rather than a true soft window approach. On the other hand, ILOG permits cost functions to be set, Appian provides a buffer plus a penalty, and DNA Evolutions evaluates deviations through use of fuzzy logic.

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 NAVTEQ (based in the United States) and TeleAtlas (based in Europe). Maps, which are not inexpensive, are often sold separately and are chosen by customers according to their requirements.

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.

In our survey, most of the respondents have specialized in private truck fleets, serving such markets as food and beverage (e.g., Safeway, Anheuser Busch and Dunkin Donuts), and consumer products (e.g., Home Depot, Walgreens and Office Depot). One exception is Pupil Transit Manager from Spatial Decision Support Systems, which concentrates on routing for school buses.

Routing installations tend to require a large degree of customization, as reflected in software prices, which often runs in the tens of thousands of dollars. As an alternative, TruckStops from MicroAnalytics is a more generic and lower priced product (below $10,000), which can be attractive for smaller fleets. In terms of pure size, UPS Logistics Technologies, MicroAnalytics and Prophesy are the market leaders with more than 1,000 installations each, but several other large players now have more than 500 installations. It should also be noted that vehicle routing is truly an international market. The base of operations for nearly half of the 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 like: 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. However, ILOG and DNA Evolutions both offer vehicle routing solvers that can be imbedded in other programs. In this manner, these products might be used in research, in fleet applications and as a component of other software products.

The 2008 Vehicle Routing Software Survey

Editor's Note: OR/MS Today will survey forecasting software in the June 2008 issue. Vendors wishing to participate should send an e-mail with the name of the company, product and contact information by March 24 to: horner@lionhrtpub.com. Matthew Saltzman, a professor of Math Sciences at Clemson University, has been named the new software review editor for OR/MS Today. Companies wishing to have their software reviewed and independent individuals interested in reviewing software should contact Saltzman directly at: software-reviews@mail.informs.org.

Janice Partyka is vice president for External Relations at TechnoCom Corporation and specializes in the wireless industry. She is a frequent contributor to industry magazines.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2008 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 2008 by Lionheart Publishing, Inc. All rights reserved.