A comprehensive study of classical heuristic algorithms used in the process of solving transportation problem

• Autorzy: Szwarc Krzysztof , Boryczka Urszula , Twaróg Sebastian , Szołtysek Jacek

Identyfikatory

DOI

10.17270/J.LOG.2019.346

Warianty tytułu

PL

Porównanie klasycznych algorytmów heurystycznych stosowanych w procesie rozwiązywania problemów transportowych

• Języki publikacji: EN

Abstrakty

EN

Background: Transportation Problem (TP) is a special case of integer programming, characterised by indisputable practical significance (in particular in the area of logistics). For this reason, many techniques have been proposed to solve the problem both in optimum and approximate manner. The problem of selecting an effective technique for determining a suboptimal solution for TP was addressed by many researchers, however the implementation of only certain heuristics, 'test bed' applied, as well as non-performance of statistical tests make it impossible to clearly identify the recommended approach to application of heuristics in TP, leaving a research gap which determined the writing of this article. The additional purpose of this paper is to provide a summary of selected approximate methods, taking into consideration the number of iterations necessary to design the optimal solution by means of Modified Distribution (MODI) method and to demonstrate potential correlations between the parameters describing a problem instance and the efficiency of the methods. Methods: This paper presents a comparative study of four classic techniques (NWC, LCM, VAM and RAM). The tests were performed on three sets of 2,500 pseudo-randomly generated tasks and the observations were also checked by means of the Wilcoxon Signed-Rank Test and Pearson correlation coefficient. Results: The results confirms that VAM is characterised by a significant quality of the determined results, whereas NWC develops solutions of low efficiency. However, contrary to the observations made for small TP instances, RAM was characterised by a higher error value than LCM for huge set, demonstrating the impossibility to generalise results obtained for small problems (presented e.g. in literature), in order to determine their efficiency for higher instances. Conclusions: It is recommended to apply VAM both for the determination of initial solution in MODI method and for performing allocation of resources, using only heuristics. However, taking into consideration the utilitarian approach and possible occurrence of the necessity to solve TP instances without using the appropriate software, it is recommended to use LCM for solving large instances of TP. The presence of strong correlation between the number of nodes describing the TP instance and the number of iterations necessary to determine the optimal solution by MODI method has been identified.

PL

Wstęp: Zagadnienie transportowe (ZT) jest specjalnym przypadkiem programowania całkowitoliczbowego, charakteryzującym się niekwestionowanym znaczeniem praktycznym (w szczególności w obszarze logistyki). Z tego powodu powstało wiele technik przeznaczonych do rozwiązywania problemu zarówno w sposób optymalny, jak i przybliżony. Problem wyboru efektywnej metody konstruowania suboptymalnego rozwiązania dla ZT został poruszony przez wielu badaczy, jednakże zastosowanie przez nich tylko niektórych heurystyk, użyte "łoże testowe", a także brak przeprowadzenia testów statystycznych uniemożliwiają jednoznaczne określenie odpowiedniego podejścia do stosowania heurystyki w ZT, pozostawiając lukę badawczą, która stała się inspiracją do napisania niniejszego artykułu. Dodatkowym celem artykułu jest porównanie wybranych metod przybliżonych, z uwzględnieniem liczby iteracji niezbędnych do zaprojektowania optymalnego rozwiązania za pomocą metody Modified Distribution (MODI) oraz wykazanie potencjalnych korelacji pomiędzy parametrami opisującymi instancję problemu a skutecznością technik. Metody: W pracy przedstawiono badania porównawcze czterech klasycznych heurystyk (NWC, LCM, VAM i RAM). Testy przeprowadzono na trzech zestawach zadań, składających się z 2500 pseudolosowo wygenerowanych instatacji problemu. Obserwacje potwierdzono za pomocą testu Wilcoxon Signed-Rank i współczynnika korelacji liniowej Pearsona. Wyniki: Badania potwierdzają, że VAM charakteryzuje się znaczącą jakością wyznaczonych wyników, podczas gdy NWC konstruuje rezultaty o niskiej jakości. W przeciwieństwie do wyników sformułowanych dla niewielkich instatacji ZT, wyniki metody RAM dla dużego zbioru charakteryzowały się wyższą wartością błędu niż rezultaty LCM, wykazując brak możliwości uogólnienia wniosków prawdziwych dla małych problemów (przedstawionych np. w literaturze przedmiotu). Wnioski: Zaleca się stosowanie VAM zarówno do określania bazowego rozwiązania w metodzie MODI, jak i do przygotowania alokacji zasobów, w przypadku korzystania wyłącznie z heurystyk. Biorąc jednak pod uwagę podejście utylitarne i możliwość wystąpienia konieczności rozwiązywania instancji ZT bez użycia odpowiedniego oprogramowania, zaleca się stosowanie LCM do rozwiązywania dużych instancji problemu. Zidentyfikowano także silną korelację pomiędzy liczbą węzłów opisujących instancję ZT a liczbą iteracji niezbędnych do określenia optymalnego rozwiązania za pomocą metody MODI.

Słowa kluczowe

EN

transportation problem; best initial feasible solution; MODI; VAM; RAM; LCM

PL

zagadnienie transportowe; MODI; VAM; RAM; LCM

