Consulting

R e a l-t i m e O p t i m i z a t i o n S y s t e m

An example of a leading edge product in optimization is the complex freight car planning system used by Green Cargo. This is an online system that plans the distribution of empty freight cars. Within seconds after the user places an order, the system lets the them know if there are any cars available to be assigned to the order.

In the first part of the optimization process, the specific cars are not actually assigned to the order. Each station has a specific working schedule of when their trains leave and the cars are to be sent as late as possible. The decision to send cars, and where to send them, has to be made. When this decision is made, certain cars are assigned to the order and the cars are delivered to the customer just before the deadline.

The second part of the optimization, which is run a few times a day, is a more time-consuming process than the first part, where heuristic methods are used. The mathematical models of arcs and nodes are not identical since the node structures are built dynamically in real-time. However, the same logical way of building the models is used in both parts and this results in satisfying solutions to the primary objective, which is to achieve a more effective flow of the empty freight cars.

The entire SJ fleet consists of some 11 000 freight cars and the system minimizes the mileage of all the empty freight cars. An objective of a system of this kind could be to decrease investments made in expensive freight cars or to decrease the amount of cars needed. It could also be to achieve a higher degree of maintenance of the cars. If we consider the main objective of Green Cargo, which is to increase the use of their cars, we can count on a considerable increase in capacity of about 30% using this system. To get a better picture of how much money there is to be saved by investing in a highly advanced optimization system, we may assume that the increase in capacity results in a proportional decrease in the amount of cars needed. This theoretical discussion means that the fleet of freight cars can be cut by 3 300 cars. An ordinary freight car costs about 100 000 USD, which means that we can theoretically save 330 000 000 USD by investing in a leading-edge optimization product. Regardless of what the objective is, this system and optimization techniques are a profitable piece of business.

The entire network of train stations and railroad throughout the country of Sweden is mathematically represented as a network with arcs and nodes in the optimization model, which is the core of this complex system. The problem can be categorized, in terms of operations research, as a "multicommodity minimum cost network flow" problem. The planning horizon is seven days, so the trains' arrival times and other time limitations only exist on a weekly basis in the system. However, since this is a real-time system, all changes that affect the plans in any way, are updated constantly and loaded into the internal representation.

Implementation and Architecture
The system is implemented in Java and consists of 700 classes. CPLEX is used as the optimization engine of the final mixed integer program formulation of the problem. The interaction with CPLEX is implemented in C. Rational Unified Process (RUP) standards have been used throughout the development and Rational Rose has been used as systemization tool. Corba and MQSeries are used for interchange between the different parts of the system. The object database, Objectivity, is used i n order to keep data persistent. This also supports the possibility of running the system in two separate processes, which is an advantage in case of insufficient memory.

In figure 1 we can see the main architecture of the system. All data regarding timetables, cars, orders, users, contracts etc. resides in the IBM Mainframe. The server is loaded with all necessary data from the mainframe. This data is refreshed every night, in order to keep the information consistent. Changes in data that influence the freight car planning are sent to the server constantly throughout the day using the MQSeries connection.

Figure 1. System Architecture

Optimization Model Briefly
When a customer requests a freight transportation at one of the order centers, this order is entered into the mainframe application. The order is sent to the system server, which tries to find a suitable distribution of empty freight cars, so that the customer gets its cars at the required location in time. An order is typically a request for a certain type of car (with possible alternatives), a loading location, a loading time, a destination and a time when the car is unloaded and ready for other assignments. Every time an order is entered in the system a new plan is derived for this specific type of car. Weight and length is reserved in the trains required for the transportation of the empty cars. With respect to all these constraints, we run a sub-optimization routine with these cars. This routine considers all trains in the system, but only a certain kind of cars, i.e. the type of cars that the order represents.

A few times a day a more extensive optimization routine is used, in order to minimize the slack of the first solution. In this optimization, all the cars and trains in the system are considered and a sub-gradient method is used to make the solution even tighter, i.e. to see if it is possible to make smart changes in the reservations, so that more capacity gets available to other orders. It is possible that the immediate answer to the requested amount of cars to an order, is that the cars cannot be sent to the location in time. In these cases, the order is put on a queue and, after a few optimization steps, cars are assigned to the order.

The final formulation of the problem, which is sent to CPLEX, is a mixed integer program (MIP). A great deal of preprocessing is done before we come as far as to send the expressions to CPLEX. Network of nodes and arcs are dynamically built as real-time changes affect the structures. The optimization models are based on networks, which take both time and space into account. The node structure of a station represents a time-expanded network, which is illustrated in figure 2. This network is called a terminal structure and all stations in the system is represented by this dynamic network. All nodes in figure 2 represents the same station. Each node represents a certain time-span and the nodes to the left in the figure represents the current time at the station, and time increases to the right. All events that are relevant can be related to a specific node. These events are, e.g. when a car gets available, when trains depart, or the time and the amount of required cars and when trains arrive. As we can see in the figure, the departing trains and the assets of available cars relate to the upper side of the network and the events, when trains arrive or cars are required, are represented by the lower side of the structure.

Figure 2. Node structure representing a station in time and space

The reason to why the network consists of two sides, is that we want to be able to control the flow of cars, to and from a station. The arcs are directed and it is only possible to send cars the way an arrow is pointing. The arcs within the station, between the upper and the lower side, make it possible to meet the requirements at the same station, so that available cars on the station is not sent away another station. There are many nodes on each side and each time a train arrives to the station a new node is created, i.e. if the time is unique and if a few other criteria are satisfied. The arcs actually represents a possibility to do something, e.g. send cars in a train. When the problem is solved, or optimized, the flow on each arc is calculated. The arcs also have a certain capacity, related to the capacity of the trains. The flow represents empty freight cars and if the flow on an arc is two units, this means that there are two empty cars in stock, or to be used to meet a requirement. The required cars are represented by arcs with a negative cost, since the costs of the model are minimized. To get a good balance in the network, during the planning horizon, a pricing system is used. For example, an arc that represents a car, which has already been assigned to a certain order, has a higher negative cost than an arc representing a car, which has not yet got assigned to its order. This is done to make sure that a car, which is assigned to an order, or customer, is not rerouted to another customer, that has not been promised cars.

System Input
Following data is needed , in order to run the system satisfactorily:

Infrastructure. All stations and terminal areas. Distances between stations. The stations are grouped into aggregated areas.
All possible transportation routes between all stations and the train movements they consist of.
Shunting movements. Schedules for shunting at stations and terminal areas.
Train movements. Schedules for all possible train movements between stations.
Train capacity. Available capacity (meters and tons) in the different train movements.
Car data. All freight cars have a unique Id, location, status. The freight cars are divided into 25 car types. All freight cars of a certain car type are completely substitutable.
Orders. Current status of all orders must be synchronized between the mainframe and the system server.

There are several functions in the system for manipulating and changing data. For example, train capacities can be changed and certain train movements can be marked as not available. Changes in train capacity is also updated automatically when other bookings are made.

System Output
Apart from these two major outputs, there are a large number of reports, statistics etc to aid the planners.

The planned distribution of cars, which gives an answer to if cars can or cannot be assigned to the different needs. This plan is done with the available cars but they are not yet assigned to any specific needs.
The final distribution of cars, which gives information about which car that is assigned to a certain order and a which train it will travel in. The final distribution is updated whenever the specific time, which is when trains leave or is shunted on each station, force us to make a definite decision.