離散最適化とその応用

第6回 区別画定問題のモデル化と最適区別の導出
根本 俊男，堀田 敬介
l………ll＝‖‖‖‖＝‖‖＝‖＝‖‖＝＝＝‖＝‖‖＝＝‖‖‖‖‖＝‖‖＝‖‖＝‖………‖‖‖‖‖‖‖‖‖＝＝‖‖＝‖＝＝‖‖‖‖‖＝‖‖＝‖‖‖‖‖‖‖‖‖＝‖‖＝‖‖‖‖‖‖‖‖‖‖＝＝＝＝‖‖‖＝‖‖‖‖‖＝‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖＝‖‖＝＝‖‖川…州l…‖＝‖‖＝＝‖‖岬的取り組みを遠ざけたのではないだろうか．もう一つ

1．はじめには，たとえ適切な数理モデルを作成しても，その最通日本の衆議院議員選挙は1994年に法改正がなされ解導出が困難な点である．これは近似解法での近似解小選挙区比例代表並立制により実施されている．小選

では政治的意味がなく［7］，厳密な意味での最通解の挙区制実施に必要な300小選挙区の良い区別を見つけ提示が重要との問題国有の背景に起因する．前者の困る問題を小選挙区区割問題と呼ぶことにする．この間

難性は，モデル化の作業とその適用結果の検証を実験

題の良い区別は，1票の格差，つまり，全選挙区中で的に繰り返すことで，より適切な方向で解決可能であ

最も人口の多い選挙区の人口と最も人口の少ない選挙

ろう．しかし，この反復に必要な最適解を導出する手区の人口の比が2倍未満と特徴付けられる．よって，軽なツールは存在しない．ただ，最近のいくつかの取この間題は1票の格差を2倍未満にする300地区へのり組みによって，技術的な困難性は随分克服されよう

地域分割を見つける数理モデルと大局的に捉えられる．としている［11］．結果的に，前者の問題の明確化の作

ただし，都道府県をまたぐ選挙区設定は制度上想定さ業にも良い影響が出始めている．

れていないので，各都道府県での地域分割と捉えるほ

ここでは，区割画定問題をどのように捉え，技術的うが適切だろう．この場合は，各都道府上削こ何議席をな面の困難性をどのように乗り越えようとしているの配分すべきかという定数配分問題と，与えられた議席かのアイディアを中心に解説してみたい．

数から選挙区をどのように設定するかの区割画定問題の二つが絡む問題として少なくとも認識しなくてはな

2．数理モデル化
初めに，区割画定問題を明確化し，それを基に二つらない．
前者の定数配分問題に対しては，ORや公共政策のの数理モデルを紹介する．

分野等で様々な観点から取り組まれ，多くの知見が得

2．1区割画定問題られている［1，12］．一方，後者の区割画定問題に関まず，区別画定問題を把握しよう．区別画定の作業しての数理的な知見は少ない．そのためか，小選挙区は，法律により設置された衆議院議員選挙区画定番議

区割問題に対する議論の多くが定数配分問題に偏り，会が区割実の作成方針に則り行う（［9］参照）．その主区割画定問題に対する理論的な基盤整備を行わなけれな方針は以下の通りである．

ば，バランスの良い制度発展が望めない状況である．
なぜ，区割画定問題に対し数理的な取り組みが少な

方針（1）1票の格差は2倍未満が基本．
方針（2）市区郡は分割しない．

かったのだろうか．原因は様々考えられるが，主に二方針（3）選挙区内で飛び地を作らない．

つの困難性を指摘できる．

方針（4）地域のつながりを考慮する．

一つは，実際の区別作成では原則的な方針のみで行われ，ルールの曖昧さが数理他にも，1選挙区に許容される人口のヒ下限制約や一モデルとの溝を作っている点である．この暖味な部分つの市区郡を分割する場合の方針などもある．この作を，政治的・制度的な解釈を確認しながら悪意性のな成方針にはあいまいな点が見受けられる．そこでまずい形で明確化していく困難な作業が避けられず，数理は単純に問題を把握し，それを適切なものへ段階的にねもと としお，ほった けいすけ
文教大学情報学部〒253−8550茅ヶ崎市行谷1100
300（50）

