On the effectiveness of primal and dual heuristics for the transportation problem

摘要

The transportation problem is one of the most popular problems in linear programming. Over the course of time a multitude of exact solution methods and heuristics have been proposed. Due to substantial progress of exact solvers since the mid of the past century, the interest in heuristics for the transportation problem over the past few decades has been reduced to their potential as starting methods for exact algorithms. However, in the context of ever increasing problem dimensions, a thorough cost-benefit analysis of exact methods versus heuristics is asked for. For this reason, this paper contributes an in-depth study of heuristics with respect to their performance in terms of computation time and objective value. Furthermore, we consider-to the best of our knowledge for the first time-simple efficient dual heuristics to obtain performance certificates based on weak duality without the need to solve the problem exactly. We test these heuristics in conjunction with state-of-the-art solvers on a variety of test problems. Thus, we especially close the gap to rather outdated comparative studies from the past century. For specific random test problems we extend previous approaches to provide a consistent and flexible problem generator for transportation problems with known solutions. Based on our numerical results, it can be concluded that primal and dual heuristics are able to rapidly generate good approximations for specific randomly generated problem instances but-as expected-are not able to yield satisfactory performance in realistic instances.