Vehicle Routing Software: On The Road To Connectivity
Creative integration of computer, communication and location technologies help a wide range of industries thrive in difficult times.
By Janice Partyka (left) and Randolph Hall (right)
In the two years since our last survey of vehicle routing software, the world has suffered a financial collapse unlike any since the 1920s. Sinking home values, overseas wars, terrorism, threats of global warming and turmoil in health care have capped a decade that many would prefer to forget. As we look forward, the global financial disaster has taught us one thing: simply moving money from account to account does not produce prosperity. Instead, our well-being depends on building economic activities that deliver goods and services to real people, when and where they need them.
Routing software companies are offering creative ways to integrate computer, communication and location technologies with algorithms and software, helping a wide range of industries thrive in a period of recovery. These technologies enable routing software companies to provide sophisticated connectivity and productivity tools to an increasingly mobile workforce and widely distributed customers.
A decade ago, cell phones were for the rich, map databases were still being developed and GPS-enabled navigation was beyond the average consumer. Routing software worked well, but it wasn’t flexible and relied on an imperfect platform, making it difficult for the drivers to access information on the road, and sometimes creating a mismatch between the route that drivers were directed to follow and what they knew to be the best course.
According to Cyndi Brandt of UPS Logistics Technologies, “new data sources have recently become available, including a more complete commercial roads database, and true historical traffic data based on real travel times.” Chris Jones of Descartes Systems Group also notes an “explosion of map data attributes and capabilities.” In the next year or two, we will have predictive travel speeds for road segments down to 15-minute intervals. “Currently, drivers say the software doesn’t know everything that they know about the routes. It is sometimes true now, but won’t be that way in the future,” Jones says.
Likewise, we are now seeing stronger connectivity between routing software’s traditional functions — that of assigning stops to drivers and placing them in an optimal sequence — with on-the-road navigation. A computer-generated printout listing turn-by-turn directions is becoming moreofananachronismthesedays,when so many drivers can receive voice commands and dynamic map displays from their phones or navigation devices. As Jones notes, “Customers and prospects are really looking for combined solutions” that both route and navigate. “The big growth market is in the portable market,” he continues. “You see fleets that would have never gotten GPS technology now using it with a mobile phone.”
According to Julian Stephens of MJC2, “Smart phones are changing the industry in a big way because they allow real-time data capture, which in turn enables real-time re-optimization of the operation. This is of particular interest to us because our dynamic scheduling algorithms can make use of these data to increase operational efficiency of mobile workforces.” With this type of on-the-road connectivity, MJC2 and other routing software companies are investing in their real-time routing features and algorithms.
Route Solutions Inc., for instance, has integrated their routing solutions with portable TomTom devices. Estimated times of arrival are generated automatically, and dispatchers can remotely change stops, directly through the device, while drivers are in the field.
Software As A Service
AccoRdIng to Greg Wieitholter of Route Solutions, “Desktop-based routing is going away.” Instead, he says, “people want Web-based solutions, so all parts of the organization can have visibility.” This is now often accomplished through the Software as a Service (SaaS) model, whereby the software vendor generates solutions and manages data from their own servers. Alternatively, MJC2, for instance, has found that “many customers prefer to host the software themselves as this gives them more control and flexibility.”
SaaS is changing the financial model of some software companies. As Jones of Descartes notes, “SaaS is the way the industry has headed. It means that customers ‘pay as they go.’ It reduces the initial payment of the customer and removes a barrier to entry.” UPS has a SaaS offering aimed at smaller fleets, which treat the software costs like utility charges rather than an up-front capitalization.
For the software companies themselves, cash flows are changing from the initial large balloon payment and lower maintenance fees that come from purchase of licenses to more continuous income flows. For some, the switch is a difficult financial transition that requires cash reserves. However, many routing companies have found ongoing support financially challenging under the license model.
The Business Of Routing
Many of the routIng companIes predict that consolidation in the industry is likely to accelerate and that companies “run by mathematicians” will be unsuccessful. Customers are looking for stability and distribution system expertise more than the latest algorithms. Nevertheless, one of the challenges that all of these companies will face is the ability to process data to re-optimize routes in real-time. With map data getting richer and real-time traffic adding road segment data in small time intervals, the processing requirements will grow substantially. The underlying architecture of these offerings and how the processing is distributed will be a critical factor in how well each product fares.
Expansion Into New Industries
RoutIng software Is being used in an increasingly diverse set of industries, both in traditional truck pick-up and delivery as well as in mobile services, such as repair crews. Among Descarte’s customers, “Sleepy’s Mattress Stores” uses routing software to schedule deliveries on the spot at point-of-sale, within one-hour time windows. At Appian Logistics Software, it is being used to synchronize trucks and plumbers so that icemakers can be installed soon after a refrigerator is rolled in the door. Route Solutions’ customers are using routing software to schedule multitudes of merchandisers and installers, who travel among retail outlets to install product displays and signage.
One clear trend is that the companies that use routing software increasingly want to offer services that set them apart from their competition, and these services demand both faster solution times and improved communication — frequently generating new solutions on the spot. However, given the tough economy, cost remains an important driver. While desirable to route the same drivers to the same customers each and every day, that level of consistency can be inefficient. As Hugh Gigante of Appian notes, “If we tell a customer that it costs them $100 a day to keep the same drivers servicing the same customers, most fleets will decide it isn’t worth the cost.” Instead, routes can be continuously re-optimized so that every vehicle is used to its max. “Defining features now are anything that reduces windshield time, saves gas and decreases wear and tear on trucks,” concludes Gigante. And trucks need to be full.
Basic Software Features
The routing software surveyed 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.
This Year’s Survey
SIxteen software vendors (12 North American and four from Europe) participated in this year’s routing software survey, representing 22 products. 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, with only one company offering a Mac version of their software, and another three in Linux and Unix. Fourteen products are available in SaaS, two of which are only available in SaaS. From a hardware perspective, vendors generally recommend a high-end PC operating in the 3 GHz range, combined with 1 to 4 Gb of memory and up to 100 Gb in hard disk space (much less if SaaS is used). 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 typically involve a combination of integer programming methods and heuristics. QuantMethods and Jeppesen were more specific, respectively stating that linear programming/branch-and-bound and column generation were used. FreshStart Logistics, new to this year’s survey, indicated that their algorithms are based on artificial intelligence and expert system approaches, rather than traditional mathematical programming. DNA Evolutions’ response of “construction and improvement” is likely representative of the general class of heuristic methods used by most routing vendors.
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-tofive-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.
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. This year, vendors were tight lipped about use of approximations.
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. 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 planned application.
More than half of the products offer some capability for real-time routing, which could come in the form of real-time re-routing of vehicles or real-time stop scheduling. Six vendors (Appian, Descartes, FreshStart Logistics, MJC2, SAITECH and UPS Logistics) have the ability to incorporate real-time traffic, which is now more widely available in major cities. 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 permits early and late penalties, DNA Evolution windows are “fuzzy by default” and MJC2 uses “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, such as the commercial products from NAVTEQ (based in the United States) and Tele Atlas (based in Europe). Maps, which are not inexpensive, 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 devices or mobile phones. Interfaces with other software systems — such as order-entry and inventory management — is also important for retailers and distributors. We saw less emphasis on this feature in this year’s survey than in the past, though many (Descartes, FreshStart Logistics, IBM ILOG, MJC2, Prophesy, SAITECH) offer integration with supply chain management. 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 our survey, most of the respondents have specialized in private truck fleets, serving such markets as food and beverage (e.g., Anheuser Busch, Coca Cola and Gold Medal Bakery). Jeppesen’s PlanOp is being used by for-hire fleets, such as Australia Post and Purolator Courier.
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, SaaS provides routing services for a monthly fee, perhaps as low as $99 per month. 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 $125 per hour. In terms of pure size, many companies now claim more than 1,000 installations each.
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 assess the degree to which routing solutions and data must be integrated across multiple sites and decide whether they would like adopt the SaaS model or host their own software. It also important to ask 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? Can stops be scheduled on the spot, or will they be generated in batches? 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? With which software systems must the routing system interact? Vendors should demonstrate that they are experienced serving other fleets with similar requirements, and they should provide references so that you can verify claims.
Janice Partyka (firstname.lastname@example.org) is principal of JGP Services, a marketing consulting practice that focuses on mobile technologies and applications. Randolph Hall (email@example.com) is vice provost for Research Advancement at the University of Southern California.
To view the directory of vehicle routing software products along with the survey data, see: www.lionhrtpub.com/orms/surveys/vehicle_routing/vrss.html
- 31FEATURES Why large, once-successful companies fail By Gary Cokins The reasons are numerous, but the world’s problems are more complex than ever, creating the need for analytics. Actionable Analytics By Krishna Rupanagunta, Meena Anantha Padmanabhan and Vinay Mony How to convert thought into action and bridge the gap between analytics…