12/05/2018

Secrets of the SAP Transportation Management Optimizer

Introduction:

Every day, businesses ship a lot of goods from their warehouses to customer locations or from vendor locations to their own warehouses. These goods can be shipped in a ship, airplane, train, truck etc. This movement of goods, also called shipments can be virtually simulated to identify the shipments with common routes that can be combined, leading to major cost savings.

SAP developed Transportation Management (TM) module to make the Supply Chain Logistics and Execution processes of businesses efficient, cheaper and more transparent. Optimization is at the core of these goals and this concept is also used in APO (Advanced Planning & Optimization), PLM (Product Lifecycle Management) modules. In the SAP world, I saw that the optimizer is treated as a black-box by some. In this blog, I will try to explain the logic behind the heart of the TM module - VSR Optimizer (VSR = Vehicle Scheduling & Routing).

SAP TM has four different optimizer engines -

VSR Optimizer: Plan Shipments in the best possible way on available Vehicles via available routes. TVSR, TVSS, TVRG Applications come under this.

Load Optimizer: Arrange pallets or packages on the vehicle considering rules like Stackability, etc. (TVSO Application)

Carrier Selection: Rank carriers[1] for each shipment considering costs, Business Shares, Allocations. (TSPS Application)

Strategic Freight Management: Rank bids by carriers for long-term contracts based on Cost, Capacity & Risk. (TSFM Application)

Among these, VSR optimizer is the most complex one.

What is Optimization?

Optimization is the act of making the best use of a situation. In the real-world, it may translate to finding a solution with the lowest time/distance (Ex: Traveling Salesman Problem) or the maximum utilization (Ex: Knapsack Problem), etc. Some examples are Stock Portfolio Optimization, Inventory Optimization, Warehouse location optimization, Employee Scheduling, airport gate allocation, etc. Even evolution of species by natural selection is a form of brute force optimization. Optimization is one of the best applications of prescriptive analytics.

The goal is to find the global minimum or maximum of an Objective Function subject to some Constraints. Different input values within these constraints are passed to the function and all the possible solutions are compared to arrive at the desired solution. Pseudo costs can also be assigned to these attributes based on their importance. Constraints limit the number of possibilities and reduce the solution space. In TM, we can have hard constraints and soft constraints/preferences. The hard constraints should not be violated and the soft constraints can be violated with some penalty.

The capacitated vehicle routing problem, which VSR optimizer solves is a generalization of the traveling salesman problem. For a traveling salesman problem (TSP), with fifteen stops, we can find the optimum route easily as shown below.

For 16 locations above, we have 15!/2 = 653837184000 permutations whereas if you have 7 locations, it is just 7!/2 = 2520 permutations. The above 15 location problem took about a minute to be solved. In 1994, the record was solving a TSP problem with 7397 cities and it took 3 - 4 years of CPU time. With growing computing power, the number of cities too increased and currently, a 109399 city instance is the largest non-trivial instance solved to optimality[4].

Solving just the TSP is easy but solving with Time Windows for each city is hard and solving with multiple vehicles, each with limited capacity is harder than TSP-TW. So this brute force method is not feasible in complex scenarios where there can be millions or even billions of possible solutions to this NP-Hard problem. So we use Heuristics to start finding our solutions from the most promising spaces and choose the best among the several good solutions obtained in this method, which can give us results which are within 1-3% of the most optimum solution. SAP TM uses genetic algorithms, which is a subset of evolutionary algorithms to solve the optimization problem. These algorithms are inspired by the theory of natural selection.

In the above figure, there are several local minimum’s but a single global minimum. All the solutions in the neighborhood are evaluated until a minimum is found. Then the search is started from a different random location. In this way, several solutions are evaluated and eventually, the optimizer arrives at the global minimum or any point closest to it.

VSR Optimizer Problem Statement:

Assume that four crates are to be shipped from a warehouse to customers A, B, C, D. TMS/ERP systems’ basic function is to store & simulate the real world movement of money & materials. So in TM system, each crate is represented by an object called Freight Unit[2]. Freight Unit is a smallest transportable unit and its granularity varies per business. These crates can be transported in trucks, trailers etc which are called vehicles and a vehicle can pickup and deliver at multiple locations.

These are the inputs to the optimizer:

The job of the VSR optimizer is to map these Freight Units to Vehicles to create a Freight Order[3], which is another object representing transportation plan with vehicles, locations sequence, dates, etc., finalized as shown below.

