はじめに

不審船を見つけるために、巡視船を出航させます。
どのような、航路を選べばよいでしょうか？

問題

エリアは、10×10の格子状としましょう。
各エリア間の移動は10分でできるとします。
時間帯(10分)ごと、エリアごとの発見確率は、過去の実績から推定しておきます。
1日走って、見つからない確率を最小化しましょう。

考え方

このような問題は、時空間ネットワーク上での最短路問題として解くことができます。
最短路問題は、組合せ最適化の典型問題の1つです。

時空間ネットワークとは、各時間帯ごとのネットワークを時間に沿ってつなげたものです。

見つからない確率は、各時間帯の見つからない確率の積で表されます。
因子の部屋のテクニックを使って、logを使えば、積を線形の式にできます。
また、確率のlogをとると負になりますが、最短路のホップ数は同じなので、最小値を0にかさ上げすることにします。

Pythonで解く

最短路は、PythonのNetworkXのdijkstra_pathを使うと解くことができます。
やってみましょう。発見確率は、乱数で作ることにします。

python

import numpy as np, pandas as pd, networkx as nx
from itertools import product
from pulp import *

nt = 6*24 # 時間数(10分刻みで24時間分)
nn = 10 # 10x10のエリア
np.random.seed(1)
# 時間帯ごとエリアごとの発見確率
a = pd.DataFrame(np.random.rand(nt, nn*nn))
b = np.log(1-a) # 見つからない確率(1-a)のlogをとる
b -= b.min().min() # 最小値を0にする
g = nx.Graph() # ノード = 時刻×100＋エリア
for t, r in b.iterrows():
    for i, j in product(range(nn), range(nn)):
        k1 = t*100 + i*nn + j
        for di, dj in [(-1,0), (0,-1), (0,0), (0,1), (1,0)]:
            if 0<=i+di<nn and 0<=j+dj<nn:
                k2 = (i+di)*nn + j+dj
                # 時空間ネットワークの接続をする
                g.add_edge(k1, (t+1)*100 + k2, weight=r[k2])
# 最短路を求める
res = np.array(nx.dijkstra_path(g, 0, nt*100))

結果の表示

時間を無視して表示してみます。

python

from more_itertools import pairwise
h = nx.Graph()
h.add_edges_from([(i, j) for i, j in pairwise(res%100)])
nx.draw(h, pos={(i*nn+j):(i, j) for i in range(nn) for j in range(nn)})

以上