Transportation Route Optimization Heuristics No one is unfamiliar with transportation routes in this age of e-commerce. The UPS truck that delivers your shipment also delivers hundreds of other packages to various locations. Each location is a stop on the route of a delivery truck. These stops cannot be random for efficiency purposes. When UPS drivers leave their depot, they have a detailed route plan. This route plan aims to minimize certain factors like the total route travel time, route miles, etc., while servicing all the stops. These detailed route plans result from Vehicle Route Optimization (VRP) heuristics. Optimization algorithms have been used in classic operations research for decades, and at the core, these algorithms aim to generate the best outcomes for a scenario. In vehicle route optimization, the best outcome serves all the customers/stops while minimizing the miles traveled and route time. SAP TM module has a robust set of optimization engines that users can leverage. One of them is VSR, which performs vehicle route optimization. SAP TM VSR Optimizer Route optimization algorithms have existed in the market for decades, and hundreds of solutions are available. These solutions are similar in terms of features and capabilities. For SAP users, optimization engines for transportation planning are embedded in SAP Transportation Management (TM) module. SAP TM engine has multiple optimization engines. SAP TM VSR optimizer is the engine that helps plan optimal shipments based on available resources and parameters like demand, capacities, schedules, and transportation costs, among other parameters. Behind the optimizer’s interface is an algorithm that considers all the parameters and plans optimal routes.  Optimizing Run Times Vehicle routing problems are challenging to solve. In an age of the AI explosion, it may be difficult to envision that there are specific problems that algorithms still cannot solve quickly and efficiently, but the fact is, such issues do exist. In modeling parlance, these problems are known as NP-hard. There is a general agreement that these are impossible to solve with precision, which is why there are methods that generate approximate solutions. However, the solve time for approximate methods is also long, considering the relative difficulty of the solution. Thus, certain modeling best practices can be used to reduce the model run time. The VSR optimizer in SAP TM leverages a meta-heuristic that is a cousin of iterated local search heuristics. You can read more about iterated local search here. This multi-step approach repeats a series of steps until it gets the desired results. However, even with these approximate solutions, these models are run-time intensive. The following high-level buckets summarize the model development approaches to minimize model run time. Minimize model complexity: A smart rule of modeling is that it does not have to exactly replicate the real-world into the model to get an optimal solution. However, the drawback of doing this is that even minor additions in model parameters or constraints may significantly add to run times. As an example, we may add just one more unit of a specific container type to the model, the model must perform all possible calculations for that unit. Eliminating that unit from the model may reduce the run time drastically, while the impact on the solution may be minimal. Modes, lanes, and constraints are just a few areas to investigate to reduce model complexity and run time. Partition where possible: Segment model as much as possible. Split the model into sub-models, if possible. Note that VRP algorithms do some form of problem partitioning on their own to reduce run time. But if model can be split into sub-models, it can significantly minimize the total run time. Leverage multi-CPU cores in parallel: While this may be a no-brainer, the more cores, the better. Leveraging multiple CPU cores in parallel by selecting the right number in the optimization profile can help reduce the model run time. Different threads work on other plans in parallel, where each thread can perform the steps of iterative local search almost independently. ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

This article is based on a personal understanding of the current features of SAP TM. The features and functionalities mentioned in this article are not comprehensive. Please refer to the official SAP Product documentation for official and comprehensive coverage.