| Peer-Reviewed

An Improved Ant Colony Algorithm to Solve Prohibited Transportation Problems

Received: 25 July 2022     Accepted: 9 August 2022     Published: 27 September 2022
Views:       Downloads:
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.

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), 2022. Published by Science Publishing Group

Keywords

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

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.
Cite This Article
  • 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

    Copy | Download

    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

    Copy | Download

    AMA 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

    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}
    }
    

    Copy | Download

  • 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  - 

    Copy | Download

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

  • Sections