Vehicle routing in practice: why manual planning is not sufficient
Posted by dr. Mieke Defraeye on 14/03/2016
Is your company lucky to have highly competent and experienced planners, who make daily route plans without optimization software? Are you nevertheless wondering if your transportation cost can be reduced? Our experience: you can reduce costs significantly, by combining the planners’ expertise with route optimization algorithms. Here’s why.
Route planning: the Vehicle Routing Problem (VRP)
If your company has to pick up and deliver orders to several customers on a daily basis with a fleet of trucks, then route planning is the problem of choosing which locations each truck will visit, and in which sequence this is done, in order to minimize transport costs. In the academic literature, this is known as the Vehicle Routing Problem (VRP), a topic that has been researched extensively over the past decades.
Challenges in real-world route planning: “Rich VRPs”
Real-world route planning, however, goes much further than the traditional VRP. A range of additional constraints and objectives arise in practical settings, and these need to be taken into account during the planning process. Drexl (2012) lists the following characteristics of real-world routing problems also known as “rich VRPs”
- Pickup-and-delivery requests. Does your company only deliver goods at your customers, or are you confronted with a combination of picking up and delivering orders? A commercial route optimizer should allow you to both pick up and drop off orders at any location.
- Compatibility between locations, requests, vehicles and drivers. Large trucks may not be able to access locations in narrow streets, the delivery of cooled products requires a truck with refrigerator compartment, customer and driver should preferably speak the same language etc.
- Multiple time windows for locations and requests. Customers and depots may have opening hours that vary per day of the week, and a specific order may need to be delivered within one or more allowed time windows.
- Consideration of service times. The time to pickup or deliver an order may depend on its weight or other characteristics. In addition, a fixed stop time per customer location can be relevant, e.g. for registration upon arrival.
- Heterogeneous fleet with respect to cost, capacity, start and end depots. The trucks in your fleet may differ in many ways – it is common that not all trucks are equally expensive. The location where trucks start and end their trip may also differ: drivers can start or stop at home, or at any depot.
- Multiple cost drivers. What are the key drivers of your transport cost? Is it driven by kilometers and work hours, or rather by the number of stops in a route? Do you have penalty costs, for instance for orders that are not delivered on the requested day? Our experience is that the transport costs to be minimized in route planning are highly company specific. Many companies have multiple cost components with different priorities. As such, a commercial route optimizer must be able to plan routes to minimize your logistics cost.
- Multiple capacity constraints. The maximal capacity of a truck is not solely determined by the maximal allowed weight. Volume, load meters, or other capacity constraints may be more relevant in your business. Therefore it is important that a commercial route optimizer can handle several capacity constraints simultaneously.
- Multiple use of vehicles. Vehicles can be used for one or more routes throughout the day. In addition, it is often not needed that a truck returns to the depot where it started the route.
- Driver rules. Drivers may have their default truck, or may switch trucks from day to day. In addition, regulatory breaks and lunch breaks need to be accounted for, and the work hour rules and regulations should be respected in route planning.
- Dynamic planning over a one-week planning horizon with event- or time-based rolling horizon planning. A route plan is usually not static, it changes when new information becomes available. Changes in order quantities, emergency deliveries, cancellations, etc. may require a revision of the route plan.
- Re-optimization options & interactive planning: full automation on route planning is often not desirable. Instead, a commercial route optimizer should allow planners to interact with the optimization process, and re-optimize based on user input.
Vehicle routing is a notoriously difficult problem, the “rich VRP” even more so
In many companies route planning is a mainly manual process, where planners construct routes based on their experience and business insight. And although the above rich VRP's features are indispensable in any state-of-the-art vehicle routing algorithms, few – if any – existing academic methods include them jointly. Therefore the use of commercial route optimizers is often scaled back to visualizing the planners' routes, as most of this route optimization software is inadequate in dealing with all the complexities that arise in a real-world business. However, the number of choices and business specific constraints that need to be considered while puzzling to make a route plan is huge, making it nearly impossible for any human being to solve a rich VRP close to optimal.
Automatic route optimization with refinement by planners is the way to go
Route optimizers are powerful tools for automatic route planning, but let’s be realistic: it seems unlikely that they can fully replace your planners’ experience and expertise. The synergy arises by using a combination of both: an interactive planning process, with the possibility to manually adapt an optimized plan and to re-optimize after adjustments have been made. This is what this may look like:
- The route optimizer provides an optimized plan, where your giant route puzzle is solved automatically within minutes, using state-of-the-art optimization algorithms.
- The planners assess the optimized plan and make minor adjustments based on expertise.
- The route optimizer continues optimizing, accounting for the changes the planner has made.
The majority of the planning effort is optimized automatically by a route optimizer, and the planners expertise is called in only when needed. This will allow your planners to save time, that in turn can be invested in improving other planning aspects, e.g. informing customers timely when a delivery is late, coordinating with production planning, tackling last-minute customer requests… We strongly believe in this approach that combines the best of two worlds: state-of-the-art optimization algorithms and human expertise.
References & further reading on the VRP
Cordeau, J. F., M. Gendreau, G. Laporte, J.Y. Potvin, F. Semet. 2002. A guide to vehicle routing heuristics. Journal of the Operational Research society, 512-522.
Drexl, M. 2012. Rich vehicle routing in theory and practice. Logistics Research, 5(1-2), 47-63.
Golden, B.L., S. Raghawan, E.A. Wasil. 2008. The Vehicle Routing Problem, Springer, New York.
Laporte, G. 2009. Fifty years of vehicle routing. Transportation Science,43(4), 408-416.
Laporte, G., M. Gendreau, J. Y. Potvin, F. Semet. 2000. Classical and modern heuristics for the vehicle routing problem. International transactions in operational research, 7(4‐5), 285-300.
Sörensen K, M. Sevaux, P. Schittekat. 2008. ‘‘Multiple neighbourhood’’ search in commercial VRP packages: evolving towards self-adaptive methods. In: Cotta C, Sevaux M, Sörensen K (eds) Adaptive and multilevel metaheuristics, volume 136.
Toth, P., D. Vigo (Eds.). 2014. Vehicle routing: problems, methods, and applications (Vol. 18). Siam.