The world’s leading publication for data science, AI, and ML professionals.

Capacity Optimization in Freight Trains – Part 1

A Guide to Freight Trains Capacity Optimization in Python

Image by Gabriel Sanchez on Unsplash
Image by Gabriel Sanchez on Unsplash

Railway freight is as complicated as any other form of mass transport. It closely relates to air freight as they both need to optimize on space for efficiency and to minimize the run time. Minimization on the run services is even more crucial when freight trains use the same tracks as passenger trains, particularly in urban setups. Therefore, there is need to run an optimal number of train services between locations as this will:

  1. Save money – Running one service with an optimal number of containers is more economical compared to running more than one service with the same or slightly more number of containers. Manpower on the service route can be reallocated to other areas in need.
  2. Reserved time slices allocation – Allows for allocation of the reserved time slices to other services like passenger trains, more so during peak operation times.

Ideally, the minimization of train services will only be possible if the wagon space usage on available freight services is maximized.

Definitions:

A few terms related to rail freight are defined as follows for a better understanding of the problem at hand:

  1. Locomotive – This is the engine of the train that pulls wagons on a rail track. The length (number of wagons) on a train and their cumulative weights will determine the type of locomotive to be used as they differ in their pulling power.
  2. Wagon – This is the towed trailer that is designed to move along a railway track and in most cases will transport containers. They differ in sizes and nature e.g., flat-top ones where containers can be easily loaded and unloaded.
  3. Containers – These are units used to carry items. Ideally, goods are just fitted in them and moved across locations. There are of different sizes, with 20-foot and 40-foot containers being the most common. A more comprehensive list of sizes can be found here.

Problem Statement:

Is it possible to optimize the capacity of containers on available wagons, all of different sizes on a train service?

Capacity Optimization:

Typically, a train pulls several wagons of different sizes where some are fitted with different sized containers. Therefore, capacity in terms of fitted containers verses the available wagon capacity needs to be maximized. This should result in cost reduction as pertains to loading, unloading and other general operation costs. In addition, the number of trips made based on a set schedule will eventually be reduced.

I’ll illustrate an example of how this Optimization process can be achieved based on the available containers vis-à-vis available wagon capacity in rail freight using multiple knapsacks.

Knapsack Problem:

The knapsack problem can be best illustrated with an example in the shopping domain. Suppose you go to your local supermarket, and you are randomly selected to pick as many items as possible from the shelves and put in your shopping bag. The shopping bag has a maximum capacity. Conditions to be part of the process are as follows:

  1. You can only pick a whole item. Therefore, an item cannot be split in any way.
  2. You’ll stop picking items once your shopping bag is full.

The ideal/optimal option here is to consider the size and value of the items being picked. For example, picking more jewelry compared to cups will be a better choice. Following this optimal process will likely result in a shopping bag (knapsack) with many and more valuable items. This optimization process can be applied across diverse business problems as elicited in this article.

Wagons as Multiple Knapsacks:

The knapsack problem can be replicated in optimizing capacity in trains. Ideally, each wagon is a bin that differs in size on the train service. Optimality will be achieved when the maximum number of containers are fitted on the available wagons. Therefore, each wagon will be a knapsack that has to fit the maximum number of containers, proportionate to the wagon capacity.

Data:

Data in this experiment involved the following parameters:

a) Weights/size/slot count – A vector ( a list with one dimension i.e. row of data) with weights of containers. Here, slot counts for each container will be assumed to be the weight. For example, a 40-foot container occupies four slots on a wagon.

b) Values – This is a vector with values of individual containers. These values attach importance to each container. Therefore, the length of this vector should the same as that of the weights/size. For example, we can assume that containers most needed at the destination are of higher value. Alternatively, 40-foot containers may be assumed to be of more importance than 20-foot containers. In such cases, they’ll have a higher value.

c) Capacity – A vector containing the capacities of the wagons. The wagons are multiple knapsacks in this instance. Therefore, each wagon’s capacity (slot count) must be represented in the vector.

The code below is a representation of how the above data points were generated and represented. Values in the data are the same. This means that all containers are of the same importance.

To solve this as a Mixed Integer Programming (MIP) problem the below steps must be fulfilled:

  1. Import the linear solver wrapper,
  2. Declare the MIP solver,
  3. Define variables,
  4. Define constraints,
  5. Define the objective,
  6. Call the MIP solver and
  7. Display the solution

  1. Import and Declare Linear Solver:

The code below defines the MIP solver for this problem using Google’s OR-Tools. The Solving Constraint Integer Programs (SCIP) backend is used. OR-Tools ** are an open source software for _combinatorial optimizatio_n, which seeks to find the best solution to a problem out of a very large set of possible solutions. The command $Python -m pip install – upgrade – user ortool**s will install OR-Tools for Python. This can be run inside an activated environment. You’ll then be able to run the code below to import and declare the linear solver.

2. Definition of Variables:

The following code creates the variables for this problem.

i is the container and j the wagon(individual knapsack). Therefore, the value of x[(i,j)] is 1 if container i is placed on wagon j. If not, then the value will be 0.

3. Define Constraints:

For this problem, constraints are as below:-

  1. Each container can be placed wholly to at most one wagon. To define this, the sum of x[i][j] over all wagons j has to be less than or equal to 1.
  2. The total wagon capacity cannot exceed the wagon limit. This means that the weights (slot counts) for the containers cannot exceed the slot count of the wagon. For example, a 60-foot wagon has 6 slots. It can therefore carry a 40-foot (4 slots) and 20-foot(2 slots), or three 20-foot, or one 20-foot, or one 40-foot container. Total container slot count cannot exceed the wagons.

The code to define the constraints is as follows:-

4. Define the Objective:

The objective function for this optimization problem, is maximizing the total value of the loaded containers. This is based on the slot count/weight and value of each containers as defined in the code below:

In addition, the value of a container is applied only when the container is placed on a wagon. Otherwise, it does not contribute to the objective which is set to maximize the total value of containers fitted on each wagon.

5. Call the MIP solver and Display the Solution

For each wagon, container numbers as well as their total weight and value will be output. Overall, the total value and weight of every container is also displayed. The output is generated in the code below:

The complete program incorporating the code snippets above is as follows :

The optimized placement of containers on the 13 wagons is below:

Conclusion:

The output in the above code is a guide on the maximization of available space on wagons by factoring the value and weight of containers to be placed on the wagons. In this example, the value was the same for all containers regardless of their sizes. This may not be the exact situation in a commercial setup. For example, an importance value for each container can be based on the urgency of the container to get to the destination etc. In part 2 of the article, I’ll incorporate real data from train plans for one rail company to see how close this optimization process can help in getting as many containers as possible to wagons between locations. Stay tuned.


Related Articles