A new hybrid algorithm for the balanced transportation problem

Mohammad Sabbagh, Hosein Ghafari, Seyed Rasoul Mousavi

    Research output: Contribution to journalArticlepeer-review

    9 Citations (Scopus)


    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.

    Original languageEnglish
    Pages (from-to)115-126
    Number of pages12
    JournalComputers & Industrial Engineering
    Early online date28 Jan 2015
    Publication statusPublished - Apr 2015


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


    Dive into the research topics of 'A new hybrid algorithm for the balanced transportation problem'. Together they form a unique fingerprint.

    Cite this