Vehicle Routing: On the road to innovation
Survey of vehicle routing software reveals fierce competition produces creative solutions.
By Janice Partyka (Left) and Randolph Hall
Routing software companies are competing fiercely to produce the most creative solutions. Just having the best routing algorithm doesn’t cut it. And offering GPS tracking isn’t enough either. “Customers want a more connected fleet,” says Cyndi Brandt of Roadnet. “We are seeing more dynamic, real-time routing, open systems, and partnerships to provide an even deeper level of analytics that serve the entire organization.”
Whether in the software or in the digital technology that supports routing, innovation is the driver. There has been a sharp uptake in mobile device usage in the vehicle. Customers are increasing using on-board computers and Android-based smartphones. Following consumer patterns, small- and medium-sized businesses want to have their data reside in the cloud to reduce computing and IT resources.
Innovative Problem Solving
Innovation begins by finding the right approach to solve real routing problems, which often differ from standard “out of the box” formulations. Successful software vendors offer services, as well as software, to ensure that routes are efficient for their intended application. “A creative routing solution can provide customers with both better service and cost savings,” says Chris Jones at Descartes.
Case 1: In Manhattan, buying groceries requires a lot of schlepping. Enter FreshDirect, a grocer that delivers to 10,000 people a day throughout the city, supported by Roadnet software. In dense areas of the city, FreshDirect trucks find a parking space early in the morning near their starting route target. Additional workers take subways to the parked trucks, and each worker delivers grocery orders on foot via the routes produced by the software. When the truck is empty, another full FreshDirect truck arrives and takes the same parking space and the deliveries continue.
Case 2: Working with Descartes, John Lewis (a large United Kingdom retailer) created a real-time delivery scheduling system to be used by customers at point of sale. When a customer places an order for a king-sized feather bed, she can choose from several delivery times. Some are free, but others carry a price. The free times are less popular slots, often in the middle of a workday, whereas the paid spots are the most sought-after times at the beginning and end of the day. John Lewis uses delivery-time pricing to balance the workload across the day, increasing route efficiency.
Case 3: The Fonterra Dairy is a large cooperative of 15,000 dairy farms in New Zealand. Bulk milk pickup is a complex operation handled by 500 trucks. The production from cows varies from day to day; truck container volume is limited, and because it is perishable, the milk must be picked up on schedule. With unknown quantities, deterministic routes cannot be created in advance, so MJC2 created a real-time routing system in which the vehicles are rerouted after every pickup.
Many call 2012 the year of the dragon, but in routing it is the year of the in-vehicle device. Regulations that require electronic logs for driver hours-of-service and gas tax have increased sales and lowered prices of on-board computers. These devices enable telematics that will provide management with visibility into the wait at customers’ loading docks, unsanctioned stops, speeding and delay that holds up the route.
On-board computers can connect to the vehicle engine. Companies get a record of the vehicle’s condition, need for maintenance and how it is driven. Idle time, the temperature of a reefer, when doors open and hard braking can all be measured. Getting drivers to eliminate engine idling is a challenge for fleet managers. Idling strains the engine and is prohibited in some locales. For instance, in New York City, vehicles that idle for more than three minutes face up to a $2,000 fine.
Smartphones are a cheap and easy alternative to on-board computers. “Phones work well because everyone knows how to use them,” says Hugh Gigante of TMW. “Fleets like them because they are easy to use, cheap and can utilize off-the-shelf apps that can be helpful.” Routing software makers are favoring Android operating systems. Smartphones are unable to provide information about a vehicle, but can be effective for tracking, navigation and limited data entry. Service fleets (e.g., engineers or health care workers) are more likely to use a smartphone. Pickup and delivery vehicles often rely on mobile handheld terminals that enable scanning and signature capture.
The mix of devices purchased by fleets is changing. One large routing provider saw 50 percent of new customers adopting smartphones, 25 percent on-board computers and 25 percent personal navigation devices. Another routing vendor reported 40 percent of new customers utilizing smartphones and 60 percent on board computers. Yet another company reported 15 percent of U.S. customers have onboard computers, but 80 percent of their proposals now incorporate in-vehicle on-board computers.
Mapping and Traffic
Routing companies generally use NAVTEQ and TomTom (previously called TeleAtlas) maps to calculate distances and travel times as well as to display routes. More detailed mapping data for trucks are available, including hazardous routes, width, weight and height restrictions. “Consumer demand for navigation has increased the availability of quality digital maps throughout the world in places like Eastern Europe,” says Will Salter of Paragon Software Systems. “This has enabled us to expand our reach further to even more countries.” Better traffic information is now available by road segments by time of day to establish historical traffic patterns.
Twelve software vendors (eight North American and four from Europe) participated in this year’s vehicle routing survey, representing 15 products. The 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 all software packages, with five offered in Linux and another four for Unix. Nine products are available in software as a service (SaaS). From a hardware perspective, there is range of requirements that depend greatly on the implementation. Vendors generally recommend a PC operating with one GHz up to three GHz, combined with up to four Gb of memory and two to 125 Gb on the hard disk. These figures have not changed much in the last four years, again showing that powerful routing software has become easier to run on one’s desktop computer. In SaaS applications, computing requirements are even smaller than in the past.
Algorithmic capabilities: The algorithms underlying routing products are generally proprietary, though they typically involve a combination of integer programming methods and heuristics (likely some form of localized search). DNA Evolutions utilizes genetic algorithms, and IBM indicated constraint programming.
Vendors generally claim unlimited problem size for their software, but from a practical perspective, processor speed, 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 at about five minutes 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.
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. Sometimes vendors can quickly update routes without going through a full execution of the routing algorithm.
Node routing is the capability to assign and sequence discrete stops, and arc routing is the capability to assign and sequence street segments. We believe it is available on all surveyed 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. Most of the vendors claim they can do both of these, along with real-time routing, daily routing and route planning. However, a single routing package is unlikely to be adept at all of these functions, and it is important to select a vendor that has experience in the intended application.
All vendors state that they have the ability to provide real-time re-routing of vehicles. Most vendors have the ability to incorporate real-time traffic and utilize historical traffic by road segments to better optimize routing. This can enable a fleet to reschedule in response to customer requirements, vehicle delays or traffic conditions.
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, IBM ILOG and Route Solutions permit early and late penalties, DNA Evolutions windows are “fuzzy by default,” and MJC2 and Optrak use “configurable rules.”
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, which are not inexpensive, and are often sold separately and are chosen by customers according to their requirements.
Integration: Real-time communication with drivers, as well as tracking their locations, has become particularly important, and most products offer these features. This usually is provided with vehicle-mounted on-board computers, smartphones, personal navigation devices or hand-help mobile units. Interfaces with other software systems – such as order-entry and inventory management – is also important for retailers and distributors. 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 less-than-truckload (LTL) networks.
In the survey, most of the respondents have specialized in private truck fleets, serving such markets as food and beverage (e.g., Kraft, Anheuser Busch, Coca Cola and Snapple). Route Solutions is being used by various state lotteries and Airport Bags, Inc. DNA Evolutions is routing the New York Department of Health.
Routing installations tend to require a large degree of customization, as reflected in software prices, which often run in the tens of thousands of dollars. As an alternative, SaaS requires little upfront cost. Beyond these software costs, some level of consulting is likely needed to ensure full integration into a fleet’s information systems, typically priced in the neighborhood of up to $100 to $250 per hour. In terms of pure size, many companies now claim more than 1,000 installations each.
General information: The online directory provides contact information and product names for the vendors in this year’s vehicle routing survey (see box). Pricing is available for some vendors (in many cases, prices are negotiable and depend on fleet size). For a 50-route single site license, expect to pay $20,000 to $40,000. ESRI was the only vendor to provide a monthly price for SaaS ($450). 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.
How to Buy
The most satisfied routing software customers know their goals before they purchase. “Be very clear about what you want to do and don’t be overwhelmed by technical jargon,” advises Julian Stephens of MJC2.
With your objectives as a framework, look for a routing company that knows your vertical market well, and one that can help you leverage the software for productivity gains throughout your organization. Look for experience with companies of your size with similar integration challenges. Consider how frequently routes must be generated and updated, and how much time is available to generate routes. Check references. Make sure the vendor has customer service available when you need it. If your routes are built between 7 p.m. and 9 p.m., make sure they will be answering calls during that time. The last step is to try it out. Some companies offer a free trial. Others will charge a customer for a trial that includes consulting services. The customer will pay for some of the trial and be obligated to make a purchase if all trial objectives are met. Some customers will ask three or four routing companies to compete for their business by giving them all the same routing problem to solve.
Janice Partyka (firstname.lastname@example.org) is principal of JGP Services (www.jgpservices.net), a marketing consulting practice that focuses on mobile technologies and applications. Randolph Hall (email@example.com), INFORMS member, is vice president for research and a professor in the Epstein Department of Industrial and Systems Engineering at the University of Southern California.
Survey Directory & Data
To view the directory of vehicle routing software products along with the survey data, click here.