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) 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), and 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, and 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, and Allocations. (TSPS Application)
Strategic Freight Management: Rank bids by carriers for long-term contracts based on Cost, Capacity & Risk. (TSFM Application)
Among these, the VSR optimizer is the most complex one.
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 the 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 the 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 that 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 minimums, 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.
Assume that four crates are to be shipped from a warehouse to customers A, B, C, and D. TMS/ERP systems’ basic function is to store & simulate the real-world movement of money & materials. So in the TM system, each crate is represented by an object called Freight Unit[2]. The Freight Unit is the 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 pick up 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 th 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. The 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.
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 customers 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 the least distance or least time: A program finds all involved locations and valid routes between these (valid routes = lanes present in Master Data). The 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 the 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 set up for each truck, which specifies that the truck needs to come back to the depot. The duration and distance costs are calculated end-to-end, even if the truck returns empty in depot scenarios.
Distance costs can also be used to achieve the 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 - for 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 the 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 the 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 a 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 the truck leaves the trailer at a safe location, transports another trailer, comes back & completes the journey. In these cases, another dimension is added to the problem as it not only involves finding a trailer, a route, and intermediate locations but also a tractor to move this trailer.
We can also maintain a 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 fewer trucks, then we can create an MTR with expensive vehicles (Higher Transp. Costs in Lane), which will be used in this region when there are bottlenecks.
The plan should meet the Requested & Acceptable dates: The date interval within which customers request the 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 a “Pickup window” at the 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 the 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 the customer, slight penalty costs are added. If it is before the 5th or after the 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 increase 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 the number of intermediate locations. By using costs per quantity, we can strike a balance between the multi-drop off and the quantity transported. i.e. if there is more volume to be transported to a final location, then we need to get a plan with fewer 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 the existing stop sequence can be changed or not, and if a new Freight Order can be created or not.
Constraints: Constraints are expectations that cannot be violated. If a solution is not possible without violating these, then the plan is abandoned or the Freight Unit is abandoned. Some of these constraints like max distance, max duration, max intermediate stops, acceptable start & end dates, etc., were discussed in the 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 . 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 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 crates containing food and crates with chemicals to a customer. These crates must never be in the same truck, so we create an incompatibility between Freight Units at the vehicle level. Also, the customer doesn’t accept trailers as his warehouse gate is small. So we maintain another incompatibility at the Vehicle - Location level.
Working times, Breaks & Driving time limit: In some cases, handling resources like forklifts could be available only during particular times. Some countries have regulations specifying that 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 of the day. All these are hard constraints that can be modeled 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.
Genetic Algorithm: We have parameters like stops, routes, 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 the initial population after which the fitness function is used to find out the fittest chromosomes for reproduction. Then, genes are exchanged between the chromosomes (crossover) and new offspring are 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, and Reduce prepare the data which is called pre-solve. After this, the 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.
After this, in the post-processing step, detailed scheduling is done to determine the 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 a different solution, which is 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 FUs with the 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 the 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 at 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 the 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.
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 a cloud server. With parallel processing, optimization is quick and the planning can be completely automatic via a 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 planners to choose from. Also, SAP releases patches for the optimizer every week, adding new functionality.
Apart from the optimizer, TM’s other features like Carrier Selection, Business Network for Logistics for tendering, execution monitoring and settlement with transportation service providers, 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: A carrier or a Logistics Service Provider is the entity that 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 FUs that will be transported together. It has a 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