ORMS Today
August 2000

On the Road to Service

Fueled by an array of technological advances, vehicle routing software heads off in a new direction aimed at meeting growing customer demands

By Janice G. Partyka and Randolph W. Hall


Joseph Park, CEO and co-founder of Kozmo.com, is known to pitch in for his company, delivering videos, snacks and meals on his bike. Whizzing through New York one day on the way to a customer, Park was struck by a car and carried off by paramedics. Don't worry; Park survived the accident. Just as important for Park, the delivery was made on time. Before being taken away, Park called his dispatcher to ensure that someone else made the delivery at the promised hour.

Webvan, HomeGrocer and other Internet companies tell similar stories of commitment to customer service, and the pressure of meeting ever-narrowing time windows. But how are the routing software companies keeping up with the challenge? In the three years since our first vehicle routing survey appeared in OR/MS Today ["On the Road to Efficiency," June 1997], we've seen big changes in the industry, not just in the companies offering software, but also in their customers and in the technologies of routing and scheduling.

Like so many areas of operations research, computing and communication have had their impact. The meteoric rise of companies like Qualcomm, Nokia, Cisco, Netscape and Sun has been paralleled by innovations in routing software delivery and integration into business systems, as well as how fleets serve their customers. Supply chain software is also having an effect, as routing software becomes one element of systems that links material and product movements from source to customer.

To create our most recent survey, we've examined questionnaires returned by 18 software companies, as well as interviewed industry leaders. We've also talked to managers for the newest kinds of fleets — Internet-based home delivery — to see how routing software is used in their business. And to find out how the software really works for the consumer, we gave two delivery companies a try: HomeGrocer.com and Kozmo.com.

Routing Fundamentals


Like all OR "problems," vehicle routing is defined by decisions, objectives and constraints. Fundamentally, the decisions of vehicle routing are to assign a group of customers to groups of drivers and vehicles, and to sequence and schedule their visits. The objective of vehicle routing is to provide a high level of customer service while keeping the operating and investment costs as low as possible. And the constraints are to complete the routes with available resources and within the time limits imposed by driver workshifts, driving speeds and customer commitments.

In our consulting experience, the challenge for vehicle routing companies comes in translating these fundamentals into products that meet the needs of individual fleets, while avoiding unnecessary complexity. It is fairly rare for a company to fit the mold of the classic "vehicle routing problem," where all routes begin from a single depot, visit a set of stops, and return at the end of the day. Instead, each fleet faces its own set of circumstances.

The diversity of fleet characteristics and applications shown in Tables 1 and 2 is illustrative. It's not easy to make a piece of software that can do an equally good job of optimizing routes for transporting prisoners, picking up animals on the roadside and delivering groceries to people's homes. Add to this the needs for system integration with onboard and hand-held computers, order-picking and order-taking and supply-chain software, and each software purchase can become a customized installation.

Table 1: Route Characteristics

Mixed Pickup and Delivery: At a minimum, mixing pickups and deliveries complicates capacity calculations. But if the fleet is providing a point-to-point routing service, the entire formulation is altered, possibly requiring a totally separate piece of software.

Randomness: Service fleets in particular (such as appliance repair, utility repair, etc.) encounter considerable uncertainty in how long it takes to serve a stop. This makes it difficult or impossible to plan an entire route in advance.

Driver Specializations: Special skills, such as the ability to repair particular kinds of equipment or drive certain classes of trucks, must be reflected in worker assignments. Driver seniority, commission arrangements and equity considerations can also play a role.

Dynamics: Many fleets are moving away from batch processing and toward real-time service, where visits are scheduled immediately, even when vehicles are already working their routes.

Time Windows: Good customer service comes from scheduling stops when customers want them and meeting the time commitment within a narrow window. However, short of inserting enormous idle time in the schedule and driving far out of the way, perfection in this regard is impossible. Therefore, fleets need tools that can trade service against cost.

Multiple Facilities: When operating from multiple depots, warehouses or plants, the company may need to shift work from location to location, based on work loads or inventory availability.

