[PYTHON] Finding the patrol boat route by optimization

Introduction

Set sail a patrol boat to find a suspicious ship. What kind of route should I choose?

Problem

Let's make the area a 10x10 grid. Suppose you can move between areas in 10 minutes. The discovery probability for each time zone (10 minutes) and each area is estimated from past results. Run for a day and minimize the ** probability of not being found **.

Way of thinking

Such a problem can be solved as the shortest path problem on the ** spatiotemporal network **. The shortest path problem is one of the typical problems of Combinatorial Optimization (http://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721).

A spatio-temporal network is a network that connects each time zone in time.

image

The probability of not being found is expressed as the product of the probabilities of not being found in each time zone. Using the technique of Inshi no heya, you can use log to make the product a linear expression. Also, if you take the log of the probability, it will be negative, but the [hop number] of the shortest path (http://e-words.jp/w/%E3%83%9B%E3%83%83%E3%83] % 97% E6% 95% B0.html) is the same, so we will raise the minimum value to 0.

Solve with Python

The shortest path can be solved using Python's NetworkX dijkstra_path. let's do it. The discovery probability will be made with random numbers.

python


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

nt = 6*24 #Hours(24 hours in 10 minute increments)
nn = 10 #10x10 area
np.random.seed(1)
#Discovery probability for each time zone and area
a = pd.DataFrame(np.random.rand(nt, nn*nn))
b = np.log(1-a) #Probability of not being found(1-a)Log
b -= b.min().min() #Set the minimum value to 0
g = nx.Graph() #node=Time x 100 + area
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
                #Connect to a spatiotemporal network
                g.add_edge(k1, (t+1)*100 + k2, weight=r[k2])
#Find the shortest path
res = np.array(nx.dijkstra_path(g, 0, nt*100))

Display results

Ignore the time and try to display it.

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)})

image

that's all