修正する手法を採る．ここでは，最も単純な形での問題把握を紹介する．
まず，区割画定問題に議論を集中させるために各都© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

道府児への定数配分数は与えられたと仮定し，方針（1）

和田が最初だろう［7］．区割画定問題の重要性を指摘を次の目的に読み替える．

し，選挙区数の少ない県での最適区割を提示した．最目的（1）′都道府児内で，1票の格差を最小．

近，モデル化が明確な24照に議論を絞り，選挙区のこの読み替えにより，与えられた定数配分の下で1票形状を制限する手法での区別も導出している［8］．たの格差が最小の区割を求めることになる．それが2倍だし，この制限のため，最適性の保障はない．

未満であれば方針（1）とは矛盾しない．次に方針（2）は，過去の取り組みを参考に，新たにいくつかのモデル市区郡を一つの要素として扱えば自ずと満たされる．

化を考えてみた．その中で実験的に良い結果を出した

方針（3）は，各市区部間に行政界での隣接関係を定め，集合m分割型モデルとグラフ分割型モデルの二つを選挙区は連結な市区郡で構成すると読み替えればよい．

ここでは採り上げる．どちらも組合せ最適化問題としさいごに，方針（4）は，地勢，交通，歴史的沿革などのて表現している点で共通している．しかし，制約1の自然的社会的条件を総合的に考慮すると政治的に解釈選挙区内の連結性を入力段階で強制するか，制約条件される．しかし，ここでは方針（3）で方針（4）も満足させとして強制するかの点で大きく異なる．

たと捉え，島のように行政界の隣接だけでは説明不足

2．3 集合m分割型モデルが生じる場合に限り交通のつながりを補完的に隣接と初めに，集合分割問題［5］を基にした集合研分割型

みなし地域のつながりとした．さらに選挙制度の基本モデルを示そう．まず，制約1を満たす市区郡の集合的な設定を加味し，都道府県毎の区割画定問題は次のをブロックと名付ける．つまりブロックは選挙区の候ように記述できる．

補である．すべてのブロックの集合をβで表す．ブ

入力：市区郡集合V＝（〃1，‥・，〃乃），市区郡の隣接関

ロック集合男から選んだ∽個のブロックが制約2を係g＝（（〃z，〃J）「市区郡〃ォと彷は隣接），各市区郡の人満たすと，実行可能な区別となる．その中で1票の格口動（Z＝1，‥・，乃），選挙区数∽（＜乃）．

差が最小な区別を見つけるのが集合∽分割型モデル

出力：1票の格差が最小の区割．

である．

制約1：選挙区は連結な市区郡で構成する．

入力データ：市区郡集合V，選挙区数糀，ブロッ

制約2：すべての市区郡は唯一つの選挙区に属す．

ク集合男を表す行列［あゎt才∈〃，ノ＝1，…，上割］：市区制約3：選挙区数は肌．

郡〃ォがブロックノの構成要素のとき∂ゎ＝1；そうで2．2 様々なモデル表現ないとき∂ゎ＝0，ブロックノの人口射＝∑ォ∈〃れ動（ノこの間題を表現する数理モデルは複数考えられる．

＝1，‥・，l割）．

今までにも，いくつかのモデル化とその解法が提案されているので紹介しよう．

変数：一つの選挙区の人口上限を示す変数㍑，下限を示す変数J，（0，1ト変数JJ（ノ＝1，…，博一）：区別に

まず，集合分割問題としての古典的なモデル化があ

ブロックノを健闘するときェノ＝＝1；しないときェJ＝0．

る［5］．ただし，最適解導出は実際には難しし−だろう．
次に，最小∽全域森問題［3］やグラフ頂点分割問題［10］としてのモデル化がある．いずれも分枝限定法で最適解導出を試みているが，たかだか5選挙区までが限界であった．また，いずれのモデル化でも選挙区の中心市区郡を事前に指定する悪意性が存在し不満である．ニューラルネットワークを利用した取り組みがあるが［6］，近似解法である．上記で紹介した取り組み

