Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems

Oshan Niluminda; Uthpala Ekanayake

doi:doi:10.11648/j.ajtte.20230806.12

Research Article |

| Peer-Reviewed

Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems

Oshan Niluminda^*, Uthpala Ekanayake

Published in American Journal of Traffic and Transportation Engineering (Volume 8, Issue 6)

Received: 5 October 2023 Accepted: 23 October 2023 Published: 11 November 2023

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

Transportation is one of the various worldwide challenges that organizations must tackle. The Transportation Problem (TP) is also an important topic in the subject of optimization, where the aim is to reduce the overall transportation cost of distributing from a particular number of sources to a specific number of destinations (locations). This paper aims to investigate the most effective way to solve the Transportation Problem (TP) using the line (edge) colouring of a bipartite network. To solve the TP, several solutions have been proposed in the literature. The Initial Basic Feasible Solution (IBFS) and the Optimal Solution are the two solutions of TP. The North-West Corner Method (NWCM), the Lowest Cost Method (LCM), Row Minima Method (RMM), Column Minima Method (CMM), and Vogel's Approximation Method (VAM) may be used to find an IBFS, while the Modified Distribution (MODI) Method and the Stepping Stone Method can be used to find an optimal solution for the TP In this paper, propose a new algorithmic technique that utilizes the line (edge) colouring of a bipartite network to obtain an optimal or nearly optimal solution to the TP. The proposed technique is applied to balanced and unbalanced TP and compared to other existing methods. Experimental results show that the line (edge) colouring algorithm requires fewer iterations to achieve optimality compared to other current methodologies. In conclusion, the line (edge) colouring algorithm is a highly effective method for solving TP. By representing the TP as a bipartite network and using the proposed algorithmic technique, the optimum or nearly optimum TP solution can be obtained quickly and efficiently. This approach has significant potential for optimizing transportation logistics in various industries.

Published in	American Journal of Traffic and Transportation Engineering (Volume 8, Issue 6)
DOI	10.11648/j.ajtte.20230806.12
Page(s)	135-144
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Column Minima Method, Graph Colouring, Modified Distribution, Optimization, Transportation Problem

References

