n-TSPメモ

ファジイc-means法を用いた複数巡回セールスマン問題の一解法より

k-tour splitting aigorithm

[STEP1]

全都市に対して、TSPを計算

⇒総経路長T、スタート地点と最も遠い拠点の距離Cmax

[STEP2]

1<=j

サブツアー長<(j/N)(T-2Cmax)+Cmax

を超えない最大の都市までが担当者jのサブツアー

[例]

拠点1⇒2⇒3⇒4⇒5⇒6⇒1

各拠点間すべて10

T=60

Cmax=18(1⇒4)

担当者3人

担当者1

(j/N)(T-2Cmax)+Cmax

=(1/6)(60-36)+25

=1/6*24+25

=4+25=29

担当者2

(j/N)(T-2Cmax)+Cmax

=(2/6)(60-36)+25

=8+25=33

担当者3

(j/N)(T-2Cmax)+Cmax

=(3/6)(60-36)+25

=12+25=37

疑問点

・担当者は29までのルートになるが1⇒2⇒3⇒1として3⇒1の距離は加算される？

・担当者2のルートは33までだが1⇒4⇒1は36だからルートを割り当てられない？

追記

・1⇒拠点⇒・・・⇒1でスタート地点から拠点と拠点からスタート地点も含めて計算（遺伝的アルゴリズムによる収集計画問題の解法より)