図14市区郡の例とそのグラフ表現（V，g）

はすべて解法の性能評価の一環である．区別画定問題に正面から向かった研究としては，コンパクト性という選挙区の形状制限を導入し，列生成法を用いて解を導出するというアメリカでの取り組みが興味深い［2］．
しかし，区割線をある程度自由に設定可能というアメリカの制度を本質的に利用しているため，日本には通さない．日本の小選挙区区割への取り組みは，坂口・
2003年4月号

巨二≠転三惑
図2 例に対するブロック集合男© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（51）301定式化：
1
2

min．〟／J，I動）

3s．t．ヴノみ≦〟（ノ＝1，‥・

4

α（1−JJ）十￠J∬J≧／（ノ＝1，…，】剰）∑ ∂ゎェノ＝1（才∈Ⅳ）ノ＝1，・＝，し創∑．′・、／ノ／
ノ＝1，・・・，卜創

JJ∈（0，1）（ノ＝1，…，一別）
ここで，αは十分大きな定数，Ⅳ＝（1，…，乃）とする．

図3 例に対する2選挙区の場合の拡大有向グラフ

さて，条件式（4）〜（6）は制約2と3を表現している．
すべてのブロックは制約1を満たしているので，実行可能解Jから導かれる別個のブロックは実行可能な区別である．条件式（2），（3）は使用するブロックの人口定式化：

min．〟／／

8

示し，区別画定問題を表現している．

ときz摘＝0．
7

上∴F 限制約なので，目的関数式（1）は，1票の格差を点〃㌘に流れ込むフローの和が正のときz沌＝1；0のs．t．／≦∑丸尾・烏≦〟（々∈〃） J∈一Ⅳ

このモデルの長所は，表現が容易な点と，〟タ困難∑／（α）＝ ∑／（α）（才∈Ⅳ，点∈〟）のクラスに属す問題であるが，実際には中規模サイズ〟∈∂むさ程度なら最適解を発見しやすい点である［4］．一方，／（α）≧0（α∈耳）

短所は，各都道府児においてブロック数l月lが大きな／（（s々，〃㌘））＝励gた（才∈Ⅳ，々∈〃）llり∑〝沌＝1（々∈〟）〜∈〃神奈川児では少なくとも21億個以上のブロックが存〝沌∈（0，1）（g∈Ⅳ，カ∈〟）在する．

∑／（α）≦ノおど烏（オ∈Ⅳ，々∈〝）〟∈∂▼uヂ

2．4 グラフ分割型モデル
次に，グラフ上にフローを流すことで制約1を満足させるモデルを提案する．まず，モデルの基になるネzg烏≦／（（〃㌘，J∠））（才∈Ⅳ，々∈〟）（19∑zざ烏＝1（ダ∈Ⅳ）（咽々∈Jlすットワークを定義したい．市区郡集合Vとその隣接z摘∈（0，1）（ダ∈Ⅳ，々∈〟）

関係且のペア（V，且）は無向グラフである．このグラ

ここで，∂十〃（∂￣〃）は，点〃から出る（に入る）枝集フの無向枝を互いに逆向きの2本の有向枝に置き換え合を示す．

た有向グラフを（Ⅴ，』）とする．この有向グラフを沼

条件式の役割を見てみよう．初めに，条件式（9），（10）個複製し，各々を（Vカ，A烏）＝（（〃錮∈Ⅳ），（α烏lα∈A））はフロー条件である．各点s々からT側にフローは流（々∈〟）と表す．ここで，〟＝（1，…，研）である．まれる．続く条件式（11）〜（用で，流れるフローを二つの方た，これとは別に点集合5＝（ぶ烏l々∈〟），枝集合Aざ々針で制御する．まず，条件式（11）−（1頚で，グラフ（V烏，＝（（5た，〃ヂ）け∈Ⅳ）（々∈〝）と，点集合r＝（帰∈Ⅳ），月々）のちょうど1点にsんからβのフローが流入する

