In previous few articles (beginner, intermediate and queuing theory), we have completed a variety of case studies used in operation analytics. One of which was based on assignment algorithm in call centers. Today’s case study will be similar but we will now look at a more broader level instead of individual caller assignment. We will formulate this problem in a similar fashion as we try a transportation algorithm. While solving this problem, we will try multiple well known solutions to the transportation problem.

### Case study

You own a call center with 1000 resources. Each of these resources have gone through a different set of trainings. These training combinations are A,B,C,D,E and F. For instance set A is the population who have gone through training 1,2,3,4,5 and 6. Similarly, set B has gone through some other set of trainings. The distribution of these callers are

A : 200

B : 200

C : 100

D : 100

E : 250

F : 150

Also, the calls you get on a daily basis have different types of queries. This can again be classified into 4 categories. Let’s call them X,Y,Z and W. Each of these category can be identified through an IVR and you can try to allot any caller to these customers. On a daily basis you get following distribution of calls :

X : 20%

Y : 30%

Z : 15%

W : 35%

The number of calls might vary with days but remains almost constant at this ratio. With every set of trainings, you get a different type of skill set which enables a caller to resolve varied type of calls in different time. For instance, a set A agent can resolve a call X in 10 minutes. Following is a grid, which you can refer to check the resolution time for each combination :

Here is the catch! Your objective is to complete the work of all the callers in the least aggregate time. This will allow you to train them on different skills and therefore decrease the resolution time dynamically. Ultimately, you want a dynamic system which can do such an allocation on real time. However, for now you need to make the assignment so that you minimize the total time taken by all callers combined.

### Kick Start the process

As of now, the problem is open ended till you assume the actual inflow of calls to a certain number. To simplify things, let’s assume that we have a balanced transportation problem in hand. Following is the distribution of calls :

X : 200 calls

Y : 300 calls

Z : 150 calls

W : 350 calls

Total calls : 1000 calls

Hence, the number of agents and calls are exactly equal. Even if the total number of calls increase, our current solution will still be valid as the ratio holds true.

### Introduction to transportation problem

This is a classic transportation problem where the time is just a substitute of cost. Here, we try to minimize the total cost by making the right set of assignments. We can either solve it through a simplex or a tabular solution. Transportation problems are generally solved in two steps :

- Identifying a basic feasible solution
- Finding the optimal solution

For this article, my focus will be to complete the first step. I will leave the second step for the reader and based on the response on this article, will publish the second part as well if required.

Identifying a basic feasible solution can be done through 3 approaches :

- North west corner rule (simplest of all)
- Minimum cost method
- Penalty cost method

### North west corner rule

The process is very simple. We just assign the maximum possible values on the north west corner till we exhaust all the callers. We start as follows :

Here we were able to make this assignment because both supply and demand is 200. However, we make an assignment of a value which is the minimum of two, which coincidentally is the same here. Now we have exhausted both the first row and first column. Hence we move to the cell (B,Y) and make the next assignment. Sequentially we make all the possible assignments.

Now we calculate the total time which in this case comes out as 7550 minutes. To simply evaluate the results , we assign all A’s for X type of calls. We will divert around 33% of Y type calls to C type agents and 66% to B type agents & so on. This is generally the least optimal solution and we can get better results by the rest two methods.

### Minimum cost method

This method is slightly evolved version of the last one. Here we simply try finding out the smallest time which for a combination of caller-customer that are available. For instance, if we look at the entire cost matrix, we find the minimum time is for X customer being attended for caller D, hence we make the maximum assignment at this combination.

Finally we arrive at the following assignments :

The total time for this assignment now reduces to 3900 minutes which is almost a 50% reduction on the overall time.

### Penalty cost method

This is an even more evolved version of initial assignment procedure. Here we start with calculating the difference between the minimum and the 2nd minimum time for each row and column. This is basically the cost of not making an assignment in the current iteration. Following is our penalty cost table :

As we see the penalty cost is maximum for the caller types D. And we need to immediately assign the maximum value to caller D. Once done, we again recalculate all the penalty costs and move on with the assignment. Finally, following are the assignments

The total cost here is 4400, which is not better the last method. However, there is no guarantee of which algorithm wins in any iteration. It completely depends on the chances you break the tie in favor of lowering the cost or in opposite direction.

### Thinkpot

Beyond this step, we now start our journey of optimization. This can again be done by multiple algorithms, namely – Stepping stone, MODI etc. However, you can progress on the simplex optimization to get the final solution. Once you have the final solution to this problem, mention the methodology and the final answer in the comment box below.

### End Notes

Transportation problem is used widely in operation research but very rarely used in analytics industry. However, I have seen enormous number of opportunities which can be converted into such transportation problems. My motive of this article was to make you realize that how powerful these operation research tools can be, if we convert our problem in hand into such objective functions. Also do mention in the comment box below, if you would like me to further kill the problem of optimizing such transportation problem with the algorithms I have mentioned above.