Table 2: Vehicle Routing Applications

  • Beverage delivery to bars and restaurants
  • Currency delivery and scheduling at ATM machines
  • Dynamic sourcing and transport of fuels
  • Grease pickup from restaurants
  • Home appliance repair, service and delivery
  • Internet-based home grocery delivery
  • Milk pickup and inventory management
  • Pickup of charitable donations from homes
  • Portable toilet delivery, pickup and service
  • Prisoner transportation between jails and courthouses
  • Retrieval of dead and diseased animals from roadsides
  • Snow plow and snow removal routing
  • Transport of urine samples from medical offices to laboratories
  • Transportation of disabled individuals with vans and taxis
  • Trash pickup and trans-shipments
  • Wholesale distribution from warehouses to retailers
  • Postal delivery truck routing

Technology Trends


In the old days, dispatchers could only talk to drivers through CB radios, and then only when they were within range. Otherwise, contact was limited to occasions when drivers would line up for their turn at a pay phone. The choices today are enormous and growing. Depending on fleet needs, one might find a combination of analog and digital cellular phones, alphanumeric pagers, mobile data terminals, hand-held scanners and personal digital assistants (along with the occasional drivers who still depend on the pay phone). Some vehicles are also equipped with global-positioning-system (GPS) receivers, which compute the latitude and longitude of vehicles in real-time. GPS, combined with a map database (such as those offered by Etak, GDT or Navigation Technologies) and wireless data communication, enables the dispatcher to track vehicle locations and assign work to the driver who is best positioned to serve it, either with the assistance of routing software or through personal judgement.

Like all areas of computing, the Internet is also impacting vehicle routing. Most importantly, it provides a simple platform for sharing information from site to site, or even among dispatchers at a single site. The Internet also allows customers to view information on their shipments, as well as to automatically enter orders. These capabilities have led to the emergence of e-commerce as an industry for delivering products, ranging from groceries to meals to major appliances, directly from warehouse to consumer, bypassing the usual retail channels.

Looking to the next few years, we believe the most exciting development will be wireless Internet. Though the industry is still embryonic, the opportunity is clear. Individuals carrying small hand-held devices will be able to access an enormous array of information targeted to the mobile user. Through a portable and flexible platform, drivers will not only be able to interface with their company's routing system, but also access traffic and weather information, exchange messages with customers, update inventory records and request assistance when needed.

Software Trends


New entries and changes in ownership have altered the competitive landscape of the routing industry. ESRI, the well-known developer of ArcView and ArcInfo GIS, entered the market in 1999 with its ArcLogistics Route product. ILOG, owner of the popular CPLEX mathematical programming software, introduced ILOG Dispatcher in 1998. Supply chain companies have also established a stronger presence, through Baan's acquisition of CAPS Logistics and Descartes' purchase of Lightstone and ROADSHOW, thus adding competition to Manugistics' prior position as a supply chain provider of routing software.

In talking with some of the industry leaders, the dominant trends have been: better customer service, shorter time windows, multiple user networks, greater customer sophistication, real-time routing and technology integration.

As Len Kennedy, chief operating officer of Roadnet, puts it, "The focus of the industry used to be plan today for tomorrow's delivery. Now customers want to know what's going on after the trucks have left the terminal, where is my delivery and when is it going to be there. Now we are looking for real-time execution and a higher level of customer service."

Michael Jakab, vice president for Business Development at Descartes, concurs: "Distributors/wholesalers and, in general, transportation providers are finding themselves more and more of a commodity and are being driven by tougher service-level agreements that include ever-tightening time windows for acceptable deliveries, Internet track and trace, and visibility to information, including proof of delivery."

David Lichtenstein, also of Descartes, adds that a stand-alone PC-based routing package will not happily co-exist in the architectural requirements of a modern delivery system.

The Internet is becoming an effective tool for merging systems and raising the visibility of routing information. According to Michael Hane, Caps Logistics' product manager at Baan, "Currently one or two people are making decisions, but more people will be involved with greater visibility to the rest of the company. The future is thin client servers. With an Internet connection and Web browser, customers can access the routing program and their data on a remote server. You won't see the problem split among 50 dispatchers. They will all be working together."