枝集合Aif＝（（〃㌘，′ォ）】々∈〃）（オ∈Ⅳ）を準備する．これよう制御している．次に，条件式（14）〜（川で，点〃ヂにらを，点集合▽＝∪烏∈〃V烏∪5−Ur，枝集合A＝

流入する正の値のフローがあれば，必ず枝（〃ヂ，f才）に∪烏∈〃（月融UA々）リリォ∈〃Aiととまとめ，拡大有向グラも正の値のフローが流れるように制御している．ただフ（▽，耳）を定める．さて，この拡大有向グラフを基し，条件式（i鋸こより，各枝集合Aff（オ∈Ⅳ）の中でフに，各校の容量は十分大きいという情報を付したネッローが流れるのはちょうど1本ずつである．

トワーク〟を定め，次のようにモデル化を行う．
入力データ：ネットワーク〟，市区郡の人口か（オ

ここで，この定式化の実行可能解に対し，点部分集合βカ＝（〃ilz摘＝1）（点∈〟）を定めよう．フローの制御により，集合β烏は非空で，互いに疎で，∪紘〟β烏∈Ⅳ），十分大きな流量β．
変数：枝α∈Aに流れるフロー／（α），（0，1ト変数＝Ⅴなので，区別画定問題の制約2と3を満たす．

y∠々（∠∈Ⅳ，点∈〟）：枝（5た，〃㌘）のフローが正のとき〝沌

さらに，条件式（摘よりフローが流入しない点でz葎＝1＝1；0のとき〟摘＝0，（0，1）一変数る・烏（オ∈Ⅳ，々∈〟）：にはならず，隣接関係に沿ってのみフローが流れるの

302（52）i数になりやすい点である．例えば，49市区郡を持つ〟∈∂十びさ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ（叩で，集合β々は制約1の連結性も満たしている．条件

人口の少ない選挙区を防ぐための分割：ある市区郡

式（8）が各β烏の人口の上・下限制約になっていることを分割しない限り近隣の選挙区人口が理想人口の2／3から目的関数は1票の格差を最小にしており，これもを下回る場合も例外事項で分割が許される．これは，区別画定問題の数理モデルとなる．

上記とは異なり分割をする前の最適区割を見て判断さこのモデルの長所は，過去のグラフ利用のモデルでれるべき処置で，最適区別の情報がないときは悪意性は必要な事前指定の中心市区郡が不要のため悪意性がが入る余地がある．ここでは，分割前の最適区別を基排除できている点にある．逆に短所は，†0，1卜整数変に千葉県の市川市，松戸市と三重照の四日市市などを数の数が2プ形作個と多い点である．素朴に分枝限定法該当させた．分割方式は，各市の地区情報を利用するで解こうとすると多くの計算時間を要す．例えば，25

手段もあるが，選挙区を共有すべき市区郡とで理想人市区郡の島根県の最適な3選挙区を見出す比較的小さ口になるように一方を定め，残りの人口を該当市に割なサイズの問題でも約37時間を費やした．

り当てた．
隣接関係：市区郡集合の要素の行政界が陸上で隣接

3．実際の問題への適用している場合に隣接関係をまずは定めた1．四つ以上

現実の300小選挙区区割画定に二つの数理モデルをの市区郡が1点で行政界を共有するという事例がある

適用したい．ここではその準備に関する取り組みと工が，その場合は隣接していないとした．陸上以外でも，夫を紹介する．

橋（道路）で結びついている場合は隣接とみなした．

3．1入力データの準備

島の場合は，飛行機または船での定期的な交通機関がまず，入力データの準備方法を概説する．区割画定存在する場合にその2市区郡間を隣接とみなした．の作業は国勢調査の速報値が発表されたのを受け実施

3．2 目的関数の変更されると定められている．そのため，2000年10月が区割画定問題では，1票の格差，つまり比の最小を目的としている．一般的に比を最小にする問題の場合データの時間的な基準になる．

