A new hybrid algorithm for the balanced transportation problem

Mohammad Sabbagh, Hosein Ghafari, Seyed Rasoul Mousavi

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

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
Volume82
Early online date28 Jan 2015
DOIs
Publication statusPublished - Apr 2015

Fingerprint

Linear programming
Experiments

Keywords

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

Cite this

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

In: Computers & Industrial Engineering, Vol. 82, 04.2015, p. 115-126.

Research output: Contribution to journalArticle

Sabbagh, Mohammad ; Ghafari, Hosein ; Mousavi, Seyed Rasoul. / A new hybrid algorithm for the balanced transportation problem. In: Computers & Industrial Engineering. 2015 ; Vol. 82. pp. 115-126.
@article{73cf2c1578b44d9182fb6f6fd30f732d,
title = "A new hybrid algorithm for the balanced transportation problem",
abstract = "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.",
keywords = "Linear programming, Transportation problem, Heuristic-exact hybrid algorithm, Negative dual rectangle, Negative sets, Transportation greedy heuristics",
author = "Mohammad Sabbagh and Hosein Ghafari and Mousavi, {Seyed Rasoul}",
year = "2015",
month = "4",
doi = "10.1016/j.cie.2015.01.018",
language = "English",
volume = "82",
pages = "115--126",
journal = "Computers & Industrial Engineering",
issn = "0360-8352",
publisher = "Elsevier",

}

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 -