Effective optimization: Different tasks, different optimizers

[thomas_engelmann]

During the last years SUV’s became very popular in Europe. SUV stands for “Sport Utility Vehicle”. It is a kind of cars. Usually they are large, have a strong motor and look like they could drive off-road. You could get the impression this kind of car is perfect, you can do anything you want. But in reality there are still a lot of other cars. In cities you drive smaller and more agile cars, families often drive vans, because the need more space than SUV’s could offer. And if you really want to drive off-road you need a much more specialized car than a SUV.

With optimization it is somehow similar: If you look on general approaches like Genetic Algorithms or Mixed-Integer-Programming, you may have the impression, that you can solve every problem with such a general approach. And somehow you are right; in general you can do that. But there are the important questions, if you can do it efficiently. For our business it’s the questions, if you find good transportation plans in an acceptable duration with a general all-fits-one-approach.

If you would try to solve all transportation problems with on general optimizer, you would get into large performance problems. There are mainly two reasons:

• Dependent on the kind of problem the one or other algorithm behaves more efficient.


• You need to exploit the business  knowledge about different tasks and to integrate it into your solution approach to become efficient

In TM we currently use two kinds of general algorithms. One is Mixed-Integer-Programming. Here you map your business problem into a mathematical formulation. In contains continuous, binary and discrete variables and linear constraints. Very efficient solvers exist for this kind of formulations. After such a solver computed the solution, you finally re-map the solution into your business scenario.
One great behavior of Mixed-Inter-Programming is that, it can tell you if it found the optimal solution or not, and if how far you are away (more concrete: how much potential improvement of the objective function may be possible).

Not a strong point for Mixed-Integer-Programming is the optimization of permutations and sequences. For special cases like a pure Traveling-Salesman-Problem(TSP) exist great solutions. But our usual TM planning problems have much more Features than a pure TSP: not one but multiple resources with different capacities, different kinds of time windows, a lot of additional objective functions and much more. If you map all these features into a linear constraints like needed for Mixed-Integer-Programming you end up in a large amount of variables and constraints. A usual VSR scenario would not be solved in appropriate time frame. Because of that we use a Meta-Heuristic  for VSR. “Heuristic” means that we work with more or less simple construction steps to build plans. “Meta” means, that we build a lot of such plans and control where we search for these plans. Therefore we add a logic to enforce that we concentrate on good plans and in parallel try very different plans. For VSR we use as Meta-Heuristic an iterative locale search combined with evolutionary concepts like populations, we call it Evolutionary-local-Search. Some details of it are described in the blog about run-time.

For Load Planning we use a Meta-Heuristic too. Here we use a concept similar to Genetic-Algorithms.

Meta-Heuristics often have two important advantages:

• Performance: They find the first solution very fast


• Extensibility: Often the Meta Heuristic works on an object model, which can be enhanced by new features much easier, then linear models of mixed integer approaches.

In the are of Meta-Heuristics there are a lot of Genetic approaches, biological concepts like ant-colonization, physical approaches like simulated annealing and much more. Usually we in SAP development look for new optimizers, which approach of a Meta-Heuristic is common and successful in this area. Then we enhance and adapt it to our scenarios.
Much more important than the concrete type of Meta-Heuristic, are the right operators to construct, manipulate and mix solutions and the right mix of these operators. That needs a lot of work, fine-tuning, experience and real-world-data of our customers.

We have different planning tasks in Transportation Management. What kind of optimizers do we have?
If you look onto TM, you find optimization in the following optimization modules:

• Vehicle Scheduling and Routing (TVSR)
  Planning from Freight Units to Freight-Orders and Bookings

• Proposal (TVRG)
  Find alternatives to transport a Freight unit through the network

• Carrier/Service-Provider selection (TSPS)
  Select Carriers for your Freight orders considering cost, allocations and business-shares

• Strategic Freight Management (TSFM)
  Combine the right bids of your Carriers for balances plans with low costs

• Load Optimization (TVSO)
  Load Pallets into trucks, trailers or containers considering rules like maximal weights or stackabillity.

If and how these services are offered to your TM system, can be checked in the transaction rcc_cust. Here you see the different types of optimization services and how they are connected to different RFC-connection. (If you wonder about the surprising ‘T’s in the acronyms, it is an additional prefix for Services in TM, to avoid clashes with other installations like APO.)


Beside the already mentioned services, there you see two additional entries: The MILP-Entry offers a general Mixed-Integer-Solver. It is not used in standard TM, but can be helpful in customer projects.  The Scheduling Engine has not really to do with optimization: For manual planning you find the connection to the scheduler in this table behind the VSS entry. It is internally re-using functionality of the VSR-optimizer and connected in the same way.

To drill down an additional step you can check the RFC-connection.  There you will find that some of the services use common destinations.  Sometimes different business scenarios are so close togehter, that we use internally the same solution approach, for example Carrier-Selection and Strategic-Freight-Management have an internally the same Mixed-Integer-Formulation.
In other cases the services have different logics, but share such a lot of libraries, that we combine them in one executable, too. For example VSR can also service for the proposal and the manual scheduling.



For a running TM installation you should see the following executables in the connections for the following applications:

vsropsvr.exe	TVSR, TVRG, TVSS
csopsvr.exe	TSPS, TSFM
vsoopsvr.exe	TVSO

It is important not to mix the connections or the executables. This would result in not running applications. Wrong entries in the RFC-connections are one of the most frequent problems, if after an installation or an update one of the applications is not working at all. The transaction rcc_version can help with an overview and has a test for the type integrated in later versions of TM.



That several applications like Carrier Selection and Strategic-Freight-Management point via their RFC-connections to the same executable, has one effect: If you update one, you automatically change both applications. We recommend this behavior, as it avoids you to find the same bug two times. You directly benefit from the corrections and from performance improvements in all applications working on this executable. This is similar to corrections in ABAP-stacks: All calling applications for a function call are effected if you change this function call.

If you – nevertheless - want to change that behavior, you can install the executable in different folders for the different applications. Then you adapt the RFC-Connection to the different destinations. This allows you update complete engines without side-effects to other applications.