市区郡集合と人口：基準時に実在する市区郡（北海には，パラメータを用い子問題を作り，それを何度か道のみ郡ではなく支庁）が要素になる．東京23区に解く必要がある．しかし，子問題でも解導出に時間を限らず横浜市などの政令指定都市の区も一つの要素と費やす本問題では困難を生じる．実は，本間題の性質した．ただし，一つの市区郡が地理的に分断されていから，最小差を達成する区別が，最小比も達成している場合は，各々を別な要素とする．そのため，実際のるかを判定する条件を導くことができ，最小比でない市区郡数と入力データの市区郡数は一致しない．各要ときに限って，探索範囲を限定した最小差の問題を解

素の人口は区割方針に従い2000年国勢調査の速報値き直すアプローチが可能である．そこで，実際には目を用いた．

的関数を最小差：祝−Jと変更する工夫で由難を回避

人口の多い市区の分割：方針（2）により基本的に市区した．

郡は分割しない．しかし，一つの市区で都道府県の3．3 ブロックの列挙（または全国の）議員1人当たりの人口（以後，理想集合研分割型モデルで用いるブロック集合男を準人口）の4／3を超える場合は分割を行うとの例外事項

備するには，無向グラフ（V，g）上で連結な部分グラがある．判断基準は明確だが，どのように分割するかフを列挙すればよい．列挙は，再帰呼出し型解法で可が問題になる．ここでは，該当市区にまずは理想人口能である（［4］第14章参月齢．しかし，実際に数え上を持つ1選挙区（さいたま市のみ2選挙区）を仮想的げると市区郡数の少ない県でもブロック数は膨大になに割り当て，該当市区は残りの人口を持つ要素で残しる．そこで，入力に月］いるブロックの選別を行う．

た． この方法だと，該当市区は一つの選挙区を他と共まず，最適解の最大人口より大きい保障のある上限有するが，残りの選挙区は独自に持つ．この方法の利びと最小人口より小さいとの保障のある下限上を定点は，分割される部分がどこと選挙区を共有するかにめる．これらを定めるには現在の区別や近似解法での悪意性が入らない点だ．欠点は，事前に割り当てる人解を参考に導出してもよいし，区割方針の分割規定に口を理想人口と決めている点だ．この欠点は，割当人
口をパラメ岬タとしてモデルに導入する方法で対処できる．
2003年4月号

1公式な市区郡の隣接関係デ岬タは著者が知る限り存在しない．デジタル地図は行政界のずれがあり利用できず，手作業で定めた．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（53）3tほある，上限Uは理想人口の4／3倍，下限エは理想人

見できたら，その点に関しては変数固定作業が可能と口の2／3倍と定めてもよい．打と⊥の差は小さいほなる．

うが好ましく，様々な工夫が必要な点である．このでは，ある点と同一のブロックにはならない点はど

打と⊥の間の人口を有するブロックを第1妥当ブロのように探せるだろうか．一つの方法は，グラフ上でックと呼ぶ．定義より，人力データを第1妥当ブロッ

その人口の上限以内で到達可能な点集合を限定する方

ク集合に制限しても元の問題と最通解は同じである．

法がある．または，第2妥当ブロックの情報を利用す

この選別で，多くの都道府児では数千〜数十万個にブる方法も考えられる．

ロック数が減少するが，まだその数は多い．

どちらかのモデルでよりよい実行可能解が得られる

さらに，ブロックに属する市区郡の組合せで選別をと，それを利用して，第2妥当ブロック集合の縮小化行なう．ある第1妥当ブロックβとそれに接続するとグラフ分割型モデルで固定する変数の数の増加が期枝をグラフ（Ⅴ，g）から除くと，残ったグラフが非連待でき，問題が解きやすくなると考えられる．計算機

結になるときがある．残った連結部分の一つが人口下実験では実際に両モデルでの途中の情事艮を双方で活用

限⊥を下回ると，元のブロックβは実際には実行可し，解導出を高速化した．

能解として利用はできないと判断できる．第1妥当ブ

4．全都道府県の最適区割

ロック集合からそのようなブロックをすべて除いたものを，第2妥当ブロック集合と呼ぶ．このアイディア