[1]	Adhikari, P., & Thapa, G. B. (2014). A Note on Feasibility and Optimality of Transportation Problem. Journal of the Institute of Engineering, 10(1), 59–68. https://doi.org/10.3126/jie.v10i1.10879
[2]	Afwat, M., Salama, A. A. M., & Farouk, N. (2018). A New Efficient Approach to Solve Multi-Objective Transportation Problem in the Fuzzy Environment (Product approach). International Journal of Applied Engineering Research, 13, 13660–13664. http://www.ripublication.com
[3]	Ahmed, M. M., Khan, A. R., Uddin, M. S., & Ahmed, F. (2016). A New Approach to Solve Transportation Problems. Open Journal of Optimization, 05 (01), 22–30. https://doi.org/10.4236/ojop.2016.51003
[4]	Charnes, A., & Cooper, W. W., (1954). The Stepping Stone Method of Explaining Linear Programming Calculations in Transportation Problems. Management Science, 1 (1), 49-69. https://www.jstor.org/stable/2627075
[5]	Edward S. A., (2012). Improved zero point method (IZPM) for transportation problems. Applied Mathematical Sciences, 6 (109–112), 5421–5426.
[6]	Ekanayake, E. M. U. S. B., Perera, S. P. C., Daundasekara W. B., & Juman, Z. A. M. S., (2021). An Effective Alternative New Approach in Solving Transportation Problems. American Journal of Electrical and Computer Engineering, 5 (1), 1. https://doi.org/10.11648/j.ajece.20210501.11
[7]	Ekanayake, E. M. D. B., & Ekanayake, E. M. U. S. B. (2022). Performance of the Best Solution for The Prohibited Route Transportation Problem by An Improved Vogel’s Approximation Method. Indonesian Journal of Applied Research (IJAR), 3 (3), 190–206. https://doi.org/10.30997/ijar.v3i3.241
[8]	Ekanayake, E. M. D. B., & Ekanayake, E. M. U. S. B. (2022). A Novel Approach Algorithm for Determining the Initial Basic Feasible Solution for Transportation Problems. Indonesian Journal of Innovation and Applied Sciences (IJIAS), 2(3), 234–246. https://doi.org/10.47540/ijias.v2i3.529
[9]	Ekanayake, E. M. U. S. B., Daundasekara, W. B., & Perera, S. P. C. (2022). An Examination of Different Types of Transportation Problems and Mathematical Models. American Journal of Mathematical and Computer Modelling, 7 (3), 37. https://doi.org/10.11648/J.AJMCM.20220703.11
[10]	Ekanayake, E. M. U. S. B. (2022). An Improved Ant Colony Algorithm to Solve Prohibited Transportation Problems. International Journal of Applied Mathematics and Theoretical Physics, 8 (2), 43-51. https://doi.org/10.11648/J.IJAMTP.20220802.12
[11]	Ekanayake, E. M. U. S. B., Daundasekara, W. B., & Perera, S. P. C. (2021). Solution of a Transportation Problem using Bipartite Graph. Global Journals, 21 (1).
[12]	Ekanayake, E. M. U. S. B., Daundasekara, W. B., & Perera, S. P. C. (2022). New Approach to Obtain the Maximum Flow in a Network and Optimal Solution for the Transportation Problems. Modern Applied Science, 16 (1), 30-48. https://doi.org/10.5539/mas.v16n1p30
[13]	Ekanayake, E. M. U. S. B., Perera, S. P. C., Daundasekara, W. B., & Juman, Z. A. M. S. (2020). A Modified Ant Colony Optimization Algorithm for Solving a Transportation Problem. Journal of Advances in Mathematics and Computer Science, 35 (5), 83–101. https://doi.org/10.9734/jamcs/2020/v35i530284
[14]	Geetha, T., & Anandhi, N. (2018). Method for Solving Unbalanced Transportation Problems Using Standard Deviations. International Journal of Pure and Applied Mathematics, 119 (16), 4971–4989.
[15]	Hamdy, A. T. (2007) Operations Research An Introduction. 8th Edition, Pearson Prentice Hall, Upper Saddle River. - References - Scientific Research Publishing. (n. d.).
[16]	Hitchcock, F. L. (1941). The Distribution of a Product from Several Sources to Numerous Localities. Journal of Mathematics and Physics, 20 (1–4), 224–230. https://doi.org/10.1002/SAPM1941201224
[17]	Issn, O., & Issn, P. (2021). Perfect Folding of Graphs Solution of a Transportation Problem. Global Journal of Science Frontier Research: 21 (1).
[18]	Jain, K. K., Bhardwaj, R., & Choudhary, S. (2019). A multi-objective transportation problem solves by lexicographic goal programming. International Journal of Recent Technology and Engineering, 7 (6), 1842–1846.
[19]	Juman, Z. A. M. S., Mostafa, S. A., Batuwita, A. P., Alarjani, A., Uddin, M. S., Jaber, M. M., Alam, T., & Attia, E. A. (2022). Close Interval Approximation of Pentagonal Fuzzy Numbers for Interval Data-Based Transportation Problems. Sustainability (Switzerland), 14 (12). https://doi.org/10.3390/su14127423
[20]	Juman, Z. A. M. S., & Nawarathne, N. G. S. A. (2019). An efficient alternative approach to solve a transportation problem. Ceylon Journal of Science, 48 (1), 19-29. https://doi.org/10.4038/cjs.v48i1.7584
[21]	Karthy, T., & Ganesan, K. (2018). Multi-Objective Transportation Problem - Genetic Algorithm Approach. International Journal of Pure and Applied Mathematics 119 (9), 343–350.
[22]	Korukoğlu, S., & Ballı, S. (2011). An Improved Vogel’s Approximation Method for The Transportation Problem. Mathematical and Computational Applications, 16 (2), 370–381.
[23]	M Selim Reza, A. K., M Jalal Uddin Jamali, A. R., & Biswas, B. (2019). a Modified Algorithm for Solving Unbalanced Transportation Problems. Journal of Engineering Science, 10 (1), 93–101.
[24]	Niluminda, K. P. O., & Ekanayake, E. M. U. S. B. (2022). An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm. American Journal of Applied Mathematics. 10 (6), 223-235. doi: 10.11648/j.ajam.20221006.11
[25]	Niluminda, K. P. O., & Ekanayake, E. M. U. S. B. (2022). An efficient method to solve minimum spanning tree problem using graph theory and improved ant colony optimization algorithm. North American Academic Research, 5 (12), 34-43. doi: https://doi.org/10.5281/zenodo.7459058
[26]	Niluminda K. P. O, Ekanayake E. M. U. S. B. (2022). Innovative Matrix Algorithm to Address the Minimal Cost-Spanning Tree Problem. J Electrical Electron Eng, 1 (1), 148-153. doi: 10.33140/JEEE.01.01.05.
[27]	Niluminda, K. P. O., & Ekanayake, E. M. U. S. B. (2022). Kruskal’s algorithm for solving the both balanced unbalanced acceptable and prohibited route transportation problems. North American Academic Research, 5 (12), 17-33. doi: https://doi.org/10.5281/zenodo.7457110
[28]	Niluminda, K. P. O., & Ekanayake, E. M. U. S. B. (2023). The Multi-Objective Transportation Problem Solve with Geometric Mean and Penalty Methods. Indonesian Journal of Innovation and Applied Sciences (IJIAS), 3(1), 74-85. https://doi.org/10.47540/ijias.v3i1.729
[29]	Niluminda, K. P. O., & Ekanayake, E. M. U. S. B. (2022). A novel approach based on the weight adjacency matrix to obtain the minimum weight spanning tree. 2022.
[30]	Kadhem, D. A. S., & Taher, M. S. (2013). Maximum {Supplies, Demands} Method to Find The Initial Transportation Problem. Journal of University of Zakho, 1 (2), 849–853.
[31]	Silmi Juman, Z. A. M., Masoud, M., Elhenawy, M., Bhuiyan, H., Komol, M. M. R., & Battaïa, O. (2021). A new algorithm for solving uncapacitated transportation problems with interval-defined demands and supplier capacities. Journal of Intelligent and Fuzzy Systems, 41 (1), 625–637. https://doi.org/10.3233/JIFS-202436
[32]	Sood, S., & Jain, K. (2015). The Maximum Difference Method to Find Initial Basic Feasible Solution for Transportation Problem. Asian Journal of Management Sciences, 03 (07), 8–11.
[33]	Koopmans, T. C., (1941). Optimum Utilization of the Transportation System. Econometrica, 17, 136–146.
[34]	Uddin, S., & Khan, A. R. (2016). Improved Least Cost Method to Obtain a Better IBFS to the Transportation Problem. Journal of Applied Mathematics & Bioinformatics, 6 (2), 1–20.

