ここでいうハキミ問題とは、利用者全員の総移動距離が最小になるように施設を配置する問題です。
黄色い点と道路ネットワーク(赤)があるとします。黄色い点には施設の利用者が１人ずついるものとします。また、利用者は施設を利用する際、道路を使った最短の道で移動するものとします。この時、利用者全員の総移動距離が最小になるように施設を置く問題がハキミ問題(しばしばミニサム問題とも言います)です。
上では白い丸で囲まれた点が最適点となります。白い線はその最適点から各点への最短のネットワークをあらわします。
数学的に書くと、領域にn個の需要p(1),...,p(n)があるものとします。施設の場所をxとして、d(x,p(i))をxからp(i)までの道路ネットワークを利用した時の最短距離とします。この時、目的関数f
f=d(x,p(1))+...+d(x,p(n))
を最小にするようにxの位置を道路ネットワーク上に決める問題がハキミ問題です。ハキミ(Hakimi)はこの問題の答えが需要の位置p(1),...,p(n)のうちのどれかに少なくとも１つは存在することを示しました。このプログラムもその性質を利用して答えを求めています。答えを求めた後で、最短路問題を使って、各点への最短路を求めています。
●参考文献：日本建築学会編、井上書院、建築・都市計画のためのモデル分析の手法 ●Javaプログラムのダウンロード(haki.java 11KB)
ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。
●大山崇のホームページの利用について
●大山崇のホームページ