計算機実験で実際に1票の格差が最小になる区割をの延長で，人口上限Uを利用した選別方法などもあ導いた．最も単純な問題把握での結果ではあるが，全るが省略する．この選別は有効で，数十一数万ブロッ

300選挙区の最適な区割を導出した初めての結果であクまで減少する都道偏：児が出てくる．この程度のブロる．

ック数だと，集合∽分割型モデルで実際に最適解を計算できる段階に入る．

今回は，区割画定問題にどのような数理的アプロー
チが適切かに主眼があったので，モデル毎に特化したところで，実際に最適な区割に利用するブロックだ解法ではなく，ILOG社のソルバーであるOPL−けの集合を妥当ブロック集合と呼ぼう．妥当ブロックStudio（ver．3．1）を利用した．使用計算機は集合を様々な工夫で求めることができれば，相当効果

PentiumIII800MHz，メモ7）512Mである．解導出があるという気持ちになってくるが，それは難しい．

までの時間制限はCPU利用時間で12時間とし，そなぜなら，もし妥当ブロック集合が得られたら，そこれ以内で最適解を導出した場合に問題例を解いたと判から1票の格差の最小が計算でき，〟クー完全のクラ断した．実際は一度解けば十分なので長時間をかけ判スに属す問題に答えたことになる．妥当ブロック集合

断してもよいが，10時間程度で解を出さない場合はを包含し，なるべくサイズの小さいブロックの集合をメモリーのオーバーフローなどハードウェアからの制時間をかけずに見つける程度に努力をとどめておいた

限で解の導出に失敗することが多かった．

ほうがよい．

2002年に改定された実際の区割（2002年区別）と3．4 グラフ分割型モデルでの前処理

本実験で求めた区割（最適区割）の都道府児毎の比較

グラフ分割型モデルの欠点は（0，1ト変数の多さで，を表1に示す．表中の「分割」とは，市区郡の分割数

計算機実験でも少し大きなサイズの問題になると最適である．2002年区割では全国で23市区郡を分割して解を出すまでに長時間かかる．そこで，この（0，1ト変いるが，作成方針に素直に沿った最適区別では19市数のいくつかを事前に0か1に固定したい．いくつか区郡の分割で済んでいる．この差は興味深い．また，の固定は簡単である．例えば，グラフ（Vi，Al）には表中の「解法」では，時間的に早く求めたモデルを枝（sl，〃壬）からフローが流れると最適性を失わず仮定

SP（＝集合m分割型）とGP（＝グラフ分割型）でできる．この仮定より，〝11＝1，〝1々＝0（々＝2，・‥，∽）示した．各モデルでの最適解導出までの時間は数秒かと固定できる．ただし，これ以外の固定は自明ではな

ら約7時間と幅が広かった．

い．グラフ（Vl，』1）以外のグラフではどの点にフロ全国での比較を表2で示す．都道府児毎にすべてのーが流入するか定まらないからだ．しかし，グラフ選挙区人口が等しい区割（理想の状態）は困難なので，（Vl，Al）では点〃fを始点に連結成分を探しているの現在の定数配分で1．778倍を下回る区別はありえない．

で，もし点〃fとは同じブロックにはならない点を発

2002年区別の1票の格差は2倍を超え問題とされて304（54）

オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

表1都道府倶毎の1票の格差：2002年区別と最適区割との比較
2002年区割

最適区割

最大人口 最小人口 1票の格差 分割 最大人口 最小人口 1実の格差 分別 解法

北海道 63 5682950 12 473579 547931 357860 1．531 一 526639 359526
青森県 20 1475635 4 368909 440232 306507 1．436− 402408 331999
岩手県 30 1416198 4 354050 387811 325128 1．193 − 356696 350520
宮城県 31 2365204 6 394201 508847 289877 1．755 − 429750 351141

1．465

秋田県 18 1189215 3396405 469672 336584 1．395

山形県 24 1244040 3
福島県 27 2126998 5
茨城県 43 2985424 7
栃木県 23 2004787 5
群馬県 27 2024820 5
埼玉県 60 6938004 15
千葉県 48 5926349 13
東京都 56 12059237 25
神奈川 49 8489932 18
新潟県 48 2475724 6