Beyond serving the needs of the end customer with high quality routes, routing software must also be designed for ease-of-use by dispatchers. Mike Hooban, president of Microanalytics, sees "getting the data right" as the initial hurdle, including calibration of the road network and getting customer addresses geo-coded on digital maps. Unfortunately, geo-coding addresses is not as simple as vendors and fleets would like because map databases are not always up to date, complete and accurate.

Routing software companies are also well aware that their customer base is quite different from that of other types of OR software. Unlike the advanced degrees of the engineers and scientists who are the mainstay of companies like ESRI and ILOG, the typical dispatcher ended his or her education with a high school diploma. However, Don Weigel, ESRI product manager, notes that "We are seeing an overall higher caliber of professional managers attracted to today's logistic teams. But the big growth in our user community comes from traditional managers and operators who spend the time both to learn and to use the software."

Delivery by Internet


Fleets can be classified in many ways, such as whether they are in the transportation or service business, whether they transport people or shipments, whether they operate on a for-hire basis or as a private fleet, and so on. Web-based electronic commerce has created new segments. Though most of these companies are similar to Amazon.com or eToys, in that they don't operate their own fleet (these instead rely on UPS, FedEx, U.S. Postal Service and other small-package companies), a few are creating home delivery services.

The Internet has created three classes of home delivery: substitute, next day and same day. Substitute service offers Internet order-entry for pre-existing delivery services. For instance, pizza parlors and restaurants now provide Internet ordering as an alternative to traditional phone-in, with little change in their method of delivery. Next day service is driven by grocery delivery. Webvan, Peapod, Streamline and HomeGrocer (recently purchased by Webvan) fall in this class. These companies offer a long list of SKUs (stock-keeping-units), warehouses equipped with order-picking systems, and truck routes that are planned to meet customer selected time windows.

Same day companies include Kozmo, Sameday and Urbanfetch. The appeal here is immediate gratification: place an order for a couple items that you need right away, and you'll have your delivery in as little as one hour. These companies use a variety of delivery methods and have been somewhat urban oriented.

HomeGrocer routes its trucks from 100,000 square-foot warehouses within a radius of 30 to 40 miles. Warehouse managers download customer orders and transmit them to pickers, who wear RF (radio-frequency) scanners to retrieve items from their 15,000 to 17,000 SKUs. Bar-code systems are used throughout the process to track orders as they are placed on trucks and delivered to customers. Mike Smith, director of distribution at HomeGrocer, has been happy with their commercial routing software, but notes the challenges in getting routing companies to move at Internet speed: "The routing companies are used to working with traditional companies that are not tremendously technology oriented like the dot.coms. If HomeGrocer wants an important change in the software, we often do it ourselves because it is quicker, and we have the technology know-how."

Two years ago, Webvan started their search for a commercial routing software vendor who would help them create real-time "incremental routes" (adjusted as orders are placed) that can hit hour time windows. Chris Kantarjiev, Webvan technology staff, found that "Routing companies weren't ready to work on that kind of solution. Only two vendors showed interest, and we had to customize a commercial package to meet our needs. To make our windows, we take a hit on efficiency and occasionally spend more time driving than delivering. But it's the nature of the customer play."

Kozmo began in New York City as a delivery service for impulse buys and rentals, such as videotapes and meals. Instead of driving trucks, delivery workers started out on bikes and scooters, as well as walking and occasional subway rides. According to Scott Evans, vice president of Logistics, "We went shopping for routing software last August and decided the offerings were unworkable. They are built for a different type of operation and the algorithms take too long to optimize." Kozmo attempts to form routes within 5 minutes, while accounting for such variables as size and weight of orders (20 pounds is the limit for a bike), terrain, mode of delivery and product type. Kozmo decided to create their own in-house system, finding it wasn't as time consuming and expensive as one might think.

