### Abstract

Original language | English |
---|---|

Pages (from-to) | 115-126 |

Number of pages | 12 |

Journal | Computers & Industrial Engineering |

Volume | 82 |

Early online date | 28 Jan 2015 |

DOIs | |

Publication status | Published - Apr 2015 |

### Fingerprint

### Keywords

- Linear programming
- Transportation problem
- Heuristic-exact hybrid algorithm
- Negative dual rectangle
- Negative sets
- Transportation greedy heuristics

### Cite this

*Computers & Industrial Engineering*,

*82*, 115-126. https://doi.org/10.1016/j.cie.2015.01.018

**A new hybrid algorithm for the balanced transportation problem.** / Sabbagh, Mohammad; Ghafari, Hosein; Mousavi, Seyed Rasoul.

Research output: Contribution to journal › Article

*Computers & Industrial Engineering*, vol. 82, pp. 115-126. https://doi.org/10.1016/j.cie.2015.01.018

}

TY - JOUR

T1 - A new hybrid algorithm for the balanced transportation problem

AU - Sabbagh, Mohammad

AU - Ghafari, Hosein

AU - Mousavi, Seyed Rasoul

PY - 2015/4

Y1 - 2015/4

N2 - We propose a heuristic-exact hybrid algorithm that consists of a heuristic phase, based on two novel heuristics, followed by an exact phase, based on an adapted Ford–Fulkerson algorithm, to solve the Balanced Transportation Problem (BTP). First, we propose three alternative primal models for the BTP. We also define the concepts of negative sets, negative dual rectangles, and the optimal tableau for the BTP. Next, we explore the relationships between these concepts. We also propose two greedy heuristics, based on a linear programming relaxation of the BTP model, to find some negative sets and negative dual rectangles. These two heuristics turn out to be very efficient and obtain optimal or near-optimal BTP tableaus rapidly, as confirmed by the computational experiments. Then, an adapted Ford–Fulkerson algorithm is presented and used to find an optimal solution. The two important advantages of our adapted Ford–Fulkerson algorithm over the standard Ford–Fulkerson algorithm are more flexibility and efficiency. Extensive computational results show that the growth in run-time of our hybrid algorithm, on average, is approximately a linear function of the BTP size. It has significant advantage over the transportation simplex method and on the largest problem instances it is almost five times faster. A key feature of the proposed algorithm is that it is free of degeneracy and cycling altogether.

AB - We propose a heuristic-exact hybrid algorithm that consists of a heuristic phase, based on two novel heuristics, followed by an exact phase, based on an adapted Ford–Fulkerson algorithm, to solve the Balanced Transportation Problem (BTP). First, we propose three alternative primal models for the BTP. We also define the concepts of negative sets, negative dual rectangles, and the optimal tableau for the BTP. Next, we explore the relationships between these concepts. We also propose two greedy heuristics, based on a linear programming relaxation of the BTP model, to find some negative sets and negative dual rectangles. These two heuristics turn out to be very efficient and obtain optimal or near-optimal BTP tableaus rapidly, as confirmed by the computational experiments. Then, an adapted Ford–Fulkerson algorithm is presented and used to find an optimal solution. The two important advantages of our adapted Ford–Fulkerson algorithm over the standard Ford–Fulkerson algorithm are more flexibility and efficiency. Extensive computational results show that the growth in run-time of our hybrid algorithm, on average, is approximately a linear function of the BTP size. It has significant advantage over the transportation simplex method and on the largest problem instances it is almost five times faster. A key feature of the proposed algorithm is that it is free of degeneracy and cycling altogether.

KW - Linear programming

KW - Transportation problem

KW - Heuristic-exact hybrid algorithm

KW - Negative dual rectangle

KW - Negative sets

KW - Transportation greedy heuristics

U2 - 10.1016/j.cie.2015.01.018

DO - 10.1016/j.cie.2015.01.018

M3 - Article

VL - 82

SP - 115

EP - 126

JO - Computers & Industrial Engineering

JF - Computers & Industrial Engineering

SN - 0360-8352

ER -