414680 444542 383531 1．159

富山県 17 1120843 3
石川県 18 1180935 3
福井県 18 828960 3
山梨県 19 888170 3
長野県 40 2214409 5
岐阜県 36 2107687 5
静岡県 39 3767427 8
愛知県 66 7043235 15

三重県 32 1857365 5
滋賀県 21 1342811 4
京都府 36 2644331 6
大阪府 64 8804806 19
兵庫県 53 5550742 12

奈良県 19 1442862 4
和歌山 16 1069839 3
鳥取県 11 613229 2−SPl．212−

GP

l．018

−SP

l．224

−

SP

− 420746 382840

l．099

−

GP− 415552 413565

l．005

−

GP425400 542573 325422 1．667− 436690 412832

l．058

−

SP426489 513647 292777 1．754− 438192 378631

l．157

−

SP400957 494447 307100 1．610− 443787 382598

l．160

−

GP404964 485045 353001 1．374

1 423106 394737

l．072

−

SP462534 533254 390968 1．364

1 474223 430912

l．101 1 SP455873 550079 374264 1．470

2 464418 443979

l．046 3 SP482369 551364 376789 1．463

5 536000 421504

l．272 5 SP471663 538502 338895 1．589

1 528821 417838

l．266 1 SP412621 527271 363043 1．452− 527271 388198

l．358

373614 478756 316394 1．513− 381907 363538

l．051 −

GP393645 456434 334780 1．363− 456434 334780

l．363

−

GP

276320 278754 273700 1．018− 278754 273700

l．018

−GP

296057 308132 280331 1．099− 296643 295714

l．003−GP442882 536492 317922 1．687− 443547 442346

l．003

−SP

−

SP−421537 508662 361557 1．407− 431628 417842

l．033

470928 555997 394127 1．411

2 512807 443878

l．155 1 SP469549 539164 328877 1．639− 482687 460403

l．048−SPSP371473 405472 295836 1．371

1 379355 353176

l．074 1 SP335703 365234 284170 1．285− 349980 324384

l．079−GP440722 539209 333621 1．616− 442941 437779

l．012−SP463411 540057 376428 1．435

1 515055 376428

l．368 1 SP

462562 558947 392322 1．425− 505892 419842

l．205−360716 373107 345046 1．081− 366196 357309

l．025

−GP

356613 389519 293819 1．326− 386501 327477

l．180−GPSP

306615 328711 284518 1．155

1 307014 306215

l．003 1 SP

島根県 25 761499 2
岡山県 32 1950656 5
広島県 43 2878949 7
山口県 30 1528107 4380750 402319 359180 1．120− 380877 380622

l．001 −

390131 442154 351781 1．257

1 430239 377590

l．139 1 GP411278 480070 383451 1．252

1 427485 404818

l．056

−

SP382027 447897 344572 1．300−l．018−SP

徳島県 15 823997 3
香川県 16 1022843 3
愛媛県 28 1493126 4
高知県 19 813980 3274666 280273 271132 1．034

1 279701 271132

l．032

−

GP340948− 372585 327195

l．139

−

GP

− 479737 328647
2 271344 2712t）3

l．460

−

GP271327 271944 270743 1．004

l．000 2 GP

福岡県 57 5015666 11455970 521113 342052 1．523− 465803 4376（）1l．064

佐賀県 21 876664 3
長崎県 22 1516536 4
熊本県 24 1859451 5
大分県 27 1221128 3
宮崎県 20 1170023 3
鹿児島 35 1786214 5
沖縄県 21 1318281 4292221 296774 288940 1．027

1 306629 283683

l．081 −GP379134 450080 276098 1．630− 450080 317646

l．417

GP371890 458483 318321 1．440

1 396596 318321

l．246 1 GP407043 436490 386266 1．130
390008 422157 370788 1．139357243 413406 321725 1．285− 436490 389220− 392845 387415
1 366697 340165− 344405 321131

