ＥＸＣＥＬによる最長片道ルート探索

4. ＪＲ最長片道ルートの計算

（３）本州循環型最長片道ルート

次に起点と終点が同一の場合、即ち循環型の最長片道ルートを求めることとしたい。今迄と同様、本州を対象とし、経路には新幹線を含めることした。
この場合、循環型にするためには「青森、幡生を通る枝の数は1」という制約を「青森、幡生を通る枝の数は0又は2」と変更すればよい。
また、東北地方、東日本地方、西日本地方はそれぞれ3区間で接続しているが、今回は一つの地方に入ったら必ずそこから出なければならないため、3区間のうち、必ず2区間を通ることとなる。従って、東北地方と西日本地方は₃C₂=3通り、東日本地方は3×3＝9通りの組合せを検討する必要がある。

（東北地方）

	Ｈ（坂町・新発田）	Ｈ（福島・郡山）	Ｈ（いわき・岩沼）	最大値	ルート
ケース�@	0	1	1	1544.5	図27 参照
ケース�A	1	0	1	1607.4
ケース�B	1	1	0	1546.0

（西日本地方）

	Ｈ（富山・糸魚川）	Ｈ（美濃太田 　・多治見）	Ｈ（金山・名古屋）	最大値	ルート
ケース�@	0	1	1	3120.8	図28 参照
ケース�A	1	0	1	2952.9
ケース�B	1	1	0	2979.9

（東日本地方）

	西日本地方
東 北 地 方
	ケース名 最大値 （暫定最大値候補との差）		ケース�@	ケース�A	ケース�B
			3120.8 ( 0.0)	2952.9 (-167.9)	2979.9 (-140.9)
	ケース�@	1544.5 ( -62.9)	3516.5 以下	○	3677.2 以下
	ケース�A	1607.4 ( 0.0)	3480.9	3641.9 以下	3623.5 以下
	ケース�B	1546.0 ( -61.4)	3515.1 以下	○	3582.8 以下

前回と同様、東北地方の最大値となるケース�Aと西日本地方の最大値となるケース�@の組み合わせで東日本地方の最大値を求め、これを暫定的な全体最大値の候補とする。次に、部分巡回ルート禁止制約のない無制約最大値（接続部は(2,2)のみで全ケースを網羅している）を計算すると3695.6 (3480.9との差は214.7)となり、上表○部分が計算不要となった。

残りの6ケースは個別計算が必要である。個別計算の結果、上表のようにケース(�A,�@)はこれらの4ケースよりも全体合計で最大値が上回っているため、ケース(�A,�@)が最長片道ルートであることが示された。この場合の東日本地方最長片道ルートを図29に示しておく。

図27

図28

図29

• 2005年7月17日
  ＥＸＣＥＬワークシートにつき、下記のデータ訂正を行い、再計算した（川口氏の指摘による）。再計算により距離は変更となったが、最長ルート自体は変更なかった(ただし、図28ケース�Bは計算間違い訂正によるルート変更あり）。
  　* 豊橋-辰野　195.8km→195.7km(2001年4月1日：天竜川治水工事に関連する川路駅移設の反映漏れ)
  　* 富山-敦賀　190.2km→190.1km(2002年10月21日：北陸新幹線建設に伴う東金沢駅移設の反映漏れ)
  　* 鳥取-伯耆大山　88.0km→87.9km(誤記修正)
  　* 広島-新山口　91.4km→154.5km(誤記修正)
  なお、再計算に当たり、日暮里−尾久−赤羽と品川−西大井−鶴見を特定運賃計算キロから営業キロに置き換えた。