An accelerated Benders decomposition algorithm for the multi-item fixed-charge transportation problem

Abstract

In today’s industrial and service sectors the role of transportation is unavoidable. Due to this importance, an optimized transportation plan with minimum transportation costs can be a favor for the managers. In this study a multi-item fixed-charge transportation problem with capacitated multiple transportation mode is considered. As such problem is of high degree of complexity, we focus on the Benders decomposition approach to solve it. For this aim, first the classical Benders decomposition approach is developed for the problem. This is the first time in the literature that the Benders decomposition algorithm is developed for this problem. In continue, as another novelty, an accelerated benders decomposition algorithm is developed for the problem by adding some valid inequalities to the classical Benders decomposition algorithm. These valid inequalities can effectively influence the performance of the classical Benders decomposition algorithm. Several test problems with various sizes are generated to test the proposed solution approaches. The test problems are solved by the classical branch and bound algorithm and the proposed classical and accelerated Benders decomposition algorithms. According to the obtained results the accelerated Benders decomposition algorithm performs better than others in terms of reporting optimal solution and CPU running time.