OR/MS Today - February 2002|
Vehicle Routing Software Survey
Change of Direction
Following the death of Internet-based home delivery companies, vehicle routing software exploits new technologies to reach traditional industries
By Randolph W. Hall
In the two years since the last OR/MS Today survey of vehicle routing software, we've seen quite a few changes in the industry. For instance, Internet-based home delivery has died in the market. However, Internet-based routing applications have grown, with focus on traditional industries, such as wholesale food distribution and home delivery of appliances and, increasingly, less-than-truckload for-hire carriage. Routing software is exploiting a plethora of new technologies, ranging from wireless data communication to genetic algorithms to client-server computer architectures. And routing vendors are weathering the economic downturn with a strong focus on delivering a quick return-on-investment to their customers.
Tools for Software Developers
The OR/MS community should especially welcome one change in the industry. ESRI and ILOG have made libraries of routing code available to software developers. Thus, it is now possible to customize products to particular applications through software licensing arrangements.
ILOG Dispatcher is a C++ library built on top of the ILOG Solver constraint-programming platform. Solver has been enhanced by representing constraints that are common in vehicle routing problems (e.g., time windows) and by incorporating search techniques that are effective in routing. A form of guided local search is utilized, incorporating penalty functions that move solutions away from local optima and toward better solutions. "Academic benchmarks are fairly easy to solve to good results," says Bruno De Backer, senior project manager for Dispatcher. "The problems given by industry are much harder. They have constraints at each node, and conditions that you face may push you toward a different solution methodology." According to De Backer, traditional routing heuristics are not effective in solving these difficult problems.
ILOG's philosophy is to make programming objects easily accessible to developers, so that they can write their own constraints and add in their own local search methods. The process is similar in concept to how ILOG's CPLEX is built into large-scale linear programs. The developer creates front-end and back-end models, and Dispatcher is used as the solver.
In the case of ESRI, a routing object is available within the NetEngine product that provides a family of network-based algorithms. NetEngine's library can be imbedded in software through either a C application program interface (API) or Visual Basic via a type library. ESRI separately sells MapObjects for creating GIS interfaces. "These libraries have given developers like Motorolla the flexibility to merge GIS and vehicle routing in customized products," says Ernie Ott of ESRI.
Routing software continues to grow in features and capabilities, in response to new technologies and customer needs. Mike Jakab, senior vice president at Descartes, sees growth in three areas: wireless communication/vehicle tracking, integrated order processing/routing systems and Web-based applications.
"The Web is helping us serve fleets that operate out of many locations," Jakab says. "Routes can be created from an Internet browser connected to an application server. The advantages include reduced software installation and maintenance costs and better data management."
In the wireless arena, Descartes has developed "Mobile Link Freight" and "Mobile Link Tracker" software to capture real-time data from the field. For instance, a driver can transfer data from a pocket PC device as deliveries are made, and the routing system can re-plan as needed, sending messages back to the driver. Real-time updates are also important in "FleetWise Reservations," which lets the order-taker schedule time windows based on the set of orders already planned. When an order is near to another, they can be married together, so that they are served at the same time of day, saving vehicle miles.
Chris Russell, president of GeoCom USA, sees the need for scalable software solutions that do not depend on loading all routing software and maps on each individual workstation. "With a traditional solution, every time you upgrade you need to upgrade each client," Russell says. "GeoCom's client-server architecture provides scalability and easier maintenance to serve larger companies that employ many dispatchers, each of whom may serve multiple locations." GeoCom's solution follows the Microsoft ".NET" architecture. It entails loading a plug-in on each client that interacts with server-based applications, such as mapping and sequencing.
GeoCom is utilizing genetic algorithms for generating routes. "We want to come up with a solution that works the first time," Russell states. "Our algorithm doesn't get trapped by the seed, so the dispatcher spends less time correcting solutions." And, like Descartes, GeoCom has come out with a real-time application for companies in the pickup-and-delivery industry, which enables routes to be re-sequenced as data come in.
At UPS Logistics, Len Kennedy has seen a trend toward distributors wanting to share more information, such as load status, with their customers. "We are making Mobilecast available on a Web site for customer service," he says. "Then you can tell people exactly when orders can be made." Kennedy also sees a demand for integrating routing systems with hand-held scanners and other data management tools for improved information management.
Like information technology in general, the routing industry has been affected by economic trends. In this environment, companies increasingly want to see a quick return on investment. According to Len Kennedy, "companies need to see reductions in hard costs, such as reducing drivers in the fleet or expediting manual processes."
According to Chris Russell, "people are a lot tighter with their wallet and projects have been put on hold." However, there has been a bright side for the routing industry. "In routing, it is easier to demonstrate a fast ROI than with other IT projects," Russell claims. Russell also notes that "people are going after point solutions [like routing], rather than for expensive suites of software." He maintains that under the ".NET" architecture, routing products are more easily integrated, so companies do not have to invest in expensive enterprise software systems.
Routing software is also expanding into new market segments. Pierre Trudeau, director of Optimization Product Marketing at ILOG, states: "We are seeing growth in the field service area in particular, as the economy has become more service oriented."
This Year's Survey
Twenty-four software vendors participated in this year's vehicle routing software survey. The questionnaire was divided into sections covering background information, algorithmic capabilities, interfaces and features, and applications. All responses are self-reported and unverified.
Algorithmic Capabilities: All products have the basic capability to sequence stops on a route, and almost all have the capability to assign stops to routes and to terminals. Most vendors claim that assignment and sequencing are simultaneous, and not sequential, and most claim that these decisions are based on actual street distances. However, some approximation of street distances can be advantageous, as it greatly reduces the computational effort in distance calculations and speeds up creation of routes.
The algorithms underlying routing products are generally proprietary. However, basic capabilities can be discerned, such as maximum allowed problem sizes (measured in stops, vehicles and terminals). Though some vendors claim unlimited problem size, computation time, memory size and disk space bound product performance, so it is important to test software on some actual problems.
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. 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. Most vendors claim they are able to do both. Most vendors also claim they can route in real time (i.e., while vehicles are in motion), as well as on a daily basis (a more common application). About half of the products are designed for planning future routes.
Interfaces and Features: As a starting point, all products can display routes and stops on maps, and most allow the user to edit these routes with the "drag-and-drop" feature (i.e., click on a stop, and move it to whichever route you desire). This feature 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 and GDT, as well as the low-cost Tiger maps, available from the U.S. government. These maps are usually sold separately, and are chosen by customers according to their requirements with regard to accuracy, pricing and coverage. Particularly for companies that operate in many regions, it is wise to select a product that can work with more than one map product.
Interfaces with software systems order-entry and inventory management are important for retailers and distributors. The less-expensive products tend to work better as stand-alone products; those designed for integration with business systems cost more. Some routing products can also be integrated with tracking and wireless communication systems, to enable real-time routing another factor affecting cost.
Applications: Whereas a few vendors provide generic products designed to serve a broad range of applications, most have specialized 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. Vendors that are more experienced in your industry will be better prepared to consult on software installation.
For example, companies like Trapeze, RouteLogic (Compass) and VersaTrans serve the transit industry, UPS Logistics serves the beverage and food distribution industry, and CAPS Logistics has been strong in distributing manufactured products. On the other hand, MicroAnalytics (TruckSTOPS) and ESRI (Arc Logistics Route) have gone after a broader market with a more generic and lower-priced product. And ILOG has established a unique position, providing a library of solvers rather than a family of interfaces.
General Information: The 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: (1) How big of a problem will be solved, measured in vehicles, stops and terminals? (2) How frequently will the solution be updated, and how quickly must the software generate a solution? (3) Who will use the software, how is the information best presented to the user, and are the users distributed among many locations? (4) Who will install and maintain the software, and (5) 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. If your interest is in solution code, and not in the interfaces, ILOG and ESRI are the places to start.
View the Vehicle Routing Software Survey
Randolph Hall (firstname.lastname@example.org) is Associate Dean for Research in the School of Engineering, and Chairman of Industrial and Systems Engineering, at University of Southern California.
OR/MS Today copyright © 2002 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
Web Site © Copyright 2002 by Lionheart Publishing, Inc. All rights reserved.