As part of this, the VSR optimizer has two goals - Vehicle Routing and Scheduling. Optimizer has to route the shipments. i.e. Find the best possible route the truck must take through the location network, meeting all the time restrictions. The next step is scheduling where start and end times are assigned to various activities for each of the locations, vehicles, etc. The solution for this problem must be found, considering all the constraints and preferences. So in the end, for each location and each vehicle, a "To-Do List" is created along with the specific timestamps which tell when to start and stop loading/unloading, when to Uncouple/recouple trailers, etc as shown below. Also, if anything is changed manually, all the subsequent times and affected objects should be changed accordingly.

Constraints & Preferences:

Preferences:

These are the expectations from the optimizer but are not mandatory. These expectations will be controlled by planning costs, which are maintained per Means of transport. There are Fixed and variable costs. It is important to maintain the costs for different attributes based on their importance accurately. The optimizer always chooses the solution with the cheapest overall costs. These are the preferences in our objective function:

Determine if the goods are to be delivered or not: A freight unit is non-deliverable if it has date conflicts or if there are no vehicles available, etc. To prevent the optimizer from giving us a solution where none of the FU's are planned, we maintain a very high non-delivery cost per FU. For example, if one of the customer needs the crate by tomorrow, but the transit duration is 2 days, since it is impossible to deliver, this Freight Unit is set aside and all the subsequent solutions will have the non-delivery cost added.

Find the route with least distance or least time: A program finds all involved locations and valid routes between these (valid routes = lanes present in Master Data). Distance matrix for these routes is filled using distances from GIS API or lane, or a straight line distance.

Higher distance costs force the optimizer to choose shorter routes and vice versa for time costs. Distance costs can be assigned for entire planning profile or individual lanes. Along with these preferences, we can set up hard constraints like maximum distance, maximum duration or the maximum number of intermediate stops for each Freight Order. In some scenarios where own trucks are used, depots can be setup for each truck, which specifies that truck needs to come back to depot. The duration and distance costs are calculated end-to-end, even if the truck return empty in depot scenarios.

Distance costs can also be used to achieve desired routing. For example if Warehouse B is an intermediate location and if this warehouse has higher storage costs, we can maintain a higher distance multiplying factor for all the lanes going to B, which reduces the number of trucks routed via this expensive warehouse.

To reduce the number of transshipment location combinations, you can define transshipment location chains and to reduce the memory taken by the distance matrix, you can use reference coordinates.

Choose the cheapest vehicle resources: Anything that transports goods is a resource. The vehicle resources are categorized into Means of Transport - example Full Truck Load, Less than Truck Load, etc. We can consolidate all crates going along the same route in one truck until it is full in terms of volume or weight. The Fixed Costs per Vehicle Resource/Per Capacity document control this and reduce the total number of vehicles used or Freight Orders created. However, LTL carriers charge per the storage used on their truck. In these cases, Cost Functions can be used to model vehicle utilization in a more complex way by setting up break weights and linear costs with slope in between them. i.e. Different costs for different size loads. So goods are sent using LTL or FTL depending on which is cheaper.

While planning in transportation cockpit, we select the resources to be used. These resources belong to Means of Transports and each Lane has some MTR’s. The distance matrix is filtered to contain only the location combinations which have valid lanes & MTR’s. The distance matrices are now complete with relevant locations, distances between the locations and the MTR's for these lanes, which finalizes the transportation network model. Due to this compounding effect, reducing the number of resources leads to considerable reduction in the CPU time as well as the Memory used.

Sometimes trailers are used and the scenario might involve a single trailer being carried to an intermediate location by one truck and from there by another truck or sometimes truck leaves trailer at a safe location, transport other trailer, comes back & completes journey. In these cases, another dimension is added to the problem as it not only involves finding a trailer, a route, intermediate locations but also a tractor to move this trailer.

We can also maintain minimum acceptable utilization % but this might lead to very long routings to fulfill the expected utilization. Also, if a region always faces bottle-neck situations due to less trucks, then we can create a MTR with expensive vehicles (Higher Transp. Costs in Lane), which will be used in this region when there are bottlenecks.

Plan should meet the requested & Acceptable dates: The date interval within which customer requested delivery are requested dates. The dates outside this interval until it is okay to deliver are acceptable dates. It is preferred to deliver within requested dates but if there are cost savings, we can do delayed or early delivery with a pseudo cost penalty during optimization. Like this “Delivery window”, we also have “Pickup window” at source location to consider requested & acceptable dates for pickup. It is recommended to use one of these windows only and do either backward or forward scheduling to arrive at the other set of dates. For example, in below image if goods are delivered in between customer requested dates 6th - 8th, no costs are added. If goods are delayed or are early by one day, which is still acceptable by customer, slight penalty costs are added. If it is before 5th or after 9th, then a very high non-delivery cost is added and the FU is removed from the plan.