l．121 −GP

l，014

GP

2003年4月号

372585 312484 1、192373282 473397 317655 1．490

329570 353686 315800 1．12386749 3797∠15© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

−−−

GPSP

l．078 1 SPl．072−

GP（55）305

表2 全国人口格差：2002年区割と最適区割の比較貸していただければ幸いである．

理想の状態 2002年区割 最適区割
最大人口
最小人口

482369271327

1票の格差 1．778

558947536000270743271132

2．064

1．977

謝辞 本研究の取り組みを迅速に公表する機会を与えて下さった毛利裕昭氏（早稲田大学），および原稿に対し有益なコメントを寄せていただいた塩浦昭義民（東北大学），宇野毅明氏（情報学研究所）に感謝します．

いるが，最適区割から2倍未満が達成できることが明
参考文献

らかになった．2002年区別が2倍未満を達成できな
かったのは定数配分のまずさが原因との多くの主張は数理的に正しくはないことが確認できる．

［1］M．L．Balinskiand H．P．Young：nlir R＠yt？Senta−
Jわ乃2〃dβd，Brookings，（2001）．

［2］A．Mehrotra，E．JohnsonandG．L．Nemhauser：An

5．おわりにoptimization based heuristic for politicaldistrictlng，

ここでは離散最適化の手法を用いて，300選挙区すべての区別を求めるまでの流れを説明した．全都道府県での最適区別の導出に成功したポイントは，一つのアプローチにこだわらず様々なモデル化を採用し，ハイブリッドに用いた点にある．逆に，一つの手法です
べての都道府県の解を導出することは現在の技術段階ではまだ難しい気がする．従来の取り組みでは一つの解法にこだわっていた点が小選挙区の区割画定問題の解決を遅らせたのかもしれない．ただし，現在の離散最適化の手法の進展は目覚しく，強力な手法が登場す〃α乃（郡∽e邦吉Scブβ乃Ce，44−8（1998），1100−1114．

［3］T．Yamada，H．Takahashiand．S．Kataoka：AbranchLand−bound algorithmforthemini−maXSpan−ningforestproblem，Eu7てゆeanhumal〆輝eYtlttOnal
斤esβα化ゐ，101（1997），93−103．
［4］久保幹雄，田村明久，松井知己編：応用数理計画ハンド
ブック，朝倉書店，（2003）．
［5］今野浩，鈴木久敏編：整数計画法と組合せ最適化目科技連，（1982）．
［6］斎藤孝之，武藤佳恭：′卜選挙区区割り問題，βれ28−7（1996），88−91．
［7］坂口利裕，和田淳一郎：選挙区割りの最適化について，る可能性は強いだろう．
最適区割の導出という点では一つの階段を上ったが，区別画定問題の数理的なアプローチとしてはまだ入口に立っただけである．政治的・制度的な観点から数理モデルの適切さを追求する必要がある．そのためには，条件を変えたモデルでの計算機実験の高速化が望まれ

三田学会雑誌，93−1（2000），109−137．
［8］坂口利裕，和田淳一郎：選挙区割り問題，オペレーショ
ンズ・リサーチ，48−1（2003），30へ35．

［9］田中宗孝：政治改革6年の道程，ぎょうせい，（1997）．
［10］烏井修：グラフ上の頂点分割問題，束京大学修士論
文，（1995）．

る．グラフの平面性など問題の持つ樟殊性をまだ利用［11］根本俊男，堀田敬介：区割画定問題に対する数理的アしてなく，各モデルに特化した解法の提案で高速化のプローチ，2002年日本OR学会春季研究発表会アブスト余地はかなりある．また，区割の画定がスムーズにサラクト集，（2002），58−59．

ポートできれば，区別情報を基にした定数配分方式が［12］大和毅彦：議員定数配分方式について一定数削減，人考えられる．小選挙区区別問題への新しい切り込みも口変動と整合性の観点から−，オペレーションズ・リサ可能だろう．この研究に興味を持っていただき，力をーチ，48−1（2003），23−29．

オペレーションズ・リサーチ

306（56）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.