An Enhanced Vogel Approximation Method for Solving the Transportation Problem

Shofiyatul Malik Mumtaza, Juhari Juhari

Abstract


The transportation problem is a classical linear programming model for allocating shipments from several supply points to several demand points at minimum total cost. A high-quality initial basic feasible solution is important because it can reduce the number of improvement iterations required by subsequent optimality tests. This study proposes an Enhanced Vogel Approximation Method (EVAM), a penalty-based modification of Vogel's Approximation Method that uses the three smallest active costs in each row or column. The method was tested on a balanced $5\times5$ transportation instance and compared with the Improved Vogel's Approximation Method (IVAM), followed by Stepping Stone improvement. The results show that IVAM produced an initial solution equal to the optimal cost of 59,356, whereas EVAM produced an initial cost of 60,727. After three Stepping Stone iterations, EVAM reached the same optimal cost of 59,356, with an initial optimality gap of 2.31\%. These findings indicate that EVAM is simple and transparent, although it does not dominate IVAM on the tested instance.

Keywords


Transportation problem; Enhanced Vogel Approximation Method; initial basic feasible solution; Stepping Stone method; optimization

Full Text:

PDF

References


References

  1. Hitchcock, F. L. (1941). The distribution of a product from several sources to numerous localities. Journal of Mathematics and Physics, 20(1–4), 224–230. https://doi.org/10.1002/sapm1941201224
  2. Koopmans, T. C. (1949). Optimum utilization of the transportation system. Econometrica, 17, 136–146. https://doi.org/10.2307/1907301
  3. Charnes, A., & Cooper, W. W. (1954). The stepping stone method of explaining linear programming calculations in transportation problems. Management Science, 1(1), 49–69. https://doi.org/10.1287/mnsc.1.1.49
  4. Ford, L. R., & Fulkerson, D. R. (1956). Solving the transportation problem. Management Science, 3(1), 24–32. https://doi.org/10.1287/mnsc.3.1.24
  5. Shore, H. H. (1970). The transportation problem and the Vogel approximation method. Decision Sciences, 1(3–4), 441–457. https://doi.org/10.1111/j.1540-5915.1970.tb00792.x
  6. Goyal, S. K. (1984). Improving VAM for unbalanced transportation problems. Journal of the Operational Research Society, 35(12), 1113–1114. https://doi.org/10.1057/jors.1984.217
  7. Balakrishnan, N. (1990). Modified Vogel's approximation method for the unbalanced transportation problem. Applied Mathematics Letters, 3(2), 9–11. https://doi.org/10.1016/0893-9659(90)90003-T
  8. Gass, S. I. (1990). On solving the transportation problem. Journal of the Operational Research Society, 41(4), 291–297. https://doi.org/10.1057/jors.1990.50
  9. Arsham, H. (1992). Postoptimality analyses of the transportation problem. Journal of the Operational Research Society, 43(2), 121–139. https://doi.org/10.1057/jors.1992.18
  10. Mathirajan, M., & Meenakshi, B. (2004). Experimental analysis of some variants of Vogel's approximation method. Asia-Pacific Journal of Operational Research, 21(4), 447–462. https://doi.org/10.1142/S0217595904000333
  11. Korukoglu, S., & Balli, S. (2011). An improved Vogel's approximation method for the transportation problem. Mathematical and Computational Applications, 16(2), 370–381. https://doi.org/10.3390/mca16020370
  12. Nahar, J., Rusyaman, E., & Putri, S. D. V. E. (2018). Application of improved Vogel's approximation method in minimization of rice distribution costs of Perum BULOG. IOP Conference Series: Materials Science and Engineering, 332(1), 012027. https://doi.org/10.1088/1757-899X/332/1/012027
  13. 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. https://doi.org/10.1016/j.eij.2019.01.002
  14. Amaliah, B., Fatichah, C., Suryani, E., & Muswar, A. (2020). Total opportunity cost matrix-supreme cell: A new method to obtain initial basic feasible solution of transportation problems. In Proceedings of the 8th International Conference on Computer and Communications Management (pp. 151–156). Association for Computing Machinery. https://doi.org/10.1145/3411174.3411198
  15. Amaliah, B., Fatichah, C., & Suryani, E. (2021). Two highest penalties: A modified Vogel's approximation method to find initial basic feasible solution of transportation problem. In 2021 13th International Conference on Information & Communication Technology and System (ICTS) (pp. 318–323). IEEE. https://doi.org/10.1109/ICTS52701.2021.9608005
  16. Amaliah, B., Fatichah, C., & Suryani, E. (2022). A new heuristic method of finding the initial basic feasible solution to solve the transportation problem. Journal of King Saud University - Computer and Information Sciences, 34(5), 2298–2307. https://doi.org/10.1016/j.jksuci.2020.07.007
  17. Amaliah, B., Fatichah, C., & Suryani, E. (2022). A supply selection method for better feasible solution of balanced transportation problem. Expert Systems with Applications, 203, 117399. https://doi.org/10.1016/j.eswa.2022.117399
  18. Ekanayake, E. M. D. B., & Ekanayake, E. M. U. S. B. (2022). A novel approach algorithm for determining the initial basic feasible solution for transportation problems. Indonesian Journal of Innovation and Applied Sciences, 2(3), 234–246. https://doi.org/10.47540/ijias.v2i3.529
  19. Hussein, H. A., Shiker, M. A. K., & Zabiba, M. S. M. (2020). A new revised efficient of VAM to find the initial solution for the transportation problem. Journal of Physics: Conference Series, 1591(1), 012032. https://doi.org/10.1088/1742-6596/1591/1/012032
  20. Karagul, K., & Sahin, Y. (2020). A novel approximation method to obtain initial basic feasible solution of transportation problem. Journal of King Saud University - Engineering Sciences, 32(3), 211–218. https://doi.org/10.1016/j.jksues.2019.03.003
  21. Wireko, F. A., Mensah, I. D. K., Aborhey, E. N. A., Appiah, S. A., Sebil, C., & Ackora-Prah, J. (2025). The maximum range method for finding initial basic feasible solution for transportation problems. Results in Control and Optimization, 19, 100551. https://doi.org/10.1016/j.rico.2025.100551
  22. Kalaivani, N., & Visalakshidevi, E. M. (2024). A generalized novel approach to transportation problem using multi-partite graph method. Measurement: Sensors, 33, 101060. https://doi.org/10.1016/j.measurementsensors.2024.101060




DOI: https://doi.org/10.18860/jrmm.v5i4.39562

Refbacks

  • There are currently no refbacks.