Cite This Article

Plain Text BibTeX RIS

APA Style

Niluminda, O., Ekanayake, U. (2023). Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems. American Journal of Traffic and Transportation Engineering, 8(6), 135-144. https://doi.org/10.11648/j.ajtte.20230806.12

Copy | Download

ACS Style

Niluminda, O.; Ekanayake, U. Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems. Am. J. Traffic Transp. Eng. 2023, 8(6), 135-144. doi: 10.11648/j.ajtte.20230806.12

Copy | Download

AMA Style

Niluminda O, Ekanayake U. Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems. Am J Traffic Transp Eng. 2023;8(6):135-144. doi: 10.11648/j.ajtte.20230806.12

Copy | Download

@article{10.11648/j.ajtte.20230806.12,
  author = {Oshan Niluminda and Uthpala Ekanayake},
  title = {Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems},
  journal = {American Journal of Traffic and Transportation Engineering},
  volume = {8},
  number = {6},
  pages = {135-144},
  doi = {10.11648/j.ajtte.20230806.12},
  url = {https://doi.org/10.11648/j.ajtte.20230806.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajtte.20230806.12},
  abstract = {Transportation is one of the various worldwide challenges that organizations must tackle. The Transportation Problem (TP) is also an important topic in the subject of optimization, where the aim is to reduce the overall transportation cost of distributing from a particular number of sources to a specific number of destinations (locations). This paper aims to investigate the most effective way to solve the Transportation Problem (TP) using the line (edge) colouring of a bipartite network. To solve the TP, several solutions have been proposed in the literature. The Initial Basic Feasible Solution (IBFS) and the Optimal Solution are the two solutions of TP. The North-West Corner Method (NWCM), the Lowest Cost Method (LCM), Row Minima Method (RMM), Column Minima Method (CMM), and Vogel's Approximation Method (VAM) may be used to find an IBFS, while the Modified Distribution (MODI) Method and the Stepping Stone Method can be used to find an optimal solution for the TP In this paper, propose a new algorithmic technique that utilizes the line (edge) colouring of a bipartite network to obtain an optimal or nearly optimal solution to the TP. The proposed technique is applied to balanced and unbalanced TP and compared to other existing methods. Experimental results show that the line (edge) colouring algorithm requires fewer iterations to achieve optimality compared to other current methodologies. In conclusion, the line (edge) colouring algorithm is a highly effective method for solving TP. By representing the TP as a bipartite network and using the proposed algorithmic technique, the optimum or nearly optimum TP solution can be obtained quickly and efficiently. This approach has significant potential for optimizing transportation logistics in various industries.
},
 year = {2023}
}

Copy | Download

TY  - JOUR
T1  - Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems
AU  - Oshan Niluminda
AU  - Uthpala Ekanayake
Y1  - 2023/11/11
PY  - 2023
N1  - https://doi.org/10.11648/j.ajtte.20230806.12
DO  - 10.11648/j.ajtte.20230806.12
T2  - American Journal of Traffic and Transportation Engineering
JF  - American Journal of Traffic and Transportation Engineering
JO  - American Journal of Traffic and Transportation Engineering
SP  - 135
EP  - 144
PB  - Science Publishing Group
SN  - 2578-8604
UR  - https://doi.org/10.11648/j.ajtte.20230806.12
AB  - Transportation is one of the various worldwide challenges that organizations must tackle. The Transportation Problem (TP) is also an important topic in the subject of optimization, where the aim is to reduce the overall transportation cost of distributing from a particular number of sources to a specific number of destinations (locations). This paper aims to investigate the most effective way to solve the Transportation Problem (TP) using the line (edge) colouring of a bipartite network. To solve the TP, several solutions have been proposed in the literature. The Initial Basic Feasible Solution (IBFS) and the Optimal Solution are the two solutions of TP. The North-West Corner Method (NWCM), the Lowest Cost Method (LCM), Row Minima Method (RMM), Column Minima Method (CMM), and Vogel's Approximation Method (VAM) may be used to find an IBFS, while the Modified Distribution (MODI) Method and the Stepping Stone Method can be used to find an optimal solution for the TP In this paper, propose a new algorithmic technique that utilizes the line (edge) colouring of a bipartite network to obtain an optimal or nearly optimal solution to the TP. The proposed technique is applied to balanced and unbalanced TP and compared to other existing methods. Experimental results show that the line (edge) colouring algorithm requires fewer iterations to achieve optimality compared to other current methodologies. In conclusion, the line (edge) colouring algorithm is a highly effective method for solving TP. By representing the TP as a bipartite network and using the proposed algorithmic technique, the optimum or nearly optimum TP solution can be obtained quickly and efficiently. This approach has significant potential for optimizing transportation logistics in various industries.

VL  - 8
IS  - 6
ER  -

Copy | Download

Author Information

Oshan Niluminda

Department of Physical Sciences, Faculty of Applied Sciences, Rajarata University of Sri Lanka, Mihinthale, Sri Lanka

Contact Email
Uthpala Ekanayake

Department of Physical Sciences, Faculty of Applied Sciences, Rajarata University of Sri Lanka, Mihinthale, Sri Lanka

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Niluminda, O., Ekanayake, U. (2023). Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems. American Journal of Traffic and Transportation Engineering, 8(6), 135-144. https://doi.org/10.11648/j.ajtte.20230806.12

Copy | Download

ACS Style

Niluminda, O.; Ekanayake, U. Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems. Am. J. Traffic Transp. Eng. 2023, 8(6), 135-144. doi: 10.11648/j.ajtte.20230806.12

Copy | Download

AMA Style

Niluminda O, Ekanayake U. Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems. Am J Traffic Transp Eng. 2023;8(6):135-144. doi: 10.11648/j.ajtte.20230806.12

Copy | Download

@article{10.11648/j.ajtte.20230806.12,
  author = {Oshan Niluminda and Uthpala Ekanayake},
  title = {Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems},
  journal = {American Journal of Traffic and Transportation Engineering},
  volume = {8},
  number = {6},
  pages = {135-144},
  doi = {10.11648/j.ajtte.20230806.12},
  url = {https://doi.org/10.11648/j.ajtte.20230806.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajtte.20230806.12},
  abstract = {Transportation is one of the various worldwide challenges that organizations must tackle. The Transportation Problem (TP) is also an important topic in the subject of optimization, where the aim is to reduce the overall transportation cost of distributing from a particular number of sources to a specific number of destinations (locations). This paper aims to investigate the most effective way to solve the Transportation Problem (TP) using the line (edge) colouring of a bipartite network. To solve the TP, several solutions have been proposed in the literature. The Initial Basic Feasible Solution (IBFS) and the Optimal Solution are the two solutions of TP. The North-West Corner Method (NWCM), the Lowest Cost Method (LCM), Row Minima Method (RMM), Column Minima Method (CMM), and Vogel's Approximation Method (VAM) may be used to find an IBFS, while the Modified Distribution (MODI) Method and the Stepping Stone Method can be used to find an optimal solution for the TP In this paper, propose a new algorithmic technique that utilizes the line (edge) colouring of a bipartite network to obtain an optimal or nearly optimal solution to the TP. The proposed technique is applied to balanced and unbalanced TP and compared to other existing methods. Experimental results show that the line (edge) colouring algorithm requires fewer iterations to achieve optimality compared to other current methodologies. In conclusion, the line (edge) colouring algorithm is a highly effective method for solving TP. By representing the TP as a bipartite network and using the proposed algorithmic technique, the optimum or nearly optimum TP solution can be obtained quickly and efficiently. This approach has significant potential for optimizing transportation logistics in various industries.
},
 year = {2023}
}

Copy | Download

TY  - JOUR
T1  - Graph Colouring to Solve Both Balanced and Unbalanced Transportation Problems
AU  - Oshan Niluminda
AU  - Uthpala Ekanayake
Y1  - 2023/11/11
PY  - 2023
N1  - https://doi.org/10.11648/j.ajtte.20230806.12
DO  - 10.11648/j.ajtte.20230806.12
T2  - American Journal of Traffic and Transportation Engineering
JF  - American Journal of Traffic and Transportation Engineering
JO  - American Journal of Traffic and Transportation Engineering
SP  - 135
EP  - 144
PB  - Science Publishing Group
SN  - 2578-8604
UR  - https://doi.org/10.11648/j.ajtte.20230806.12
AB  - Transportation is one of the various worldwide challenges that organizations must tackle. The Transportation Problem (TP) is also an important topic in the subject of optimization, where the aim is to reduce the overall transportation cost of distributing from a particular number of sources to a specific number of destinations (locations). This paper aims to investigate the most effective way to solve the Transportation Problem (TP) using the line (edge) colouring of a bipartite network. To solve the TP, several solutions have been proposed in the literature. The Initial Basic Feasible Solution (IBFS) and the Optimal Solution are the two solutions of TP. The North-West Corner Method (NWCM), the Lowest Cost Method (LCM), Row Minima Method (RMM), Column Minima Method (CMM), and Vogel's Approximation Method (VAM) may be used to find an IBFS, while the Modified Distribution (MODI) Method and the Stepping Stone Method can be used to find an optimal solution for the TP In this paper, propose a new algorithmic technique that utilizes the line (edge) colouring of a bipartite network to obtain an optimal or nearly optimal solution to the TP. The proposed technique is applied to balanced and unbalanced TP and compared to other existing methods. Experimental results show that the line (edge) colouring algorithm requires fewer iterations to achieve optimality compared to other current methodologies. In conclusion, the line (edge) colouring algorithm is a highly effective method for solving TP. By representing the TP as a bipartite network and using the proposed algorithmic technique, the optimum or nearly optimum TP solution can be obtained quickly and efficiently. This approach has significant potential for optimizing transportation logistics in various industries.

VL  - 8
IS  - 6
ER  -

Copy | Download