SAP schedules car drivers at scale

[dr__marcus_dettenbach]

Imagine you are a logistic service provider handling roll-on/roll-off (ro-ro) car logistics.

The biggest of such facilities can be found in harbors around the world. They have a capacity of several ten thousand cars with a daily throughput of a couple of thousands.

International car logistics is handled by ro-ro vessels. Inland transport happens on feeder vessels, trains, or trucks. The biggest of such ro-ro vessels can accommodate up to 8500 cars. As the name roll-on/roll-off suggests, those cars are driven by car drivers onto and from the vessel. It is easy to imagine that a logistic service provider must manage a car driver workforce of several hundred car drivers per shift to fulfill the daily business.

Shift scheduling is a classical optimization problem. The main issues are conflicting objectives as well as many constraints and short run time requirements. Luckily SAP provides the tools and the knowledge to tackle such problems.

My name is dr..marcus.dettenbach and I am a Data Scientist at SAP. This blog is about a solution we built to tackle the problem I just lined out.

Shift scheduling for car drivers in a ro-ro logistics company – How it works.

The problem can be seen as a matching of supply and demand. Demand in our case is the work that needs to be executed, i.e. cars to be loaded or unloaded. Supply is represented by the available workforce, i.e. car driver capacity per shift. The figure below illustrates a very simplified version of the problem.

Simplified illustrative concept of shift planning in a ro-ro context

We identified several constraints that must be considered. First, there is a set of more restrictive constraints, let’s call them hard constraints. The customer considers a shift plan not meeting theses constraints an infeasible solution. Examples of such criteria include:

• The handling of a vessel or train must be executed within a given time window


• All operations must adhere to a shift schedule


• Some operations must be carried out in sequence

Second, there is a set of soft constraints that might be violated to a certain extend. Examples of such constraints are:

• Car driver capacity per shift must be respected


• Capacity per shift should be planned as smooth as possible to allow high utilization of car drivers


• An upper limit of car drivers working at the same time on a vessel or train must be respected


• Operations should be split as little as possible

Based on our experience, literature research and run time requirements it became clear that a heuristic solution approach is needed. After an evaluation phase, we implemented a constraint-based optimization heuristic. All constraints are relaxed. In case a constraint is not met, e.g. the car driver capacity per shift is exceeded, a penalty cost is induced. The sum of all penalty costs constitutes the objective function that must be minimized. The concept of the heuristic is described by the following steps:

1. Start with an initial solution


2. Compute the penalty cost for the solution


3. Alternate the solution


4. Compute penalty cost for alternated solution and keep solution in case it is better than previously best solution


5. Repeat steps 3 and 4 until a stop criterion is met.

Of course, this sounds a lot easier than it is and I will not bother you with mathematical details. Let me just spend a few words on the concepts. The overall approach makes sure that at every point in time a solution exists. The shift plan quality of a solution can be validated easily.

Regarding the penalty cost: For each constraint mentioned above a penalty cost is computed in case the constraint is not met. When comparing different solutions, the objection function with solely the penalty costs of the hard constraints is considered. A solution with lower hard constraint penalty costs is better regardless the penalty costs of the soft constraints. In case the hard constraint penalty costs of two solutions are equal, e.g. 0, the soft constraint penalty costs are compared. This way we foster the creation of shift plans considered feasible by the customer.

Regarding alternating and evaluating new solutions: Here efficiency is key as the speed of this process determines the possible quality improvement over time. You can develop the alternating and evaluation logic yourself or rely on special JAVA libraries such as OptaPlanner, a constraint solver with construction heuristics and metaheuristics. It goes without saying that the usage of special libraries is much faster and usually more efficient.

Following the cloud mindset - Implementing the solution as a side-by-side extension

The overall software stack in this project consisted of several SAP Products like SAP Yard Logistics, SAP Multi Resource Scheduling and SAP Plant Maintenance. We decided to “keep the core clean” and developed the optimization algorithm as a stand-alone JAVA application. In the on-premise scenario the application is deployed to the SAP HANA XSA runtime and in the cloud scenario to the Cloud Foundry runtime which is an integral part of the SAP Business Technology Platform. Both runtimes are very similar and little work is needed to switch from one option to the other. The picture below illustrates the architecture highlighting the place for the JAVA application in blue and mentioning that SAP HANA XSA and Cloud Foundry could be swapped. Both runtimes support multiple other programming languages.

Illustrative SAP HANA XSA architecture

Let’s sum it up

To solve large scale shift scheduling problems an efficient heuristic solution approach was designed. The heuristic was implemented in a JAVA application. Using the capabilities of SAP HANA or SAP Business Technology Platform such an app can easily be integrated into the overall solution. This is equally possible in the cloud or on-premise.

Hands on next steps

Learn more on SAP Business Technology Platform and Cloud Foundry
Fundamentals of the SAP BTP, Cloud Foundry environment

Get a kick-start on SAP HANA Development. This blog post also compares XSA and Cloud Foundry runtime.
A Field Guide to SAP (HANA) Development | How to Get Started or Keep on Going without Getting Lost

Read more about applied optimization at SAP:
SAP optimizes Berth Plans to increase productivity and utilization of scarce infrastructure
SAP optimizes call center workforce to make customers and staff happy

If you are interested in applying optimization technics in your products or have any questions around optimization problems in general, please feel free to contact dr..marcus.dettenbach or engage in the comment section below.