December 1998 Driven by the expanding global economy — as well as mergers and acquisitions which have consolidated the manufacturing and retail sectors into fewer, more competitive corporations — the demand for supply chain management (SCM) solutions is growing exponentially throughout the industrial world. Demand for SCM has been further fueled by an increased awareness and focus on profitability tied to reduced operating costs. The ascent of SCM, coupled with the introduction of enterprise resource planning systems which dovetail with SCM to give corporations unprecedented insight into, and control of, their operations, has fostered an increased awareness of the impact that operations research systems and OR practitioners have on defining business processes and solutions. This article describes the real-life experience of one firm that suffered growing pains in its transportation system as it struggled to cope with rapid expansion, and details the impact OR-based software has had on helping manage the firm's day-to-day transportation operations. The company shall remain nameless, but the story is true. A Transportation Manager's Nightmare Joe is the transportation operations manager for a major do-it-yourself home improvement retailer which operates stores nationwide. He is responsible for shipping more than a million pounds of merchandise from several thousand vendors located worldwide onto the shelves of hundreds of retail stores each day. The merchandise involved ranges in shape, size and weight, from nails to power drills to lawn fertilizer to ride-on tractor mowers. Joe's transportation function represents the critical link in his company's supply chain management process, and is key to its competitiveness and profitability. If the store in your neighborhood doesn't have the drill you want in stock because of a late shipment, you'll surely take your business down the street. Or even if it's in stock, you may choose to buy the drill from a competitor if Joe's shipping costs drive up his price. Joe's job is a delicate balancing act between competing goals of reducing transportation costs and increasing customer service levels while satisfying many conflicting side considerations. Although Joe is not schooled in OR, as we will see he tackles a tough real-world OR problem with a fresh new (albeit ugly) data set every day. Joe's daily routine begins with reviewing new or modified orders received from an order processing system and resolving data errors (inaccurate information). Next, he must decide how best to ship them, choosing among several alternative modes and carriers. Before he had the help of optimization software, he performed this difficult step manually. The remainder of his day is spent awarding shipments to carriers, generating bills of lading (BOLs) and, most importantly, communicating shipment details (scheduled pickup/delivery times, etc.) to the vendors, stores and carriers, primarily by phone and fax. Like many retailers, Joe's company does not currently manage its own fleet of trucks. Instead, they rely on outside truckload (TL) and less-than-truckload (LTL) motor carriers, as well as small package delivery companies. Carrier contract terms specify the types of freight these carriers will handle, negotiated rates along travel lanes, and charges for special services. As their names suggest, TL rates are designed for large (i.e. > 10000 lbs.) shipments, LTL rates for mid-sized loads, and small package rates for under 150 lbs. or so. In deciding how to ship each order, Joe can take the easy route and book them individually with LTL, TL or small package carriers based strictly on order size. To cut costs, however, he can build routes combining LTL orders into multi-stop TL shipments to take advantage of cheaper per-mile TL rates (multi-stop order consolidation). Trying to find the most cost-effective combinations of orders is a complex task however, so Joe often must overlook savings opportunities to focus on the other tasks required to get shipments out the door and delivered on time. As his company grew over the years, so did Joe's workload. With the addition of new vendors and new stores, the volume of shipments grew to the point that the tasks of correcting order errors, generating BOLs and communicating shipment details to vendors and carriers consumed most of his department's time. This left little time to look for order consolidation opportunities, and as a result, the bulk of his shipments went individually using expensive LTL carriers. In fact, the majority of Joe's vendors were simply allowed to take care of their own shipping, and passed along high shipping charges in the price of the goods. The Nightmare Gets Worse Joe's problems were compounded in 1997 when his parent company merged with two competing chains, more than doubling the number of stores and volume of shipments overnight. Corporate hoped to squeeze out additional profits by integrating transportation functions across the new company, and began cutting costs by eliminating redundant positions. Fortunately, Joe kept his job, but his traffic planning workload was drastically increased and became even more complex. Ironically, the increased number and geographic spread of vendors and stores created more savings opportunities, but these opportunities were increasingly being missed because the amount of data to process had become staggering. There was no effective way to address the problem with additional people either, for if they divided the set of orders among them (by origin or destination regions, for example), they would pass up opportunities for multi-stop routes spanning the regions. They needed software to globally optimize all orders, considering all available shipment modes and carriers. Around the time of the mergers, a new vice president of logistics joined Joe's company with aggressive ideas about revamping the company's logistics strategy. The new vice president was intent on redesigning their distribution network to adopt a pure "cross-docking" strategy, which was becoming all the rage in retailing [Logistics Management, October 1997]. Cross-docking would allow them to eliminate costly inventory entirely throughout the chain, but would require shutting down all of their existing distribution centers (DCs), and replacing them with pool points throughout the country. The vice president simultaneously launched a "freight conversion" program, under which Joe's traffic department took control of the shipment process away from the vendors. Shifting from vendor-managed to in-house controlled freight would provide increased visibility of shipments, potentially shortening the length of the supply chain. It also would allow them to negotiate better unit-level pricing for the goods themselves, and place the challenge on Joe's traffic department to "beat" the old shipping costs charged by the vendors. (This trend in the retail industry is known as inbound logistics management.) To summarize Joe's situation: An increased daily volume of shipments arising from the steady growth of his retail chain overloaded his traffic department. Mergers with competing chains doubled his shipment volume almost overnight. He needed to reduce freight costs. He needed to convert from vendor-managed shipping to in-house controlled freight from vendors. He needed to blend best-shipping practices of former companies to take advantage of multi-stop truckload shipment and cross-docking savings opportunities. Management realized that they had to do something fast. Operations Research-Based Transportation Management Software to the Rescue To implement this ambitious logistics strategy, Joe's department laid out their requirements for a transportation management software package that could be tailored to their needs. After a thorough selection process, his company chose a flexible inbound/outbound freight consolidation and logistics management software package. They chose the package as much for its existing capabilities as for the willingness of the vendor's staff of OR practitioners and software engineers to listen to what they were trying to accomplish and modify the software to accommodate their needs. What they required of the software was the ability to dynamically build the most cost-effective mix of multi-stop TL and pool shipments based on unique sets of several thousand orders and actual carrier rates each day. And they needed it to produce a solution in minutes, not hours, so that they could replan throughout the day in response to last-minute changes, without holding up the process of booking shipments. To accommodate this requirement, the software was modified to consider hand-in-hand two logistics strategies which had previously been handled separately: multi-stop order consolidation and pooling. Multi-stop order consolidation is a cost-savings logistics strategy that involves building loads (routes) combining LTL-sized orders into multi-stop TL shipments to take advantage of cheaper per-mile TL rates. This load-building problem is extremely complex for a retailer dealing strictly with competing LTL and TL carriers. In this environment, the objective is not to minimize the number of trucks or the total miles traveled, as in fleet management problems. Rather, order consolidation seeks to minimize a non-linear total shipping cost function by exploiting the LTL and TL rate structures in place. Indeed, if orders are small and origins and destinations are scattered about, the solution may be to ship each individual order direct using LTL carriers, which have a virtually unlimited supply of trucks. (This simple assignment always represents an upper bound on the total cost.) On the other hand, the best solution may assign multi-stop truckload shipments to a variety of TL carriers, based on which carrier offers the best rates along specific travel lanes and today's availability of trucks. TL routes may appear to go somewhat out of the way to pick up and deliver additional orders (incurring extra per mile and stopoff charges), but still result in savings compared with shipping the orders LTL. Pooling or cross-docking is a strategy in which central locations (pools) act as trans-shipment points in the distribution network. What distinguishes pooling from traditional use of DCs is that little or no inventory is held at the pool, thus minimizing holding costs. In many cases the pool is not operated by the shipper, but by a third party, eliminating facility ownership costs altogether. The day-to-day pooling problem is to build truckloads made up of many smaller orders from one or more vendors and route them to pools, where incoming shipments are broken up into smaller orders (for a small handling charge) and redelivered at LTL rates to many local stores. This bypasses DCs altogether (see Figure 1). Significant cost savings may be achieved when the total pooling cost (the TL portion of the trip plus handling and local LTL redelivery charges) compares favorably against shipping orders individually LTL into stores across the country. Figure 1: Multi-Vendor Inbound Pooling for Retailers: In this example, orders from two vendors on the West Coast are needed in stores on the East Coast. OR-based transportation management software helps traffic departments build multi-stop truckload (TL) cross-country shipments which deliver merchandise either directly or through cross-dock facilities to stores. Significant cost savings may be achieved compared with shipping orders individually at expensive LTL rates. Is Operations Research Ready for Prime Time? Taken separately, multi-stop order consolidation and pooling are each extremely difficult combinatorial problems. We learned back in our OR school days that such problems are in the class called NP-hard, and would take lifetimes on a computer to solve. When we recognize the non-linear objective function, we immediately imagine algorithms getting stuck on local optima, far from the true optimal solution. The requirement to embed an algorithm into a real-time application to consider these two logistics strategies together on large data sets seems impossible. Order consolidation and pooling resemble in some aspects the textbook vehicle routing problem (VRP) and its alphabet soup of extensions. An excellent introduction to research on the VRP is provided by Marshall Fisher in "Handbooks in OR & MS," vol. 8. Unfortunately, the list of "complications" which follows his problem description reads like a checklist of the difficult constraints faced by Joe the retailer. Fisher traces three generations of vehicle routing research: Simple heuristics Math programming-based heuristics Artificial intelligence techniques and optimization algorithms Despite all this valuable research, the message, as feared, is that no robust algorithm exists which can be transferred from one company's problem to another (and that we could spend a career trying to develop one). Furthermore, computational results accompanying much of the research suggests that it was primarily focused on improving upon best-known solutions to standard data sets. These data sets numbered at most 200 customers, and with the exception of the heuristics, runtimes were reported in minutes, not seconds. Could it be that OR isn't ready for prime time — day-to-day problems involving thousands of orders? Julien Bramel and David Simchi-Levi's excellent recent book, "The Logic of Logistics," offers a survey of practical solution approaches to the vehicle routing and other logistics problems, with a focus on heuristics. Again, we don't find a canned solution, but we are heartened by examples and proofs it offers that effective algorithms can be developed. Operations Research Practitioners Roll Up Their Sleeves and Roll Out a Solution Getting back to our example, Joe's traffic department was missing out on thousands of dollars of savings each day, and his problems were growing. The logistics software vendor's OR department was on the hook to help fast. It was clear that no linear programming model or, for that matter, any algorithm documented in the literature, could be applied to Joe's multi-stop order consolidation and pooling problem. But the problem sure looked and smelled like an OR problem, with the following characteristics: Minimize an objective function (shipping costs). Choose between competing alternatives (assign orders to LTL, multi-stop TL shipments, deliver directly to stores or through pools). Subject to limited resources (TL carrier availability, truck capacities) and side constraints (time windows, pickup/delivery sequence). Despite the lack of an off-the-shelf algorithm, the OR team knew they could help. Even the most advanced optimization algorithm is nothing more than an efficient search of the solution space. Recognizing this, the OR team knew they had one thing in their favor: the load-building experience of Joe's traffic department coupled with their own transportation and OR backgrounds. Since the size of the problem and its solution space was potentially so large, they worked closely with Joe to incorporate his knowledge into an algorithm tailored to focus its search on feasible combinations of orders/shipping mode selections most likely to generate significant cost savings. Leveraging heavily on their library of transportation algorithms, the OR team was able to "marry" the previously independent multi-stop order consolidation and pooling algorithms and deliver a customized transportation management software to Joe's department within a few short months. Operations Research Pays For Itself After a series of enhancements were added to the software and a testing phase was completed, Joe's department "went live" with the software in the spring of 1998. To date, the pooling concept has been a smashing success. In fact, as soon as control was assumed over a sufficient number of vendors, the software more than paid for itself processing barely one week's worth of orders. The software's automated order consolidation and pooling functionality identified savings opportunities hidden within thousands of orders which were simply not humanly possible for Joe to find manually. The moral of the story is that OR is ready for prime time, and there is a demand for OR practitioners to package their expertise into tailored solutions to day-to-day logistics problems like Joe's. Bill Schineller is manager of operations research at Logistics Information Systems, Inc. (LIS), a transportation management software company headquartered in Framingham, Mass. LIS's software modules, including MAXPAYLOADTM, utilize OR techniques to optimize both the inbound and outbound shipping processes. Schineller can be reached via e-mail at bschineller@liscorp.com. LIS is on the web at www.liscorp.com. TIPS FOR EMBEDDING OPERATIONS RESEARCH INTO TRANSPORTATION MANAGEMENT SOFTWARE By Ozlem Ergun A key transportation management software (TMS) issue is determining how to efficiently use a given fleet of vehicles (including: private, LTL, TL, and small package delivery carriers) to pick-up and deliver shipments. The problem is to determine the pickup and delivery sequence of shipments assigned to each vehicle which minimizes total cost, subject to a variety set of constraints such as vehicle capacities, pick-up/delivery time restrictions and load/unload precedence. This problem can be modeled as a vehicle routing problem (VRP) with many side constraints. Given that the VRP is notoriously hard, the size of the real world data sets can make it impractical to just formulate the problem as an integer program (IP) and use an advanced IP solver to get an optimal solution. Practitioners often turn instead to solution techniques that yield acceptable solutions within a reasonable time frame. These include: Route building heuristics select arcs greedily in a sequential manner until a feasible solution has been created. Route improvement heuristics start with a feasible solution and seek a small change that reduces cost while maintaining feasibility. Mathematical programming-based heuristics solve to optimality some mathematical programming approximation of the problem. These approximations are solved using several techniques such as Lagrangian relaxation algorithm and column generation. Artificial intelligence/self-adaptive methods include tabu search and simulating annealing. These start with initial feasible solutions, then repeatedly make a local change to the current solution (such as swapping shipments between vehicles). Each new solution is accepted if it satisfies certain criteria. Whereas traditional local improvement methods accept a local change if it strictly decreases the cost, and stop when such a change does not exist, tabu search and annealing allow the selection of non-improving solutions under certain conditions. A third approach, genetic algorithms, uses ideas from the evolution theory to create new and hopefully better feasible solutions. Optimization algorithms are based on polyhedral combinatorics, and a variety of relaxation techniques. The idea is to first solve an easy relaxation of the problem and then try to create a feasible solution for the "real" VRP based on the relaxed optimum while not increasing the cost too much. Regardless of the chosen technique, an important tip for the OR practitioner is this: Understand and take advantage of your client's business rules concerning fleet utilization. Observe the client's current procedures, ask questions, and get your hands on real data early on in the development process. The business rules you discover may be incorporated directly into the model as constraints, or better yet, applied in a preprocessing step to drastically reduce the problem size. Business rules can be your friend — they make the problem more manageable and help ensure that the plans your software generates can be applied in practice. Finally, the practitioner must never forget the absolute requirement of TMS to facilitate the inevitable changes users make to recommended plans. The capability not only to allow the user to change plans, but more importantly, to provide insight into the cost impact of changes, is key to the software's operational success. Ozlem Ergun is a graduate sudent at the Massachusetts Institute of Technology, currently pursuing a Ph.D. in operations research. She recently completed an internship at LIS, working as part of the operations research team to revise and develop new algorithms for solving complex logistics problems. Table of Contents OR/MS Today Home Page OR/MS Today copyright © 1998 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 1998 by Lionheart Publishing, Inc. All rights reserved.