We put Homegrocer to the test on July 4. It takes a while getting used to the ordering process, but it is also fun trying out some of the more unusual items (the purchase included Hinoichi Yam Cakes, Zatarain Jambalaya Rice Mix and Breadshop's Juice Sweetened Granola). At checkout, the 3 p.m.-4:30 p.m. window was selected from several delivery options available for the following afternoon. Sure enough, the driver pulled up about 4 p.m. the next day and was even kind enough to carry in the bags of groceries (after donning special slippers to protect the floor). He brought along an accurate manifest listing every item in the order, billing information and various terms and conditions. (For those old enough to enjoy the attention, you can count on being carded for any alcohol purchase.) The professional appearance of the driver and truck, and attention to detail, were impressive.

A week later, we made a short lunch order to Kozmo: a sandwich, a couple of chocolate protein bars and a Frappuccino®. The order arrived just 35 minutes later, well within the 60 minutes allotted. The convenience of immediate delivery, combined with the freshness of their product (the Kozmo sandwich was a hands-down winner), was a definite plus, but Kozmo is clearly in a different market than HomeGrocer. To meet its time commitment, Kozmo must work within smaller territories and offer a shorter list of SKUs. Instead of refrigerated trucks, Kozmo drivers travel in personal vehicles, and the service seems geared toward immediacy and flexibility.

Survey Results


Our survey this year covered similar ground as 1997, including questions on functionality, system requirements, features, pricing, GIS capabilities, product integration and customers (survey results begin on page 32 of the print edition). Recognizing that it would be impossible to set a common standard, we did not ask about computation speed or other performance measures. We also did not explore the actual algorithms, which are typically proprietary heuristics (often blended with optimization for sub-problems). But this time around we added questions on algorithmic capability, such as whether the program is capable of assigning stops to terminals.

All 18 vendors who responded to the survey offer Windows NT products, and many also have products available for Windows 2000. Some are also available on Web and Unix platforms. A high-end PC is generally all that is required for hardware, along with a large amount of hard disk space (up to 10 gigabytes). For a mid-sized fleet of 50 trucks, expect to pay anywhere from about $8,000 to $60,000, supplemented by installation support costs at the rate of $75 to $150 per hour.

Basic features (found in most software packages) include an ability to accept customer time windows, display routes and stops on maps, geocode stops from addresses, generate turn-by-turn driver instructions, assign drivers to routes and edit routes with "drag-and-drop." Most vendors claim a variety of algorithmic capabilities, including simultaneous assignment and sequencing of stops, solutions based on actual street distances and an ability to assign stops to terminals. Software is differentiated by their system integration features, such as integration with customer order processing, supply chain management, real-time vehicle tracking and bar-code scanning.

Only a few vendors report installations at more than 500 companies, with ESRI, Roadnet, Trapeze and Truckstops leading the pack (TransCAD is also in this range, but provides a more general product than routing, and GeoRoute 5 reports 2,000 sites, with a focus on postal routing). It should be noted that a few of the vendors, including Trapeze, specialize in bus routing and have therefore developed products that are customized for a market other than trucking. Otherwise, private truck fleets are the dominant customer, constituting up to 100 percent of vendors' customer bases.

When picking a vendor, the best advice is to look for experience working in your particular industry, willingness to support any needed system integration, and a proven ability to solve problems of desired size with necessary speed. Because processing speed and data preparation can vary from application to application, it is a good idea to try the software on test data sets. Also look for products that can be coupled with map databases that support accurate geocoding for the routed area.



Janice Partyka is president of JGP & Associates of La Canada, Calif., a marketing and technology consulting firm specializing in transportation and communication.

Randolph Hall is professor of Industrial and Systems Engineering and director of the METRANS Center at the University of Southern California. Research for this article was supported in part by a grant from the National Science Foundation (DMI-9732878).


Be sure to read the accompanying Vehicle Routing Software Survey.





  • Table of Contents

  • OR/MS Today Home Page


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


    Lionheart Publishing, Inc.
    506 Roswell Street, 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 1999, 2000 by Lionheart Publishing, Inc. All rights reserved.