北海道と九州の最長ルートの探索は手計算で可能であったが、本州地区のＪＲ最長片道ルートの探索は手計算ではおそらく不可能である。
これを解く一つの方法が、葛西隆也氏も用いている整数計画法であるが、この、「ＪＲ最長片道ルートの探索に整数計画法を用いる」という発想は、「巡回セールスマン問題」がルーツなのではないかと思われる。巡回セールスマン問題は、決められた都市の全てを「一筆書き」で辿る最短ルートを求めるというものであるが、例えば「巡回セールスマン問題への招待」（山本芳嗣・久保幹雄／朝倉書店）では、これが整数計画法で解けることが示されている。巡回セールスマン問題と最長片道ルート問題は、最小化と最大化、最長片道ルートは全接続点を通る必要がないなど、異なる点もあるが、「一筆書き」であるという共通点について、全く同じ手法が使えるのである。
そこで、以下では、まず巡回セールスマン問題を紹介し、次にそれを最長片道ルート問題に変更する方法について述べることにしたい。