Main Article Content

Abstract

The Transportation Problem (TP) is a mathematical optimization technique which regulates the flow of items along routes by adopting an optimum guiding principle to the total shipping cost. However, instances including road hazards, traffic regulations, road construction and unexpected floods sometimes arise in transportation to ban shipments via certain routes. In formulating the TPs, potential prohibited routes are assigned a large penalty cost, M, to prevent their presence in the model solution. The arbitrary usage of the big M as a remedy for this interdiction does not go well with a good solution. In this paper, a two-phase method is proposed to solve a TP with prohibited routes. The first phase is formulated as an All-Pairs Least Cost Problem (APLCP) which assigns respectively a non-discretionary penalty cost M*ij <= M to each of n prohibited routes present using the Floyd¢s method. At phase two, the new penalty values are substituted into the original problem respectively and the resulting model is solved using the transportation algorithm. The results show that, setting this modified penalty cost ( M*) logically presents a good solution. Therefore, the discretionary usage of the M <= ∞ is not a guarantee for good model solutions. The modified cost M*<= M so attained in the sample model, is relatively less than the Big M ( <= ∞) and gives a good solution which makes the method reliable.

Keywords

Floyd's method transportation problem prohibited routes 2-phase method penalty cost

Article Details

How to Cite
Ackora Prah, J., Acheson, V., Barnes, B., Takyi, I., & Owusu-Ansah, E. (2022). A 2-Phase Method for Solving Transportation Problems with Prohibited Routes. Pakistan Journal of Statistics and Operation Research, 18(3), 749-758. https://doi.org/10.18187/pjsor.v18i3.3911

References

  1. Ackora-Prah, J., Anto, E. K. & Osei, L. K. (2016). Optimal Location of Electricity, 3:1, 21 - 31, http://dx.doi.org/10.12988/ijco.2016.510675 DOI: https://doi.org/10.12988/ijco.2016.510675
  2. Aini, A. & Salehipour, A. (2012). Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem. Applied Mathematics Letters, 25:1, 1-5. DOI: https://doi.org/10.1016/j.aml.2011.06.008
  3. Amaliah, B., Fatichah, C., Suryani, E. (2019) Total opportunity cost matrix- Minimal total: A new approach to determine initial basic feasible solution of a transportation problem, Egyptian Informatics Journal, 20:2, 131-141, ISSN 1110-8665, https://doi.org/10.1016/j.eij.2019.01.002. DOI: https://doi.org/10.1016/j.eij.2019.01.002
  4. Amoako, E. (2019). Application of Floyd’s Algorithm for Knust Fire Service. Applied Mathematics, 49-58.
  5. Charnes, A. & Cooper, W. W. (1954). The stepping stone method of explaining linear programming calculations in transportation problems, Management Science 1, 49-69. DOI: https://doi.org/10.1287/mnsc.1.1.49
  6. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, C. (2001), Introduction to Algorithms, MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3. Section 25.3, "Johnson’s algorithm for sparse graphs", 636-640.
  7. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. See in particular Section 26.2, "The Floyd-Warshall algorithm", 558-565 and Section 26.4, "A general framework for solving path problems in directed graphs", 570-576.
  8. Dantzig, G. B. (1951). Application of the simplex method to a transportation problem, In Activity Analysis of Production and Allocation, (Edited by T.C. Koopmans), John Wiley & Sons, New York.
  9. Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269-271. doi:10.1007/BF01386390. DOI: https://doi.org/10.1007/BF01386390
  10. Floyd, Robert W. (1962). Algorithm 97: Shortest Path. Association for Computing Machinery, New York,
  11. NY, USA, volume 5, No. 6, ISSN: 0001-0782, https://doi.org/10.1145/367766.368168. DOI: https://doi.org/10.1145/367766.368168
  12. Hitchcock, F.L. (1941). The distribution of a product from several sources to numerous localities, MIT Journal of Mathematics and Physics 20:224-230 MR0004469. DOI: https://doi.org/10.1002/sapm1941201224
  13. Hosseini, E. (2017). Three new methods to find initial basic feasible solution of transportation problems. Applied Mathematical Sciences, 11:37, 1803-1814. DOI: https://doi.org/10.12988/ams.2017.75178
  14. Hougardy, S. (2010). The Floyd-Warshall algorithm on graphs with negative cycles. Information Processing Letters, 110:8-9, 279-281. DOI: https://doi.org/10.1016/j.ipl.2010.02.001
  15. Iheonu, N. O. & Inyama, S. C. (2016). Optimization of Transportation Problem. Journal of Advances in Mathematics and Computer Science, 1-11. DOI: https://doi.org/10.9734/BJMCS/2016/17279
  16. Khamami,A. & Saputra, R. (2019). The shortest path search application based on the city transport route in Semarang using the Floyd-warshall algorithm. In Journal of Physics: Conference Series, 1217:1, 012116. IOP Publishing. remark DOI: https://doi.org/10.1088/1742-6596/1217/1/012116
  17. Li, J., Qin, H., Shen, H.,Tsui, K. L. (2019). The unilateral transportation problem, Transportation Research Part E: Logistics and Transportation Review, 132, 1-29, ISSN: 1366-5545, https://doi.org/10.1016/j.tre.2019.10.004. DOI: https://doi.org/10.1016/j.tre.2019.10.004
  18. Monge, G. (1781). Dissertation on the theory of cuttings and embankments. History of the Royal Academy of Sciences of Paris, with the Memories of Mathematics and Physics for the same year, 666-704.
  19. Phil, F. (2010). "An Interview with Edsger W. Dijkstra". Communications of the ACM. 53:8, 41-47. doi:10.1145/1787234.1787249 DOI: https://doi.org/10.1145/1787234.1787249
  20. Ramadhan, Z., Siahaan, A. P. U. & Mesran, M. (2018). Prim and Floyd-Warshall Comparative Algorithms in Shortest Path Problem. In Proceedings of the Joint Workshop KO2PI and The 1st International Conference on Advance & Scientific Innovation. DOI: https://doi.org/10.4108/eai.23-4-2018.2277598
  21. Reinfeld, N. V. & Vogel, W. R. (1958). Mathematical Programming, Prentice-Hall, New Jersey.
  22. Sapundzhi, F. I. & Popstoilov, M. S. (2018). Optimization algorithms for finding the shortest paths. Bulgarian Chemical Communications, 50:Special Issue B, 115-120.
  23. Seidel, R. (1995). All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs, Journal of Computer and System Sciences, 51:3, 400-403, ISSN 0022-0000, https://doi.org/10.1006/jcss.1995. 1078. DOI: https://doi.org/10.1006/jcss.1995.1078
  24. Taylor, B. W. III (1999) Introduction to Management Science, 6th ed., Prentice Hall Inc., New Jersey.