An Improved Ant Colony Algorithm to Solve Prohibited Transportation Problems:: Science Publishing Group

An Improved Ant Colony Algorithm to Solve Prohibited Transportation Problems

Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake

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

International Journal of Applied Mathematics and Theoretical Physics, Volume 8, Issue 2, June 2022

Pages: 43-51

Received: Jul. 25, 2022

Accepted: Aug. 09, 2022

Published: Sep. 27, 2022

DOI: 10.11648/j.ijamtp.20220802.12

Downloads:

Views:

Download PDF: Download PDF

Export Citation: Export citation to RIS Export citation to BibTeX

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.

Keywords

Ant Colony Optimization Algorithm, Initial Feasible Solution, Optimal Solution, Prohibited Transportation Problems, Transportation Problem

To cite this article

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

Copyright © 2022 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

References

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.