Use Multi - Pickup and Multi-Drop off: Multi-Pickup & delivery increases cost savings via consolidation in high volume lanes. The fixed cost per vehicle/tour helps us minimize the number of vehicles used. The optimizer automatically considers the Loading sequence based on the location sequence. We can also maintain the maximum number of pick up locations and the maximum number of drop off locations as constraints or we can give stop costs to try to reduce number of intermediate locations. By using costs per quantity, we can strike a balance between the multi-drop off and quantity transported. i.e. if there is more volume to be transported to a final location, then we need to get a plan with less number of intermediate stages. The costs per quantity help us do that. This can also be multiplied by the distance to make the distance inversely proportional to the final destination volume.

Incremental Planning: Freight orders already created can be changed if there is an opportunity for better utilization as long as the execution of these orders has not started. We can customize to what extent the freight orders can be changed too. i.e. if new stops can be added or not, if existing stop sequence can be changed or not and if a new Freight Order can be created or not.

Constraints:

Constraints are the expectations that cannot be violated. If a solution is not possible without violating these, then plan is abandoned or Freight Unit is abandoned. Some of these constraints like max distance, max duration, max intermediate stops, acceptable start & end dates etc., were discussed in above section for easier understanding.

Capacity: While planning, the capacity cannot exceed the capacity of the vehicle or container. This check is done at multiple levels - for mass, volume, number of pallets, etc etc. and if any of these exceeds the available capacity in those dimension units, the vehicle will be considered to be full.

Incompatibilities: There can be (in)compatibilities in between orders, vehicles, locations or a combination of them. In the model building phase, the incompatibilities are evaluated and passed to the optimizer. This cuts down a lot of data that is processed by the optimizer and makes the solution space smaller. Example: From our warehouse, we ship a crates containing food and crates with chemicals to a customer. These crates must never be in same truck, so we create an incompatibility between Freight Units at vehicle level. Also, the customer doesn’t accept trailers as his warehouse gate is small. So we maintain another incompatibility at Vehicle - Location level.

Working times, Breaks & Driving time limit: In some cases, the handling resources like forklift could be available only during particular times. Some countries have regulations specifying that the drivers cannot drive for more than X hours in a day (DOT Rules). Some warehouses or customer locations might be open only during certain times in a day. All these are hard constraints which can be modeled in using break calendars, activities, etc., but they highly increase the computations.

Planning Horizon: Planning horizon is a time window within which all the freight orders' activities need to be completed. It restricts the total time for the truck to make a round trip if we are using a depot location for example. This time window acts as a hard constraint in the planning.

VSR Optimizer way of working:

Genetic Algorithm: We have parameters like stops, route, vehicle, etc which are represented as genes in binary format. The combination of genes (1001, 0001,0000, etc) is a Chromosome (100100010000), which is the solution. The collection of solutions is population. There is also a fitness function to evaluate the goodness of the solution/chromosome. The process starts with identifying parameters, then creating initial population after which fitness function is used to find out the fittest chromosomes for reproduction. Then, genes are exchanged between the chromosomes (crossover) and the new offspring is added to the population. After this, within the resulting chromosome, some genes can be interchanged (mutation). This is one generation. This process is iterated for a couple of generations until there is no significant improvement in fitness. These are the phases in which the solution is evaluated:

The RCC framework connects all the applications and sends data to the optimizer which is stateless. In the optimizer, the modules Model Generator, Repair, Reduce prepare the data which is called pre-solve. After this, Evolutionary Local Search Module does optimization and the module solution checker checks for flaws in this. After this, the scheduler adjusts the dates and times so that there are no gaps or truck wait times, etc.

  1. Model Building Phase: The RCC framework starts the optimizer which reads all the data and the relevant optimizer settings obtained from the TM application. The tables are also written to an input file which, along with the trace file can be accessed after the optimization run. From this data, an in-memory TOR object model is built, which has all the objects and dependencies. In this model, for each FU, a network is created in the form of graph structure with nodes (Source, Destination & Transshipment Locations) and edges (relationship - unidirectional or bidirectional) and for each vehicle, the possible tour instances are simulated. This network is built considering the FU-Location Incompatibilities, Zone Hierarchies, Vehicle Availability for vehicle to vehicle transfer, Fixing status and FU constraints (except time constraints), etc. This pre-solving reduces our search space by removing the useless Lanes/Vehicles and undeliverable Freight Units due to missing lanes, etc., and all these inconsistent objects are "fixed", and the fixing status is propagated to the dependent objects.

  2. Initialization Phase: The first step is to try to put all the FU's on vehicles randomly and create a plan, so that no matter when the optimizer is stopped, it always has a valid solution at hand. Each FU has 2 positions - Pickup and Delivery - which are to be placed on the timeline of Vehicle(s) through different location sequences in between. Different location sequences and different Vehicles are tested for each additional FU and by making these small changes in routing by heuristics like Nearest neighbor, 2-opt, k-opt, etc , it finds the local minimum which has the highest fitness value in the neighborhood, which is called local search. This process is iterated. The initialization phase can use the parallel processing capabilities for more number of random initializations. This evolutionary local search occurs over a number of generations

  3. Improvement Phase: Now, large changes are done like removing vehicles from plan, changing travel sequences, etc., to find cheaper solutions. There are different pre-defined operators which are activated or deactivated at each step to make these large changes. Also, detailed scheduling is done in this phase. This phase stops whenever time finishes or when there is no improvement in fitness value with time.

