A comprehensive study of classical heuristic algorithms used in the process of solving Transportation Problem

Abstract

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.