Did you like reading this article ? Do share your experience / suggestions in the comments section below. I’d love to know your

Hi Tavish – As usual great article. Any plans of covering a case study around IIoT? Something around Predictive Based Maintenance of industrial equipment & predicting Remaining Useful Life of assets or anything around that? Would be great if you can cover a case study in that area.

Hi Anupam,

Great ideas. Will keep the topics in mind.

Thanks,

Tavish

3750 with Excel solver

My answer is same as yours 🙂

Please provide suitable example with R and algorithm that will be applied.

Hi Srivastava,

This is an interesting case study, I used Simplex method in Solver with an objective to minimize the cost (or time in this case). The total time for the assignment reduced to 3750. The results were as below:

A B C D E F

X 100 100

Y 200 50 50

Z 50 100

W 150 0 200 0

Hi Sridhar,

You are spot on!

Tavish

The output was not structured properly in my previous comment making it unreadable., Apologies.,. Here is the output that I got

X assigned to B: 100

X assigned to C: 100

Y assigned to A: 200

Y assigned to B: 100

Z assigned to F: 150

W assigned to D: 100

W assigned to E: 250

Has anyone used ‘lpSolve’ package in R to solve these type of problems? Eager to connect and discuss about it…

I’m currently working on a cost optimization problem and running into issues with excel solver because of its limitations with the number of variable cells and constraints.

3750….with Simplex Method

Correcto

Great example

I tried some optimal solution using MODI looks like i am reaching there. Will post the results soon

Great post and what tool do you think is best for a hosted OR max/min Optimization problem?

R or even excel is ok for learning, but a commercial grade hosted solution is a different use case.

Thanks!

Great article. Very useful insight. Thank you.

I did integer optimisation. The result is 8155. it is nowhere near your results.

I am eager to know your allotment. Please share your detailed results.

Here is the proposed linear programming model and I’m solving it right now with GAMS just give me a couple of minutes. https://www.dropbox.com/s/yfkxhjgup2x5bpn/Solution.JPG?dl=0

Got a minimum value of 3750 by integer optimization.

Ok, here’s the proposed linear programming model and the optimal solution provided by GAMS in 0.02 seconds of resolution time: https://www.dropbox.com/s/fvv8jk7xgx2rghh/Solution.JPG?dl=0

Here’s the GAMS code:

option optcr=0;

set

i /1*6/

j /1*4/;

free variable z;

table c(i,j)

1 2 3 4

1 10 8 2 3

2 11 4 11 12

3 10 9 4 7

4 1 12 11 14

5 12 7 6 4

6 5 5 11 11

;

positive variables

x(i,j);

parameter

b(j)

/

1 200

2 300

3 150

4 350

/

a(i)

/

1 200

2 200

3 100

4 100

5 250

6 150

/

equations

fo

r1(j)

r2(i)

;

fo..z=e=sum((i,j),c(i,j)*x(i,j));

r1(j)..sum((i),x(i,j))=e=b(j);

r2(i)..sum((j),x(i,j))=e=a(i);

model analyticsvidhya /all/;

solve analyticsvidhya using lp minimizing z;

At a minimum of 3750 total minutes 😀

Milo,

I second you on the answer,

T

Hi Tavish,

-11 is what i got as a solution , but haven’t plotted a loop to draw a new optimal solution. Is the right direction i am going ?

I user MODI method i.e. uv method.

I used i meant*

My objective solution was 3775 by integer optimization.

Hi,

I think you can do better allotment. You can try a few optimization algorithm, you should reach till 3750.

I got 3750…..by using Simplex Method

Great. 3750 is indeed the most optimum solution.

Very interesting approach to analytical problems, Awaiting part 2. Can you also share how to code it in SAS or some code snippet if you have.

Here’s the proposed linear programming model and optimal solution: https://www.dropbox.com/s/fvv8jk7xgx2rghh/Solution.JPG?dl=0.

With a minimum total time of 3750 minutes. Modeled and solved in GAMS.

Solving it through Excel solver , answer is 3750 min and allotment will be as follows :

X: 100 to D

X: 100 to F

Y: 200 to B

Y:200 to F

Z: 100 to A

Z: 50 to C

W: 100 to A

W:250 to E

Hope this is the right allotment

Informative article. Simplex solver produced 3750. Would like to know about Stepping stone, MODI .

After a long time I find an application of Transportation problem in Data Analytics. Problem formulation is more critical. Appreciate you example of call center optimization through transportation problem solving technique. Even simpler Assignment problem solving techniques is an useful tool. I had worked on the sensitivity analysis of an assignment problem. Thanks for sharing the problem which brings me back to 35 years when I had learn OR.