International Journal of Applied Mathematics and Theoretical Physics

| Peer-Reviewed |

An Improved Ant Colony Algorithm to Solve Prohibited Transportation Problems

Received: Jul. 25, 2022    Accepted: Aug. 09, 2022    Published: Sep. 27, 2022
Views:       Downloads:

Share

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.

DOI 10.11648/j.ijamtp.20220802.12
Published in International Journal of Applied Mathematics and Theoretical Physics ( Volume 8, Issue 2, June 2022 )
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

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://download.sciencepg.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

  • Section