After this, in the post-processing step, detailed scheduling is done to determine final optimum sequence of events. Enhancements can be done using BADI in this step and also the changes that happen in this step are not shown in the RCC Log. Enhancements can also be done in the pre-processing step to influence the input values. After this, start the next logical step (Ex: Carrier Selection, Tendering etc.) automatically using strategies.

There is another planning method - Transportation Proposal, which also uses the optimizer but in a different way. In this method, the various diverse solutions are actively sought out instead of just focusing on the Costs as the normal Optimizer planning does. The result is a set of different solutions, with their costs where the user can manually choose among these best solutions. In this, the freight units are clustered into subsets and for each subset, the optimizer searches for different solution, which are finally combined.

The random seed is constant across all the planning runs. So you should get the same results if you plan the exact same FU's with same Vehicles, routes etc. But if you see that the results are different, then it means something has changed (maybe the context as you now have previously planned FO included in planning run or maybe the capacity or the validity of lanes etc.

Also, there are different variants within optimizer planning. For example, the optimizer can create entirely new FO's or change the existing ones (Incremental Planning). It can plan the entire FU at once or each stage in the FU separately, which is mainly used in Ocean transport with pre-carriage, main-carriage and on-carriage. Everything can be customized by tweaking the Planning Profile.

With different types of capacities, i.e. Trucks, Trailer Units, Planned Freight Orders, Ocean Freight Bookings, LTL Tariffs and with different types of demands, i.e. Freight Units, Container Units, RailCar Units and with different constraints discussed above and with specific requirements like Compartments in Trucks, Minimum/Maximum storage time at hubs, Depot Locations, etc., the complexity increases. However, this complexity can be reduced drastically and best results can be achieved very quickly by dividing the planning process into different sub-scenarios, cutting down the number of lanes/Vehicles and letting the process take care of some planning burden.

Should you use SAP TM?

The optimization process can be done in industrial solvers like ILOG, GAMS, CPLEX, etc., or using R/Python functions, etc., or even in Excel to an extent. There are many reasons for a big business to choose SAP TM software over these.

The VSR optimizer is built to be highly customizable keeping several business models in mind. It gives very good results quickly even when a large amount of data is passed to it. The optimizer is stateless and it can be run on a different application server or even on cloud server. With parallel processing, optimization is quick and the planning can be completely automatic via batch job or completely manual by drag and drop or interactive (results generated by the optimizer are monitored and corrected by the planners). You can also do Gantt Chart based planning or Map based planning or even command line based planning. There is another planning mode called Transportation Proposal which gives a set of widely varying plans for planner to choose from. Also, SAP releases patches for the optimizer every week, adding new functionality.

Apart from optimizer, TM’s other features like Carrier Selection, Collaboration Portal for Tendering, POWL queries for easily accessing data, Event Management & Fiori mobile apps for tracking, Charge Management, Settlement, Cost Distribution, BW/BI, Lumira for visualization & Analytics and Business Context viewer for contextual dashboards magnify the advantages of using TM. The best part is that everything can be done in a web browser. If all these features are developed in-house, it would take a lot of time and money and for big businesses, having a system of record, that integrates well with their existing ECC system has many benefits.

Glossary:

[1] Carrier: Carrier or a Logistics Service Provider is the entity who physically ships the goods. For example - USPS, Fedex, Radiant Logistics, etc.

[2] FU: Freight Unit: The document which represents the goods that are to be planned together. It has source location, destination, weight & volume of goods to be transported, expected date of delivery etc.

[3] FO: Freight Order: The document that represents the final plan, which is a collection of FU's that will be transported together. It has source, destination locations, truck used, actual transportation dates, etc.

Utilization: A truck is said to be 80% utilized if it is 80% full. For trailers, the highest it has ever been filled in that particular run is its utilization.



References:

SAP TM Whitepapers

support.sap.com

[4] http://www.akira.ruc.dk/~keld/research/LKH/

https://www.msi.umn.edu/sites/default/files/OptimizingWithGA.pdf