METHODOLOGY RECOMMENDATION FOR ONE‐CRITERION TRANSPORTATION PROBLEMS: CAKMAK METHOD

<jats:p>Transportation problems (TP) are one of the most prominent fields of application of the mathematical disciplines to optimization and operations research. In general, there are three starting basic feasible solution methods: Northwest Corner, Least Cost Method, VAM – Vogel's Approximation Method. The three methods differ in the quality of the starting basic solution. In this study, we actually show a new method for starting basic feasible solution to one‐criterion‐transportation problems: Çakmak Method. This method can be used for balanced or unbalanced one-criterion transportation problems, and gives the basic feasible optimum solution accordingly.</jats:p>

section_content: Transportation problems(TP) are not only historically one of the most prominent fields of application of the mathematical disciplines to optimization and operations research [1, 2]. A transportation problem basically deals with the problem, which aims to find the best way to fulfill the demand of n demand points using the capacities of m supply points. While trying to find the best way, generally, a variable cost of transporting the product from source (supply) to destination (demand) point or a similar constraint should be taken into consideration. Finding Basic Feasible Solution to Transportation Problem is unlike other Linear Programming problems, a balanced TP with m supply points and n demand points is easier to solve, although it has m + n equality constraints. The reason for that is, if a set of decision variables (x ij 's) satisfy all but one constraint, the values for x ij 's will satisfy that remaining constraint automatically.
section_name: Introduction

section_content: Transportation models deal with the determination of a minimum-cost plan for transporting a commodity from a number of sources to a number of destinations. To be more specific, let there be m sources (or origins) that produce the commodity and n destinations (or sinks) that demand the commodity (Fig). At the i-th source, i = 1; 2; …, m, there are si units of the commodity available. The demand at the j-th destination, j = 1; 2; …, n, is denoted by dj. The cost of transporting one unit of the commodity from the i-th source to the j-th destination is c ij. 

Let X ij be the numbers of the commodities that are being transported from the i-th source to the j-th destination. Our problem is to determine those X ij that will minimize the overall transportation cost. An optimal solution X ij to the problem is called a transportation plan. 

A general transportation problem can be defined as:

This model deals with the determination of a minimum-cost plan for transporting a single commodity from a number of sources to a number of destinations. The model can be modified to account for multiple commodities. The data of the model include: level of supply at each source, the demand at each destination, the unit cost of transporting the commodity from each source to each destination. Since there is only one commodity, a destination can receive its demand from one or more sources. The objective of the model is to determine that the total transportation cost is minimized. When total supply and demand are equal, the formulation is called a balanced model. Also in applications total supply and demand could not be equal and this kind of formulation is called an unbalanced model. In this study we use an unbalanced model as an example. In literature, three kinds of optimization technique are generally used. 

The three methods differ in the quality of the starting basic solution they produce, in the sense that a better starting solution yields a smaller objective value. In general, the Vogel method yields the best starting basic solution, and the Northwest corner method yields the worst. The trade off is that the Northwest corner method involves the least computations [3]. and repeat again until all demand and supply are allocated.
section_name: Transportation models

section_name: Northwest corner

section_content: (a) Allocate as much as possible to the cell with the lowest cost. 

(b) Adjust row and column totals as above. 

(c) From the remaining cells whose column has some free demand and whose row has some free supply select the one with the lowest cost. (d) Repeat again until all has been allocated.
section_name: Least cost method

section_content: This method attempts to identify the greatest advantage of a cell over the next best cell in its row or column. The basic steps are: (a) Calculate a penalty for each row and column by subtracting the smallest cost element in the row or column from the next smallest cost for the same row or column. (b) Identify the row or column with the greatest penalty. Allocate as much as possible to the cell with the least cost in this row or column. Adjust the free demand and supply totals and cross out the row or column whose demand or supply is entirely used up. If both the row and the column have no supply or demand left, only cross out one. (c) If all columns and rows have been satisfied then we have an initial solution. Otherwise recalculate the penalties for uncrossed out rows and columns without counting rows and columns with zero free demand or supply. VAM method does not give the optimum solution generally but, two scientists gave and application example by using VAM within Total Opportunity Cost (TOM) experimental analysis and they solved 128 out of 640 instances. They exhibited that VAM -TOC application provides on average a very nearly optimal solution [4].
section_name: Vogel's approximation method (VAM)

section_content: This method can be used for balanced or unbalanced one-criterion transportation problems, and gives the basic feasible optimum solution accordingly. It has 4 basic steps, and we explain all steps on an example of transportation problem tableau. 

Example: this is an unbalanced transportation problem. We add a dummy column for making demand and supply quantities equal. S i and D i can be defined as tons, and c ij can be defined as USD. The formulation of Çakmak method can be written as follows:

. Account Y ij variables.
section_name: New methodology (Çakmak method)

section_name: STEP 1.

section_content: [ ] This new tableau has been organized by Y ij values and we use them to enter the demand -supply variable needed. First we search the minimum variable in the tableau. As we can see, it is -9,4 variable, its demand is 100 tons and supply for this row is 450 tons. We load this cell, X 23 only with 100 tons as the demand needed. If there are two same Y ij variables in the same row or column, we choose the maximum demanded cell first. After fully loading of commodity in the cell, we cross out the row or column that had been loaded. 

Then we will choose the cell with the minimum negative Y ij value from the cells that do not lie in a crossed-out row or column and we will repeat the procedure. After we cross-out all the rows and columns, we account the total cost finally.
section_name: Account the mn

section_content: Account total cost. This solution gives the optimum value.
section_name: STEP 4.

section_content: In this study, we actually show a new method for one-criterion transportation problems: Çakmak Method finds the optimum solution accordingly the Northwest, VAM and Minimum Cost Method. This method can be used for balanced or unbalanced one-criterion transportation problems, and gives the basic feasible optimum solution accordingly. 

Çakmak Method includes the minimum cost selecting among the different paths of supply and demand by using the determination of biggest demand and supply interaction in tableau, and the minimum cost among the all costs and also among the rows and columns that are interacted between each other in the tableau. Thus, we can find the convenient solution to the problem. We solved many transportation problems by this method and we found approximately 90 % optimal solutions, and others were the most approximate to the optimum solution.
section_name: Conclusions

section_content: We recommend this methot for one-criterion TP and this work can be expanded for the multi-criteria TP in the next studies.