An Effective Approach for Solving Multi-objective Transportation Problem
Lakhveer Kaur1, Sukhveer Singh2,*, Ashok Singh Bhandari3, Sandeep Singh4 and Mangey Ram5
1Govind National College, Narangwal, Ludhiana, India
2Department of Mathematics, Graphic Era Hill University, Dehradun, India
3Department of Mathematics, Shri Guru Ram Rai University, Dehradun
4Akal University, Talwandi Saboo, Punjab, India
5Department of Mathematics and Computer Science Engineering, Graphic Era Deemed to be University, Dehradun, India
E-mail: Sangha.1987.lk@gmail.com; sukhveer.singh@thapar.edu; bhandariashoksingh@gmail.com; sandeep.singh@thapar.edu; mangeyram@gmail.com
*Corresponding Author
Received 23 March 2023; Accepted 21 September 2023; Publication 27 November 2023
In this present study, a transportation problem is considered such that the total cost and time of transportation are minimized without taking into account their priorities. In literature, there are less techniques available for finding the efficient solutions of multi-objective transportation problem. So, we developed a heuristic algorithm to find most efficient solution of multi-objective transportation problem, which gives efficient solution with minimum difference from ideal solution. Firstly, we aim at formulating a multi-objective transportation problems along with a novel algorithm to find efficient solutions. The proposed algorithm gives optimal solution faster in comparison to other available techniques in literature for the given multi-objective transportation problem. Moreover, it avoids the degeneracy as well as requires low computational effort. Furthermore, an illustrative example is provided to show the feasibility and applicability of the proposed approach and compare the results with the existing approaches to show the effectiveness of it.
Keywords: Efficient solution, ideal solution, multi-objective transportation problem, simple heuristic.
Practical applications give rise to a large class of mathematical programming problems frequently. For instance, a product may be transported from factories (sources) to retail stores (destinations). One must know the amount of the product available as well as the demand of the product. So, the difficulty is that the different ways of the network joining the sources to the destinations have different costs linked with them. Therefore, we aim at calculating the minimum cost routing of products from point of supply to point of destination and this problem is named as cost minimizing Transport Problems. Generally, the classical transportation problems are associated with single objective, which can be transportation cost or time and are developed by Hitchcock (1941) and Koopmans (1947). But competition between organizations is increasing day to day very quickly. So it is not sufficient to achive only one objective at time, when transportation of goods from organizations is made. Therefore it is necessary to proceed with multi-objectives simultaneously so that firms can get maximum profit. Many researchers have developed efficient techniques for solving two or more objectives simultaneously, which are by Lee et al. (1973), Zeleny (1974), Diaz (1978; 1979), Isermann (1979), Aneja et al. (1979), Gupta et al. (1983), Ringuest et al. (1987), Reeves et al. (1985), Kasana et al. (2000), Chang (2007; 2008), Bai et al. (2011), Pandian et al. (2011), Quddoos et al. (2013a) and Nomani et al. (2017) etc. All techniques developed by these researchers are very difficult to apply and more time consuming.
In literature, we find that there are many transportation models where linear programming has been applied or approaches to solve multi-objective transportation problems. From this idea, Chanas (1984) developed multi-objective linear programming by using parametric approach. Further, Zimmerman (1978) makes use of intersection of all constraints and goals by proposing a multi-criteria decision making (MCDM) set and multi-objective linear programming problems that taking all parameters, along with a triangular possibility distribution. Prakash (1981) considered linear programming approach to multi criteria decision making where the constraints are of equality type. Also, various authors worked on developing different models for solving multi-objective transportation problems.
In this paper, an novel algorithm has been developed to find optimal value of multi-objective Transportation Problem. The proposed algorithm gives optimal solution faster in comparison to other available techniques in literature for the given Transportation Problems. Moreover, it avoids the degeneracy as well as demands low computational effort.
For sources and destinations , multi-objective transportation problems are represented mathematically as follows:
subject to
where
Quantity of goods transported from source to destination .
Cost of transportation of goods from source to destination of objective.
Availability at source .
Demand at destination .
and are non-negative numbers.
Because of the special structure of the multi-objective transportation model, the problem can also be represented as Table 1.
Table 1 Tabular representation of model ()
Destination | Supply | ||||
Source | () | ||||
Demand () |
Some important basic definitions to proceed with proposed heuristic are given below:
Definition 1. Ringuest et al. (1987) An ideal solution to the multi-objective transportation problem would result in each objective simultaneously realizing its minimum. That is, if = min , then the vector is an ideal solution. When there is a feasible extreme point such that .
Definition 2. The cells, in which allocations are made, called basic cells and rest are called non-basic cell.
Definition 3. Ringuest et al. (1987) A feasible vector yields a non-dominated solution to the multi-objective transportation problem if, and only if, there is no other feasible vector such that , and , for some . When this relationship holds is said to be efficient.
Definition 4. Closed loop is made by drawing only horizontal and vertical lines through basic cells on starting and ending with same non-basic cell.
Definition 5. For the non-basic cells, pointer cost is obtained by adding (for fixed r) of cells with plus sign and subtracting (for fixed r) of cells with negative sign for each closed loop.
Definition 6. The efficient solution which has minimum difference from ideal solution as compare to other efficient solutions is called most efficient solution.
The following steps along with basic definitions given in Section 3 are considered to proceed with proposed heuristic:
Step 1: Represent the given problem into the tabular form as Table 1 and make it balance if it is not balanced by adding (according to requirement) dummy row or column with transportation cost zero.
Step 2: Consider any single objective from given problem and find its optimal solution by Modified Distribution Method Dantzig (1963) and put this solution in MOTP table.
Step 3: Calculate the cost of each objective separately for current solution, which is an efficient solution for MOTP.
Step 4: Make closed loop from each non-basic cell and assign alternatively plus (+) and minus (-) signs in the corner cell of each loop on starting with plus (+) sign from non-basic cell. Then calculate the pointer cost . Calculate , for fixed and , if all then go to step 7 otherwise follow the step 5.
Step 5: Select the non basic cell having most negative and make it basic cell by giving maximum possible allocation and that is the minimum allocation in cell with negative sign on the closed loop of . Adjust the allocations of other cells by adding to allocation of cell with plus sign and subtract from the allocation of cell with negative sign. Then go to step 3.
Step 6: Repeat the processor from step 3 to step 5 until we get all . Then follow the step7.
Step 7: Current solution is most efficient solution for MOTP.
To illustrate the proposed study, we consider the following examples of sugar transportation problem where supplies, and demands are considered. Suppose there are three sugar factories from where the sugar is supplied to three cities . Conveyances with three different capacities are available to be selected for transporting sugar, respectively. There are three examples are considered for the validity of previous defined technique.
In this section, a numerical transportation is considered having three destination and three origins. Considered problem is solved using proposed algorithm for showing more effective application of developed algorithm. Input data of numerical example is shown in Table 2. The first entry of cell (i,j) represent quantity of fuel consumed during transportation of commodities from source i to destination j, second entry of cell (i,j) depict cost of road taxwhile transporting Goods and last entry of cell (i,j) denotes the transit time of transportation from source i to destination j. Last row and column denotes demand of goods at destination and availability of goods at source .
Table 2 Input data for Example 1
Destination | Supply () | |||
Source | ||||
3 2 7 | 147 | 135 | 100 | |
4 5 1 | 267 | 541 | 125 | |
1 3 5 | 617 | 438 | 75 | |
Demand () | 60 | 80 | 160 |
So step wise procedure for considered numerical problem according to the algorithm developed in previous section is given as follows:
Step 1. Make the initial table for MOTP as shown in Table 2.
Step 2. Find the optimal solution of problem by considering first objective on applying modified distribution method. Solution is shown in Table 3.
Table 3 Initial solution for Example 1
Destination | Supply () | |||
Source | ||||
100 | ||||
3 2 7 | 147 | 135 | 100 | |
80 | 45 | |||
4 5 1 | 267 | 541 | 125 | |
60 | 15 | |||
1 3 5 | 617 | 438 | 75 | |
Demand () | 60 | 80 | 160 |
Step 3. Efficient solution obtained from Table 3 for MOTP is (285, 1185, 1525).
Step 4. Make the closed loop from each non-basic cells in Table 3 and pointer cost is:
Table 4 Solution obtained after making as basic cell.
Destination | Supply () | |||
Source | ||||
100 | ||||
3 2 7 | 147 | -135 | 100 | |
65 | 60 | |||
4 5 1 | 267 | 541 | 125 | |
60 | 15 | |||
-1 3 5 | 6-17 | 438 | 75 | |
Demand () | 60 | 80 | 160 |
Also,
As therefore go to step 5.
Step 5. Make as basic cell by giving maximum possible allocation i.e. 15 and adjust allocations of cells and as 65, 60 and 0 respectively as shown in Table 4 and efficient solution obtained from Table 4 is (360, 1095, 1420).
Step 6. Now again make closed loop from non-basic cells and in Table 4 and pointer cost is:
Also,
As all therefore current solution is most efficient solution.
Input data for three more examples is given in Tables 5 to 7. These examples are solved using proposed method and existing algorithm and data for obtained results is given in Table 8.
In this section, a numerical transportation is considered having three destination and three sources. Considered problem is solved using proposed algorithm for showing more effective application of developed algorithm. Input data of numerical example is shown in Table 5.
Table 5 Input data for Example 2
Destination | Supply () | |||
Source | ||||
6 3 | 55 | 42 | 7 | |
10 8 | 84 | 126 | 5 | |
10 9 | 1110 | 87 | 8 | |
Demand () | 8 | 10 | 2 |
In this section, a numerical transportation is considered having four destination and Three sources. Considered problem is solved using proposed algorithm for showing more effective application of developed algorithm. Input data of numerical example is shown in Table 6.
Table 6 Input data for Example 3
Destination | Supply () | ||||
Source | |||||
1 4 | 2 7 | 73 | 74 | 8 | |
1 5 | 9 8 | 39 | 410 | 19 | |
8 6 | 9 2 | 45 | 61 | 17 | |
Demand () | 11 | 3 | 14 | 16 |
Table 7 Input data for Example 4
Destination | Supply () | |||||
Source | ||||||
9 2 2 | 1294 | 986 | 613 | 946 | 5 | |
7 1 4 | 398 | 794 | 759 | 522 | 4 | |
6 8 5 | 513 | 985 | 143 | 356 | 2 | |
6 2 6 | 889 | 1166 | 293 | 281 | 9 | |
Demand () | 4 | 4 | 6 | 2 | 4 |
In this section, a numerical transportation is considered having five destination and four origins. Considered problem is solved using proposed algorithm for showing more effective application of developed algorithm. Input data of numerical example is shown in Table 7.
In the previous subsection, the mathematical model of the example for different cases is formulated and our methodology to establish the deterministic model for each case is used. The equivalent deterministic forms of the chance constraints. Hence, the deterministic form of the multi-objective transportation problems. The approach is used to tackle the multiple conflicting objectives. The comparison can be show in table and results of previous problems with another existing methods effectively in Table 8.
Table 8 Comparative analysis of solution obtained by proposed heuristic of considered examples
Sr. | Efficient | Most | Ideal | |
No. | Source | Solution | Efficient Solution | Solution |
Ex.1 | Gupta et al. (1983) | (285, 1185, 1525) | (360, 1095, 1420) | (285, 670, 1160) |
(360, 1095, 1420) | ||||
Ex.2 | Bai et al. (2011) | (153, 121) | (153, 119) | (153, 114) |
(153, 119) | ||||
(143, 265) | ||||
Ex.3 | Aneja et al. (1979) | (168, 215) | (176, 175) | (143, 167) |
(176, 175) | ||||
(101, 137, 101) | ||||
(101, 130, 195) | ||||
Ex.4 | Isermann (1979) | (106, 120, 88) | (127, 104, 76) | (101, 72, 64) |
(112, 112, 88) | ||||
(127, 104, 76) |
In this research, a transportation problem has been formulated in multi-objective environment and an novel algorithm is proposed to find efficient solutions with ideal one’s. The values obtained by the proposed algorithm shows that the decision maker has the more flexibility. The proposed algorithm avoids the degeneracy and gives the efficient solution faster than others existing algorithms for the given in the field of transportation problems. It also reduces the computational work. From the comparative study, it has been concluded that the proposed approach is more suitable and practicable, and provide a better way to solve the transportation problems where the existing are unable to find the results. In future, we extend this approach to the other domain. In future, the method can be modified to solve the type of multi objective transportation problems with all the parameters, i.e., availability, demand and unit transportation cost, uncertain.
The authors would like to thank Graphic Era Hill University for providing support for conducting this research work.
Aneja et al. (1979) Aneja, Y. P. and Nair, K. P. K. (1979). Bi-criteria transportation problem.Manag. Sci., Vol. 25, pp. 73–78.
Bai et al. (2011) Bai, G. and Yao, L. (2011). A simple algorithm for multi-objective transportation model. International conference on business management and electronic information. pp. 479-482.
Bander et al. (2015) Bander, A. S.,Morovati, V. and Basirzadeh, H. (2015). A super non-dominated point for multi-objective transportation problems. Application and Applied Mathematics, Vol. 10(1), pp. 544–551.
Chang (2007) Chang, C. T. (2007). Multi-choice goal programming problem. Omega-Int J Manage S., Vol. 35, pp. 389–396.
Chang (2008) Chang, C. T. (2008). Revised multi-choice goal programming. Appl Math Model., Vol. 32, pp. 2587–2595.
Dantzig (1963) Dantzig, G. B. (1963). Linear Programming and Extensions, Princeton University Press, Princeton, N. J.
Diaz (1978) Diaz, J. A. (1978). Solving muliobjective transportation problems. Ekonomicky matematicky obzor, Vol. 14, pp. 267–274.
Diaz (1979) Diaz, J. A. (1979). Finding a complete description of all efficient solution to a multiobjective transportation problems. Ekonomicky matematicky obzor, Vol. 15, pp. 62–73.
Gupta et al. (1983) Gupta, B. and Gupta, R. (1983). Multi-criteria simplex method for a linear multiple objective transportation problem. Indian J. Pure Appl. Math., Vol. 14(2), pp. 222–232.
Hitchcock (1941) Hitchcock FL (1941) The Distribution of a product from several sources to numerous localities. J. Math. Phy. Vol. 20, pp. 224–230.
Isermann (1979) Isermann, H. (1979). The enumeration of all efficient solution for a linear multiple objective transportation problem. Nav. Res. Logist. Q., Vol. 26(1), pp. 123–139.
Kasana et al. (2000) Kasana, H. S. and Kumar, K. D. (2000). An efficient algorithm for multiobjective transportation problems. Asia pacific Journal of Operational Research, Vol. 7(1), pp. 27–40.
Koopmans (1947) Koopmans, T. C. (1947). Optimum utilization of the transportation system. Econometrica, Vol. 17, pp. 3–4.
Lee et al. (1973) Lee, S.M. and Moore, L. J. (1973). Optimizing transportation problems with multiple objectives. AIEE Transactions, Vol. 5, pp. 333–338.
Nomani et al. (2017) Nomani, M. A., Ali, I., Ahmed, A. (2017). A new approach for solving multi-objective transportation problems. International Journal of Management Science and Engineering Management, Vol. 12, pp. 165–173.
Pandian et al. (2011) Pandian, P., Anuradha, D. (2011). A new method for solving bi-objective transportation problem. Aust. J. Basic & Appl. Sci., Vol. 10, pp. 67–74.
Quddoos et al. (2013a) Quddoos, A., Javiad, S. and Khalid, M. M. (2013). A new method to solve bi-objective transportation problem. International journal of applied science, Vol. 26(4), pp. 555–563.
Reeves et al. (1985) Reeves, G. R. and Franz, L. S. (1985). A simplified interactive multiple objective linear programming procedure. Computational and Operations Research, Vol. 12(6), pp. 589–601.
Ringuest et al. (1987) Ringuest, L. and Rinks, D. B. (1987). Interactive solutions for the linear multiobjective transportation problem. Eur. J. Oper. Res., Vol. 32, pp. 96–106.
Zeleny (1974) Zeleny, M. (1974). Linear multiobjective programming. Springer-Verlag, Berlin.
Chanas (1984) S. Chanas, W. Kolodziejckzy and Machaj, “A fuzzy approach to the transportation problem,” Fuzzy Sets and Systems, Vol. 13, pp. 211–221, 1984.
Zimmerman (1978) H. J. Zimmermann, “Fuzzy programming and linear programming with several objective functions”, Fuzzy sets and System, Vol. 1, pp. 45–55, 1978.
Prakash (1981) S. Prakash, “Transportation problem with objectives to minimizes the total cost and duration of transportation”, OPSEARCH, Vol. 18, pp. 235–238, 1981.
Sukhveer Singh, Assistant Professor, Department of Mathematics, Graphic Era Hill University, Dehradun, is an Assistant Professor at Graphic Era Hill University, Dehradun, India. Prior to joining this University, Dr. Singh received a Ph.D. in Applied Mathematics with a specialization in multi-criteria decision-making and soft computing techniques, from Thapar University, Patiala, India in 2020 and a Postdoc in Mathematics from the Indian Institute of Technology, Roorkee, India in 2021. His research interests are in the fields of Computational Intelligence, Multi-criteria decision-making problems, Reliability theory, Optimization techniques, various nature inspired algorithms (e.g. genetic algorithms, swarm optimization), fuzzy and intuitionistic fuzzy set theory, and Expert Systems. Application areas include a wide range of industrial and structural engineering design problems. Singh has authored/co-authored over 12 technical papers published in refereed International Journals.
Lakhveer Kaur, Assistant Professor, Govind National College, Narangwal. Kaur is working as an Assistant Professor at Govind National College, Naranagwal in the Department of Mathematics. Also a member of the board of studies for UG and PG in Panjab University, Chandigarh. The author has done research on the topic “Study on optimization methods associated with different types of transportation problems”.
Sandeep Singh, Associate Professor, Department of Mathematics Akal University, Talwandi Sabo, Bathinda is an Associate Professor with the Department of Mathematics at Akal University Talwandi Sabo, Bathinda, Punjab, India. He received his Ph.D. in Group Theory (Mathematics) from the School of Mathematics, Thapar University, Patiala, India, and his M.Sc. degree in Mathematics from Punjabi University, Patiala, India. He was also a postdoctoral fellow at the Department of Mathematics, Indian Institute of Technology Roorkee under program SERB–NPDF (National Postdoctoral fellowship). His research interests include Group Theory, Automorphism Groups, Number Theory, Sum-set Problems, and Optimization Techniques. Besides holding an excellent academic record throughout, He has cleared the national level examinations NET–JRF conducted by UGC-CSIR, India. Also, he had been a recipient of CSIR junior and senior research fellowships for 2011–2013, and 2013–16 respectively. He has published more than 20 research papers in various journals of international repute and of different publishers like Springer, Taylor Francis, World Scientific, and others.
Ashok Singh Bhandari, Assistant Professor, Department of Mathematics, School of Basic and Applied Sciences, Shri Guru Ram Rai University, Dehradun. Dr. Ashok Singh Bhandari received the B.Sc. and M.Sc. degree in science from Hemwati Nandan Bahuguna Garhwal University, Srinagar, India, in 2013 and 2015, and Ph.D. in Mathematics from Graphic Era (Deemed to be University) Dehradun, India. He is currently working as an Assistant Professor in the Department of Mathematics, School of Basic and Applied Sciences, Shri Guru Ram Rai University, Dehradun, India. He has published research papers in Elsevier, Emerald, inderscience, International Journal of Mathematical, Engineering and Management Sciences, Springer nature, and many other national and international journals of repute and presented his works at national and international conferences. His fields of research are reliability theory and optimization.
Mangey Ram, Graphic Era Deemed to be University, India. Prof. Mangey Ram received the Ph.D. degree major in Mathematics and minor in Computer Science from G. B. Pant University of Agriculture and Technology, Pantnagar, India in 2008. He has been a Faculty Member for around fifteen years and has taught several core courses in pure and applied mathematics at undergraduate, postgraduate, and doctorate levels. He is currently the Research Professor at Graphic Era (Deemed to be University), Dehradun, India. Before joining the Graphic Era, he was a Deputy Manager (Probationary Officer) with Syndicate Bank for a short period. He is Editor-in-Chief of the International Journal of Mathematical, Engineering and Management Sciences; Journal of Reliability and Statistical Studies; Journal of Graphic Era University; Series Editor of six Book Series with Elsevier, CRC Press-A Taylor and Frances Group, WalterDe GruyterPublisher Germany, River Publisher and the Guest Editor and Associate Editor with various journals. He has published 400 plus publications (journal articles,books,book chapters,conference articles) in IEEE, Taylor and Francis, Springer Nature, Elsevier, Emerald, World Scientific and many other national and international journals and conferences. Also, he has published more than 60 books (authored/edited) with international publishers like Elsevier, Springer Nature, CRC Press-A Taylor and Frances Group, WalterDe GruyterPublisher Germany, River Publisher. His fields of research are reliability theory and applied mathematics. Dr. Ram is a Senior Member of the IEEE, the Senior Life Member of the Operational Research Society of India, the Society for Reliability Engineering, Quality and Operations Management in India, Indian Society of Industrial and Applied Mathematics, He has been a member of the organizing committee of a number of international and national conferences, seminars, and workshops. He has been conferred with the “Young Scientist Award” by the Uttarakhand State Council for Science and Technology, Dehradun, in 2009. He has been awarded the “Best Faculty Award” in 2011; the “Research Excellence Award” in 2015; “Outstanding Researcher Award” in 2018 for his significant contribution to academics and research at Graphic Era Deemed to be University, Dehradun, India. Also, he has received the “Excellence in Research of the Year-2021 Award” by the Honourable Chief Minister of Uttarakhand State, India, and the “Emerging Mathematician of Uttarakhand” state award by the Director, Uttarakhand Higher Education. Recently, he received the “Distinguished Service Award-2023” for the subject and nation development by Vijñāna Parishad of India.
Journal of Reliability and Statistical Studies, Vol. 16, Issue 1 (2023), 153–170.
doi: 10.13052/jrss0974-8024.1618
© 2023 River Publishers