• Wydawca: Wyższa Szkoła Logistyki
• Czasopismo: LogForum
• Rocznik: 2019
• Tom: Vol. 15, no. 3
• Strony: 390--401
• Opis fizyczny: Bibliogr. 20 poz., tab.

Twórcy

autor

Szwarc Krzysztof

• Institute of Computer Science, University of Silesia in Katowice, ul. Będzińska 39, 41-200 Sosnowiec, Poland

autor

Boryczka Urszula

• Institute of Computer Science, University of Silesia in Katowice, ul. Będzińska 39, 41-200 Sosnowiec, Poland

autor

Twaróg Sebastian

• Department of Social Logistics, Faculty of Management, University of Economics in Katowice, ul. 1 Maja 50, 40-287 Katowice, Poland

autor

Szołtysek Jacek

• Department of Social Logistics, Faculty of Management, University of Economics in Katowice, ul.1 Maja 50, 40-287 Katowice, Poland

Bibliografia

• 1. Ali U., Mustapha A., 2013. Comparison of Transportation Algorithms Using Data from Katsina State Transport Authority, Katsina State, Nigeria, Nigerian Journal of Basic and Applied Science 21(3), 207-214. http://doi.org/10.4314/njbas.v21i3.6.
• 2. Dantzig G., 1951, Application of the simplex method to a transportation problem. In: Koopmans, T. (Ed.), Activity Analysis of Production and Allocation. John Wiley and Sons, 359-373.
• 3. Das U., Babu A., Khan A., Helal A., Uddin S., 2014. Logical Development Of Vogel's Approximation Method (LD-VAM): An Approach To Find Basic Feasible Solution Of Transportation Problem, International Journal of Scientific & Technology Research 3(2), 42-48.
• 4. Deshpande V., 2009. An Optimal method for Obtaining Initial Basic Feasible Solution of the Transportation Problem. National Conference on Emerging Trends in Mechanical Engineering (ETME-2009), 31-36.
• 5. Gujjula R., Werk S., Günther H.-O., 2011. A heuristic based on Vogel's approximation method for sequencing mixed-model assembly lines, International Journal of Production Research, 49 (21), 6451-6468, http://doi.org/10.1080/00207543.2010.527384.
• 6. Hitchcock F., 1941. The Distribution of a Product from Several Sources to Numerous Localities, Journal of Mathematics and Physics 20(1-4), 224-230, http://doi.org/10.1002/sapm1941201224.
• 7. Jude O., Ifeanyichukwu O., Ihuoma I., Akpos E., 2017. A New and Efficient Proposed Approach to Find Initial Basic Feasible Solution of a Transportation Problem. American Journal of Applied Mathematics and Statistics 5 (2), 54-61, http://doi.org/10.12691/ajams-5-2-3.
• 8. Karagul K., Sahin Y., 2019. A novel approximation method to obtain initial basic feasible solution of transportation problem. Journal of King Saud University - Engineering Sciences. http://doi.org/10.1016/j.jksues.2019.03.003.
• 9. Kasana H., Kumar K., 2013. Introductory Operations Research: Theory and Applications, Springer Berlin Heidelberg. http://doi.org/10.1007/978-3-662-08011-5.
• 10. Khan A., Vilcu A., Uddin S., Istrate C., 2016. The performance evaluation of various techniques for transportation problem, Buletinul Institului Politehnic Iaşi 62(1-2), 19-30.
• 11. Liu C.-H., Trung L., 2013. The Study of Using LP to Solve Flower Transport Problem, Journal of Convergence Information Technology 8(8), 1116-1124, http://doi.org/10.4156/jcit.vol8.issue8.133.
• 12. Ratner B., 2009. The correlation coefficient: Its values range between +1/-1, or do they? Journal of Targeting, Measurement and Analysis for Marketing 17(2), 139-142, http://doi.org/10.1057/jt.2009.5.
• 13. Reeb J., Leavengood S., 2002. Transportation problem: A special case for linear programming problems, Oregon State University Extension Service, EM 8779.
• 14. Reinfeld N., Vogel W., 1958, Mathematical programming, Prentice-Hall.
• 15. Russell E.J., 1969. Letters to the Editor Extension of Dantzig's Algorithm to Finding an Initial Near-Optimal Basis for the Transportation Problem, Operations Research 17 (1), 187-191. http://doi.org/10.1287/opre.17.1.187.
• 16. Salami A., 2014. Application of Transportation Linear Programming Algorithms to Cost Reduction in Nigeria Soft Drinks Industry, International Scholarly and Scientific Research & Innovation 8(2), 416-422.
• 17. Sharma G., Abbas S., Gupta V., 2012. Solving transportation problem with the various method of linear programming problem, Asian Journal of Current Engineering and Maths, 81-83.
• 18. Shenoy G., Srivastava U., Sharma S., 1986. Operations Research for Management. Wiley Eastern. ISBN 0-85226-917-X.
• 19. Soomro A., Tularam G., Bhayo G., 2014. A comparative study of initial basic feasible solution methods for transportation problems. Mathematical Theory and Modeling 4(1), 11-18.
• 20. Tiwari N., Shandilya S., 2006. Operations Research. PHI Learning. ISBN 13: 9788120329669.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).