Road installation with optimization

Problem

point(node)And road candidates(Edge)In a graph consisting of
Consider setting up a road on the edge.
I want to be able to move between several nodes.
The set of sets of nodes you want to move is called demand.
Convenience is the total distance traveled to meet demand.
Optimize installation costs and convenience.

Combinatorial optimization (http://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721) can also be used to solve such problems.

Way of thinking

For installation costs only, the Minimum Spanning Tree in the Typical Problem 85% A8% E5% 9F% 9F% E6% 9C% A8) Problem or [Steiner Tree](https://en.wikipedia.org/wiki/%E3%82%B7%E3%83%A5%E3% 82% BF% E3% 82% A4% E3% 83% 8A% E3% 83% BC% E6% 9C% A8) This is a problem. For convenience alone, it is a multi-product minimum cost flow problem, which is a variant of the typical problem minimum cost flow problem.

Lowering the installation cost will reduce the convenience, and increasing the convenience will reduce the installation cost. An optimization problem with multiple evaluation scales in this way is called a multipurpose optimization problem.

Here, let's find a trade-off between installation cost and convenience. To do this, we will solve mathematical problems based on the high-mix minimum-cost flow problem many times, while capping the installation cost.

Formulation

$ \ mbox {objective} $ $ \ sum_i {\ sum_j {\ sum_k {x_ {ijk}}}} $ Convenience
$ \ mbox {variables} $ $ x_ {ijk} \ ge 0 ~ \ forall i, j, k $ Demand Flow rate from node j to node j with respect to i
$ y_ {jk} \ in \ {0, 1 \} ~ \ forall j, k $ Whether to install a road between node j and node k
$ \ mbox {subject to} $ $ \ sum_ {j, k} {y_ {jk}} \ le Upper limit $ Maximum installation cost
$ x_ {ijk} \ le y_ {jk} ~ \ forall i, j, k $ x constraints
$ \ sum_k {x_ {ijk}} = \ sum_k {x_ {ikj}} + Demand ~ \ forall i, j $ Flow storage

Solve with Python

Prepare what you need.

python


import random, numpy as np, pandas as pd, networkx as nx, matplotlib.pyplot as plt
from itertools import chain, combinations
from pulp import *

def draw(g):
    """drawing"""
    nx.draw_networkx_labels(g, pos=pos)
    nx.draw_networkx_nodes(g, node_color='w', pos=pos)
    nx.draw_networkx_edges(g, pos=pos)
    plt.show()
def addvar(cnt=[0], *args, **kwargs):
    """Variable creation"""
    cnt[0] += 1
    return LpVariable('v%d'%cnt[0], lowBound=0, *args, **kwargs)

Let's create a problem at random. Demand was set only between some nodes.

python


n = 16 #Number of nodes
g = nx.random_graphs.fast_gnp_random_graph(n, 0.26, 8) #Graph
rn = g.nodes() #Node list
pos = nx.spring_layout(g, pos={i:(i/4, i%4) for i in rn}) #Node position
for i, j in g.edges():
    v = pos[i] - pos[j]
    g[i][j]['dist'] = np.sqrt(v.dot(v)) #distance
dems = random.sample(list(combinations(rn, 2)), 10) #demand
draw(g)

image

I will try to find the minimum spanning tree.

python


h = nx.minimum_spanning_tree(g, 'dist')
draw(h)

image

I will try to solve it.

python


rved = [(j, i) for i, j in g.edges()] #Reverse side
#Flow rate per demand
a = pd.DataFrame([(df, dt, ef, et, g.edge[ef][et]['dist'], addvar()) 
                  for df, dt in dems for ef, et in chain(g.edges(), rved)], 
                 columns=['DeFr', 'DeTo', 'EdFr', 'EdTo', 'Dist', 'Var'])
#Whether to install the side
b = pd.DataFrame([(fr, to, g.edge[fr][to]['dist'], addvar(cat=LpBinary)) 
                  for fr, to in g.edges()], columns=['Fr', 'To', 'Dist', 'Var'])
res = [] #Solution(setup cost,Convenience,Graph)
mxcst = 999 #Installation cost upper limit
while True:
    m = LpProblem() #Mathematical model
    m += lpDot(a.Dist, a.Var) + lpDot(b.Dist, b.Var)*1e-6 #Objective function(Convenience)
    m += lpDot(b.Dist, b.Var) <= mxcst #Installation cost upper limit
    for _, r in a.iterrows():
        i, j = r.EdFr, r.EdTo
        if i > j: i, j = j, i
        #Install when flowing the flow rate
        m += r.Var <= lpSum(b.query('Fr==%s & To==%s'%(i,j)).Var)
    for (df, dt), c in a.groupby(('DeFr', 'DeTo')):
        for nd in rn:
            z = 1 if nd == df else -1 if nd == dt else 0
            #Flow rate storage
            m += lpSum(c.query('EdFr == %s'%nd).Var) == \
                 lpSum(c.query('EdTo == %s'%nd).Var) + z
    m.solve() #Solution
    if m.status != 1: break
    a['Val'] = a.Var.apply(lambda v: value(v)) #result(Flow rate)
    b['Val'] = b.Var.apply(lambda v: value(v)) #result(Whether to install)
    cst = value(lpDot(b.Dist, b.Var)) #setup cost
    val = value(m.objective) #Convenience
    mxcst = cst - 1e-3 #Next installation cost upper limit
    h = nx.Graph()
    h.add_edges_from([(r.Fr, r.To) for _, r in b[b.Val == 1].iterrows()])
    res.append((cst, val, h))

Let's see the result. The higher the installation cost, the better the convenience.

python


plt.rcParams['font.family'] = 'IPAexGothic'
plt.plot([r[0] for r in res], [r[1] for r in res])
plt.xlabel('setup cost')
plt.ylabel('Convenience')

image

It is a graph when the convenience is the best.

python


draw(res[0][2])

image

I tried to make a GIF animation of the transition of installation cost. anim.gif

that's all

Recommended Posts