The transportation problem with exclusionary side constraints and two branch-and-bound algorithms

The transportation problem with exclusionary side constraints, a practical distribution and logistics problem, is formulated as a 0–1 mixed integer programming model. Two branch-and-bound algorithms are developed and implemented in this study to solve this problem. Both algorithms use the Driebeek penalties to strengthen the lower bounds so as to fathom some of the subproblems, to peg variables, and to guide the selection of separation variables. One algorithm also strongly exploits the problem structure in selecting separation variables in order to find feasible solutions sooner. To take advantage of the underlying network structure of the problem, the algorithms employ the primal network simplex method to solve network relaxations of the problem. A computational experiment was conducted to test the performance of the algorithms and to characterize the problem difficulty. The commercial mixed integer programming software CPLEX and an existing special purpose algorithm specifically designed for this problem were used as benchmarks to measure the performance of the algorithms. Computational results show that the new algorithms completely dominate the existing special purpose algorithm and run from two to three orders of magnitude faster than CPLEX.