2009年2月23日月曜日

巡回セールスマン問題を解く(4)

 予測していたように pgRouting の TSP 自明な3点以外でもエラーになる場合があった。しょうがないので、若干負けているが自前のルーチンを使う事にした。それで、厳密に都市間の距離を計算して勝負してみたが、それでも負ける(本当は勝っている、と言っても、こちらだけ厳密な距離を使用しているので、不公平な比較だが…)。
 何故負けるかというと、現在は配送問題も加えており(集荷と出荷の関係を持ち込む)、単純な最短巡回問題では無くなっているからだという結論に達した。出荷条件が整っていない場合に、その都市の順序を先送りするという方式を取っているが、こういう事をする場合には、むしろ不完全な解の方が先送りした結果良い結果を生むという皮肉な事態になっているようだ。
 という事で、都市間距離に加えて、配送問題も取り込む事にする。ブログへのポストは、この辺が潮時か…。

追記:距離の計算において、最終都市から起点都市への距離の追加が漏れていた。これを入れれば、元より勝っていたっぽい。

0 件のコメント: