Transportation Problem — Solve using Genetic Algorithm

Quick and simple implementation using Python

Transportation problem (TP) is one of the most popular problems in Operations. However, people from other areas have also shown interest to learn the formulation and solution techniques for TP. It is because it can be related to a wide variety of problems and thus acts as a stepping stone for model development.

This article is structured into three segments:

• Introduction to Transportation Problem
• Genetic Algorithm and its Operators
• Implementing Genetic Algorithm to Transportation Problem

1.0 Introduction to Transportation Problem

Transportation Problem is a combinatorial problem that deals with transporting items from multiple sources to multiple destinations at minimum cost. The transportation problem is formulated as a Mixed-Integer Programming (MIP) problem where the objective function is minimization.

The mathematical formulation of the Transportation Problem is given below,

where,

• c is the cost to travel from source i to destination j
• x is a binary variable that connects source i to destination j

As seen above, equation (1) is the objective function that tries to minimize the total cost of transporting from sources i to destination j, equation (2) and (3) restricts transportation from each node to only one destination and vice-versa. It can be observed that items can be transported from one or more sources to one or more destinations by modifying equations (2–3). However, it is not in the scope of this article. And finally, equation (4) is the binary constraints.

Numerical Illustration: Using Exhaustive or Brute Force Search

Consider a Transportation Problem with 3 sources — A, B, C, and 3 destinations — D, E, F. An Exhaustive Search or Brute Force Search technique to solve the Transportation Problem comprises of three 3 simple steps,

• Step 1: Find all possible source-destination combinations — (AD, BE, CF), (AD, BF, CE), (AE, BD, CF), (AE, BF, CD), (AF, BD, CE) and (AF, BE, CD)
• Step 2: Calculate the cost of each combination. Assume $23, $56, $12, $53, $18, and $54 to be the transportation cost for the above combinations respectively
• Step 3: Select a combination with the minimum cost as the optimal solution which is (AE, BD, CF) with transportation cost = $12.

The Need for Heuristics/Meta-Heuristics

Solving small scale Transportation problems is quite simple and fast as seen above. However, with an increase in the number of sources and destinations, the Transportation Problem becomes computationally difficult to solve within a reasonable amount of time. It is due to an exponential increase in source-destination combination. Therefore, a heuristic/meta-heuristics technique such as a Genetic Algorithm can be used to obtain the optimal solution in lesser time.

2.0 Genetic Algorithm and its Operators

Genetic Algorithm (GA) is one of the most popular Evolutionary Algorithms used by people from academia and industry. It comprises of three operators: selection, crossover & mutation. Many literatures on this subject can be found on Google Scholar.

2.1. Key Components of the Genetic Algorithm:

• Chromosome: A combination of 0–1 for the binary variable (x)
• Population: A set of chromosomes
• Parents: Present set of chromosomes
• Children: Set of chromosome derived from Parents
• Fitness: The objective function value of a chromosome

2.2 Genetic Algorithm Operators:

In this article, the primary focus is simply implementing GA with the following operators: Random Selection Operator, Single Point Crossover Operator, and Shift Mutation Operator.

2.2.1 Random Selection: The chromosomes from the population are selected in a random fashion to form children. The algorithm of random selection is quite simple and easy to implement. The python code of the Random Selection operator is provided below.

It should be noted that the selection of chromosomes may be sub-optimal. To this end, other selection operators such as Tournament Selection, Roulette Wheel selection, etc can be used as well.

2.2.2 Single Point Crossover: In a single-point crossover, a crossover point is randomly generated which determines the point for the exchange of information between parents to form children. The python code of single point crossover operator is provided below.

For example, when the crossover point generated is 2, all information from index 3 onwards are exchanged between the two parents to form children, as described here.

2.2.3 Shift Mutation: The chromosome from the population is modified by using either the left or right shift. The number of positions a chromosome shift is generated randomly. The python code of shift mutation operator is provided below.

Using mutation, GA can escape local optima (i.e. stagnation) and explore solution space more efficiently. However, the mutation rate needs to low, which otherwise makes GA behave like a random search.

3.0 Implementing Genetic Algorithm to Transportation Problem

To execute the Genetic Algorithm, an initial population is generated as an initial feasible solution, which is encoded and decoded based on the problem. These solutions are improved to obtain an optimal solution iteratively. Next, a brief overview of population initialization, encoding, and the fitness function is given, followed by the main program.

• Initialize Population: The population of chromosomes is generated randomly with range[0, 1] with N rows and C columns, where M is the number of chromosomes and C is the length of chromosome/number of source or destination nodes.
• Encoding Chromosome: Fractional numbers are ranked starting from 0. Therefore, an array [0.47, 0.99, 0.88, 0.18, 0.85] is modified to [1, 4, 3, 0, 2].

Fitness of a Chromosome: The performance of a chromosome in a population is measured by computing the objective function value, i.e. summing the product of cost (c) and binary matrix (x).

The main program of the Genetic Algorithm given below integrates all operators and functions discussed above. To obtain an optimal solution, pass the transportation cost matrix as an argument.

The output from the program:

Finally, You made it to the end!

First of all, thank you for going through the entire article. I know it isn’t easy to follow such a long article. I wish that I could have written it short, but that would defeat the purpose of learning. The complete code in python is available here.

So, from this article, you know how to implement the Genetic Algorithm to a Transportation Problem in a simple manner. And now you can experiment and modify the Genetic Algorithm operators or use Genetic Algorithm to solve other combinatorial problems.

Please note, there are few other ways to apply the Genetic Algorithm to a Transportation Problem. In fact, everyone has their own way of implementing. So, expand the search and try to implement it with the help of a problem.