Physical distribution (transportation) of goods and services from multiple supply centers to multiple demand centers is an important application of linear programming (LP). A transportation problem (TP) can also be solved using the simplex method when expressed as an LP model. However, because a TP has a large number of variables and constraints, solving it using simplex methods takes a long time. Many scientists have devised and continue to devise novel solutions to the classic TP. The prohibited route transportation problem, on the other hand, is a subset of TPs for which most scientists have yet to develop a specific TP. Certain routes may be impassable in some cases due to transportation issues. To name a few: construction projects, poor road conditions, strikes, unexpected disasters, and local traffic laws. Such limits (or prohibitions) in the TP can be managed by assigning a very high cost to the prohibited routes, ensuring that they do not appear in the optimal solution. This paper presents a heuristic algorithm and an improved ant colony optimization algorithm for achieving an initial feasible solution (IFS) to a prohibitive transportation problem (PTP). Using the PTP in the proposed method, on the other hand, produces the best IFS for a prohibited transportation problem and outperforms existing methods with less computation time and complexity. As a result, the proposed methods are an appealing alternative to traditional problem-solving approaches. In some numerical examples, the feasible solution of the proposed method is the same as the optimal solution.
| Published in | International Journal of Applied Mathematics and Theoretical Physics (Volume 8, Issue 2) |
| DOI | 10.11648/j.ijamtp.20220802.12 |
| Page(s) | 43-51 |
| 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 |
Ant Colony Optimization Algorithm, Initial Feasible Solution, Optimal Solution, Prohibited Transportation Problems, Transportation Problem
| [1] | Blum, C. (2005). Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling, Computers & Operations Research, 32 (6): 1565-1591. |
| [2] | Dantzig, G. B. (1951). Application of the Simplex Method to a Transportation Problem, Activity Analysis of Production and Allocation, Cowles Commission Monograph 13. |
| [3] | Dorigo, M.; Birattari, M. (2006). Stutzle, T. Ant colony optimization, IEEE Computational Intelligence Magazine, 1 (4): 28-39. |
| [4] | Dorigo, M.; Maniezzo, V.; Colorni. (1996). A., Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26 (1): 29-41. |
| [5] | Ford. R. L; Fulkerson, R. D. (1956). Solving the transportation Problems. Management Sciences, Vol. 3. No. 1. |
| [6] | Hitchcock, F. L. (1941). The Distribution of a Product from Several Sources to Numerous Localities," Journal of Math. and Physics, vol. 20, pp. 224-230. |
| [7] | Koopmans T. C. (1949). Optimum utilization of the transportation system. Econometrica, 17, 3-4. |
| [8] | 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. Special Issue: Artificial Intelligence in Electrical Power & Energy. Vol. 5, No. 1, pp. 1-8. |
| [9] | Ekanayake E. M. U. S. B.; Perera S. P. C.; Daundasekara W. B.; Juman Z. A. M. S. Juman. (2020). A Modified Ant Colony Optimization Algorithm for Solving a Transportation Problem, Journal of Advances in Mathematics and Computer Science, 35 (5): 83-101. |
| [10] | Engelbrecht, A. P. (2005). Fundamentals of Computational Swarm Intelligence, 2005; Chichester, UK: Wiley. |
| [11] | Pandian, P.; Natarajan, G. (2010). A new method for finding an optimal solution for transportation problems, International Journal of Mathematical Sciences and Engineering Applications, 4, 59-65. |
| [12] | Rashid, A. (2013). Development of a new heuristic for improvement of initial basic feasible solution of a balanced transportation problem, Jahangirnagar Journal of Mathematics and Mathematical Sciences, 28. |
| [13] | SHARMA, J. K. (2008). Operations Research Theory and Applications, 6th ed.; Trinity, GOLDEN HOUSE, DARYAGANJ, NEW DELHI - 110002, INDIA, pp. 256-309. |
| [14] | Sharma.. R. R. K,; Sharma. K. D. (2000). A new dual based procedure for the transportation problem, European Journal of Operational Res., 122, 611-624. |
| [15] | Sirinivasan, G. (2010). Operations Research Principles and Applications, 2nd ed; 2010; PHI Learning Private Limited, New Delhi, pp, 104-144. |
| [16] | Socha, K.; Sampels, M.; Manfrin, M. (2003). Ant algorithms for the university course timetabling problem with regard to the state-of-the-art, Proc. Workshop on Applications of Evolutionary Computing, 334-345. |
| [17] | Stutzle, T.; Hoos, H. H. (1997). The MAX-MIN ant system and local search for the traveling salesman problem, Proc. IEEE International Conference on Evolutionary Computation, 309-314. |
| [18] | Tolstoy, A. N. (1930). Russian; Methods of finding the minimal total kilometrage in cargotransportation planning in space. Russian; Transportation Planning, Volume, Trans Press of the National Commissariat of Transportation, Moscow, pp. 23–55. |
| [19] | Uthpala Ekanayake, Wasantha Daundasekara, Pantalian Perera. (2020). An Approach for Solving Minimum Spanning Tree Problem and Transportation Problem Using Modified Ant Colony Algorithm, American Academic Research, Volume 3, Issue 9; October, 3 (10) 28-45. |
| [20] | Vishwas Deep Joshi,; Nilama Gupta. (2012). Identifying more-for-less paradox in the linear fractional transportation problem using objective matrix, Mathematika, 28, 173–180. |
| [21] | Wang, X.; Gao, X. Z. Ovaska, S. J. (2007). A Hybrid Optimization Algorithm Based on Ant Colony and Immune Principle, International Journal of Computer Science & Applications, Vol. 4 Issue 3, pp 30-44. |
APA Style
Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake. (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
ACS Style
Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake. An Improved Ant Colony Algorithm to Solve Prohibited Transportation Problems. Int. J. Appl. Math. Theor. Phys. 2022, 8(2), 43-51. doi: 10.11648/j.ijamtp.20220802.12
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.ijamtp.20220802.12,
author = {Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake},
title = {An Improved Ant Colony Algorithm to Solve Prohibited Transportation Problems},
journal = {International Journal of Applied Mathematics and Theoretical Physics},
volume = {8},
number = {2},
pages = {43-51},
doi = {10.11648/j.ijamtp.20220802.12},
url = {https://doi.org/10.11648/j.ijamtp.20220802.12},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijamtp.20220802.12},
abstract = {Physical distribution (transportation) of goods and services from multiple supply centers to multiple demand centers is an important application of linear programming (LP). A transportation problem (TP) can also be solved using the simplex method when expressed as an LP model. However, because a TP has a large number of variables and constraints, solving it using simplex methods takes a long time. Many scientists have devised and continue to devise novel solutions to the classic TP. The prohibited route transportation problem, on the other hand, is a subset of TPs for which most scientists have yet to develop a specific TP. Certain routes may be impassable in some cases due to transportation issues. To name a few: construction projects, poor road conditions, strikes, unexpected disasters, and local traffic laws. Such limits (or prohibitions) in the TP can be managed by assigning a very high cost to the prohibited routes, ensuring that they do not appear in the optimal solution. This paper presents a heuristic algorithm and an improved ant colony optimization algorithm for achieving an initial feasible solution (IFS) to a prohibitive transportation problem (PTP). Using the PTP in the proposed method, on the other hand, produces the best IFS for a prohibited transportation problem and outperforms existing methods with less computation time and complexity. As a result, the proposed methods are an appealing alternative to traditional problem-solving approaches. In some numerical examples, the feasible solution of the proposed method is the same as the optimal solution.},
year = {2022}
}
TY - JOUR T1 - An Improved Ant Colony Algorithm to Solve Prohibited Transportation Problems AU - Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake Y1 - 2022/09/27 PY - 2022 N1 - https://doi.org/10.11648/j.ijamtp.20220802.12 DO - 10.11648/j.ijamtp.20220802.12 T2 - International Journal of Applied Mathematics and Theoretical Physics JF - International Journal of Applied Mathematics and Theoretical Physics JO - International Journal of Applied Mathematics and Theoretical Physics SP - 43 EP - 51 PB - Science Publishing Group SN - 2575-5927 UR - https://doi.org/10.11648/j.ijamtp.20220802.12 AB - Physical distribution (transportation) of goods and services from multiple supply centers to multiple demand centers is an important application of linear programming (LP). A transportation problem (TP) can also be solved using the simplex method when expressed as an LP model. However, because a TP has a large number of variables and constraints, solving it using simplex methods takes a long time. Many scientists have devised and continue to devise novel solutions to the classic TP. The prohibited route transportation problem, on the other hand, is a subset of TPs for which most scientists have yet to develop a specific TP. Certain routes may be impassable in some cases due to transportation issues. To name a few: construction projects, poor road conditions, strikes, unexpected disasters, and local traffic laws. Such limits (or prohibitions) in the TP can be managed by assigning a very high cost to the prohibited routes, ensuring that they do not appear in the optimal solution. This paper presents a heuristic algorithm and an improved ant colony optimization algorithm for achieving an initial feasible solution (IFS) to a prohibitive transportation problem (PTP). Using the PTP in the proposed method, on the other hand, produces the best IFS for a prohibited transportation problem and outperforms existing methods with less computation time and complexity. As a result, the proposed methods are an appealing alternative to traditional problem-solving approaches. In some numerical examples, the feasible solution of the proposed method is the same as the optimal solution. VL - 8 IS - 2 ER -
Email: