Article Sidebar

Download
PDF
Statistic
Read Counter : 779 Download : 670

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

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

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following License

CC BY: This license allows reusers to distribute, remix, adapt, and build upon the material in any medium or format, so long as attribution is given to the creator. The license allows for commercial use.

 

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
Crossref
Scopus
Google Scholar
Europe PMC

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
  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.
  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.
  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.
  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.
  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.
  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.
  13. Hosseini, E. (2017). Three new methods to find initial basic feasible solution of transportation problems. Applied Mathematical Sciences, 11:37, 1803-1814.
  14. Hougardy, S. (2010). The Floyd-Warshall algorithm on graphs with negative cycles. Information Processing Letters, 110:8-9, 279-281.
  15. Iheonu, N. O. & Inyama, S. C. (2016). Optimization of Transportation Problem. Journal of Advances in Mathematics and Computer Science, 1-11.
  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
  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.
  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
  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.
  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.
  24. Taylor, B. W. III (1999) Introduction to Management Science, 6th ed., Prentice Hall Inc., New Jersey.