ダイクストラ法による交通配分プログラム
ダイクストラ法による交通配分プログラムです。プログラム言語はRubyを使用しています。
道路の末端から発生したOD交通量を最短経路で道路上に配分します。交差点を示す各ノードにもコストを設定していて、直進に比べて、右折、左折は時間がかかるなどの設定もできるようにしています。最短経路に１回配分するだけなので需要配分になります。
リンク上でQV曲線を設定して、交通量を分割して配分するようにすれば分割配分のプログラムになりますが、今回はそこまではやってません。実行はコマンドプロンプトで下記のように実行すればよいです。
下記の場合はoutput.txtに結果が出力されます。
ruby route_search.rb DATA.txt > output.txt結果は各起終点間の最短経路と各リンクの交通量、交差点の方向別交通量の算出するようにしています。
#! /usr/local/bin/ruby -Ks
require "csv"
class ODdata
def initialize(znum = 0,zname = '',od_dat = 0)
@znum = znum
@zname = zname
@od_dat = od_dat
end
attr_accessor :znum, :zname, :od_dat
end
#
class Ndata
def initialize(node_num=0,node='',ldn=0,lnk='',st=0,jj='',tsum=0.0,nchk=0,spath='',nlc=0.0)
@node_num = node_num
@node = node
@ldn = ldn
@lnk = lnk
@st = st
@jj = jj
@tsum = tsum
@nchk = nchk
@spath =spath
@nlc = nlc
end
attr_accessor :node_num, :node, :ldn, :lnk,:st, :jj, :tsum, :nchk, :spath, :nlc
end
#
class Ldata
def initialize(lnum =0,lname = '',node1 = '',node2 = '',linklen =0,linkspeed =0.0,linkcost =0.0,linkqdat=0.0)
@lnum = lnum
@lname = lname
@node1 = node1
@node2 = node2
@linklen = linklen
@linkspeed = linkspeed
@linkcost = linkcost
@linkqdat = linkqdat
end
attr_accessor :lnum, :lname, :node1, :node2, :linklen, :linkspeed, :linkcost, :linkqdat
end
#
class Crdata
def initialize(crnum =0,crname = '',status = '',node1 = '',node2 = '',cost = 0.0,crqdat = 0.0,crlnk1 = '',crlnk2 = '')
@crnum = crnum
@crname = crname
@status = status
@node1 = node1
@node2 = node2
@cost = cost
@crqdat = crqdat
@crlnk1 = crlnk1
@crlnk2 = crlnk2
end
attr_accessor :crnum, :crname, :status, :node1, :node2, :cost, :crqdat, :crlnk1, :crlnk2
end
#
def rdata(fld,oddata,ldata,crdata) # データの読み込み
file = open(fld)
l = file.gets
data = l.split(/\t/s)
oddata.znum = data[1].to_i # zone数
l = file.gets
data = l.split(/\t/s)
oddata.zname = data
onum = oddata.znum
$od = Array.new(onum){Array.new(onum)}
for i in 1..onum
l = file.gets
data = l.split(/\t/s)
$od[i] = data
end
oddata.od_dat = $od
l = file.gets
data = l.split(/\t/s)
ldata.lnum = data[1].to_i # link数
l = file.gets
ln = Array.new(ldata.lnum)
n1 = Array.new(ldata.lnum)
n2 = Array.new(ldata.lnum)
len = Array.new(ldata.lnum)
sp = Array.new(ldata.lnum)
lco = Array.new(ldata.lnum)
qdat = Array.new(ldata.lnum)
for i in 1..ldata.lnum
l = file.gets
data = l.split(/\t/s)
ln[i] = data[0]
n1[i] = data[1]
n2[i] = data[2]
len[i] = data[3].to_f
sp[i] = data[4].to_f
if sp[i] != 0 then
lco[i] = (len[i]*0.001/sp[i])*3600
else
lco[i] = 0
end
end
ldata.lname = ln
ldata.node1 = n1
ldata.node2 = n2
ldata.linklen = len
ldata.linkspeed = sp
ldata.linkcost =lco
ldata.linkqdat = qdat
l = file.gets
data = l.split(/\t/s)
crdata.crnum = data[1].to_i
l = file.gets
cn = Array.new(crdata.crnum)
st = Array.new(crdata.crnum)
cn1 = Array.new(crdata.crnum)
cn2 = Array.new(crdata.crnum)
cc = Array.new(crdata.crnum)
cqdat = Array.new(crdata.crnum)
crdata.crlnk1 = Array.new(crdata.crnum)
crdata.crlnk2 = Array.new(crdata.crnum)
for i in 1..crdata.crnum
l = file.gets
data = l.split(/\t/s)
cn[i] = data[0]
st[i] = data[1]
cn1[i] = data[2]
cn2[i] = data[3]
cc[i] = data[4].to_f
end
crdata.crname = cn
crdata.status = st
crdata.node1 = cn1
crdata.node2 = cn2
crdata.cost = cc
crdata.crqdat = cqdat
for i in 1..crdata.crnum
for j in 1..ldata.lnum
if (crdata.node1[i]== ldata.node1[j]) && (crdata.crname[i] == ldata.node2[j]) then
crdata.crlnk1[i] = ldata.lname[j] # 上流側のリンク
end
if (crdata.crname[i]== ldata.node1[j]) && (crdata.node2[i] == ldata.node2[j]) then
crdata.crlnk2[i] = ldata.lname[j] # 下流側のリンク
end
end
end
end
#
def dijkstra(org,dst,ldata,crdata,ndata) # 最短経路探査(ダイクストラ法)
$zlnk.clear
$zjj.clear
$znode.clear
$zcos.clear
cost = []
ndata.spath = []
for i in 1..ndata.node_num
ndata.jj[i] = ''
ndata.tsum[i] = 0.0
ndata.st[i] = 3
end # i
# 発ノードの判定
for i in 1..ndata.node_num
if(ndata.node[i] == org) then
# print "発ノード = ",org,"着ノード = ",dst,"\n"
ndata.jj[i] = 'ZZ' # 発ノードを示す
ndata.tsum[i] = 0.0
ndata.st[i] = 1
end # if
end # i
#
$zcc=[]
iflg = 0
while iflg == 0
iflg = 1
$zlnk.clear
$znode.clear
$zcos.clear
for i in 1..ndata.node_num
ndata.nchk[i] = 0
end # i
for i in 1..ndata.node_num
$zlnk.clear
$znode.clear
$zcos.clear
if (ndata.st[i] == 1) && (ndata.nchk[i] ==0) then
for j in 1..ndata.ldn[i]
for l in 1..ldata.lnum
if( ndata.lnk[i][j] == ldata.lname[l] ) then
$znode.push(ldata.node2[l]) # 下流側のノード
$zcos.push(ldata.linkcost[l]) # リンクの所要時間
end # if
end # l
$zlnk.push(ndata.lnk[i][j]) # 下流側リンク
end # j
for l in 1..ldata.lnum
if(ndata.jj[i] == ldata.node1[l]) && (ndata.node[i] == ldata.node2[l])
ulnk = ldata.lname[l] # ulnk 上流側リンク
end # if
end # l
ncc = 0
for n in 0..$znode.length-1
for nn in 1..ndata.node_num
if $znode[n] == ndata.node[nn]
ncc = nn
end
end # nn
if ndata.st[ncc] !=1 then
ndata.st[ncc] = 2
ndata.jj[ncc] = ndata.node[i]
end
end # n
for n in 0..$znode.length-1
$zcc[n] = 0.0
end # n
for n in 0..$znode.length-1
for m in 1..crdata.crnum
if(crdata.crlnk1[m] == ulnk) && (crdata.crlnk2[m] == $zlnk[n]) then
$zcc[n] = crdata.cost[m] # 交差点通過時の所要時間
end # if
end # m
end # n
ncc = 0
for n in 0..$znode.length-1
for nn in 1..ndata.node_num
if $znode[n] == ndata.node[nn]
ncc = nn
end
end # nn
if ndata.st[ncc] !=1 then
ndata.tsum[ncc] += $zcos[n]+$zcc[n]
end
end # n
ndata.nchk[i] = 1
end # if
end # i
#
fast_i = 0
$fast_tsum = 9999.9
$fchk = 0
for i in 1..ndata.node_num
if ndata.st[i] == 2 then
if($fast_tsum > ndata.tsum[i]) then
$fast_tsum = ndata.tsum[i]
fast_i = i
end # if
end # if
end # i
ndata.st[fast_i] = 1
iflg = 1
for i in 1..ndata.node_num
if ndata.st[i] > 1 then
iflg = 0
end # if
end # i
end # while
# 最短経路の抽出
$nc = []
$rpath = []
for i in 1..ndata.node_num
$nc[i] = 0
end # i
$echk = dst
iflg = 0
#
while iflg == 0
for i in 1..ndata.node_num
if(ndata.node[i] == $echk) then
$rpath.push(ndata.node[i])
$echk = ndata.jj[i]
$nc[i] = 1
if $echk == org then
iflg = 1
break
end # if
end # if
end # i
end # while
$rpath.push(org)
for i in 0..$rpath.length-1
k=$rpath.length-1-i
ndata.spath[k] = $rpath[i]
end # i
# 最短経路
print "org=",org,"\t","dst=",dst,"\t","spath=",ndata.spath,"\n"
end
#######################################################
# main
#######################################################
begin
doc = ARGV[0]
oddata=ODdata.new
ldata = Ldata.new
crdata = Crdata.new
ndata = Ndata.new
ndata.node = Array.new(1)
rdata(doc,oddata,ldata,crdata)
# puts crdata.crname
for i in 1..oddata.znum
# puts oddata.zname[i]
for j in 1..oddata.znum
$od[i][j] = oddata.od_dat[i][j].to_f
end # j
end # i
# STEP0 リンク表の作成############################
for i in 1..ldata.lnum
nflg = 0
for j in 0..ndata.node_num
if(ldata.node1[i] == ndata.node[j]) then
nflg = 1
end # if
end # j
if(nflg == 0) then
ndata.node_num += 1
ndata.node[ndata.node_num] = ldata.node1[i]
end # if
end # i
for i in 1..ldata.lnum
nflg = 0
for j in 0..ndata.node_num
if(ldata.node2[i] == ndata.node[j]) then
nflg = 1
end # if
end # j
if(nflg == 0) then
ndata.node_num += 1
ndata.node[ndata.node_num] = ldata.node2[i]
end # if
ldata.linkqdat[i] = 0
end #i
for i in 1..crdata.crnum
crdata.crqdat[i] = 0.0
end # i
# puts ndata.node
# print 'node_num= ',ndata.node_num,"\n"
ndata.ldn = Array.new(ndata.node_num)
ndata.st = Array.new(ndata.node_num)
ndata.jj = Array.new(ndata.node_num)
ndata.tsum = Array.new(ndata.node_num)
ndata.nchk = Array.new(ndata.node_num)
ndata.nlc = Array.new(ndata.node_num){Array.new(10)}
for i in 1..ndata.node_num
ndata.tsum[i] = 9999.99
end # i
ndata.nchk[1] = 0
$nlink = Array.new(40){Array.new(10)}
$nlink[0][0] = 0
$zlnk = Array.new(0)
$znode = Array.new(0)
$zcos = Array.new(0)
$zjj = Array.new(0)
#
for i in 1..ndata.node_num
lnn = 0
for j in 1..ldata.lnum
if(ndata.node[i] == ldata.node1[j]) then
lnn += 1
ndata.ldn[i]= lnn
$nlink[i][lnn] = ldata.lname[j]
end # if
end # j
end # i
# ndata.st : 1:起点ノードから最短経路が見つかったノード集合 2: 集合1の候補 3:残りのノード
ndata.lnk= $nlink
for i in 1..ndata.node_num
ndata.st[i] = 3 # 初期値の設定
ndata.nchk[i] = 0
end # i
# dijkstra法による最短経路の算出,リンク交通量の算出
for i in 1..oddata.znum
org = oddata.zname[i]
for j in 1..oddata.znum
if i != j then
dst = oddata.zname[j]
dijkstra(org,dst,ldata,crdata,ndata)
# print "ndata.spath=",ndata.spath,"\n"
# print "oddata= ",oddata.od_dat[i][j],"\n"
# リンク交通量の算出
for k in 0..ndata.spath.length-2
n1 = ndata.spath[k]
n2 = ndata.spath[k+1]
for h in 1..ldata.lnum
if((n1==ldata.node1[h])&&(n2==ldata.node2[h])) then
ldata.linkqdat[h] += oddata.od_dat[i][j]
end # if
end # h
end # k
# 交差点方向別交通量の算出
for l in 0..ndata.spath.length-3
cn = ndata.spath[l+1]
c1 = ndata.spath[l]
c2 = ndata.spath[l+2]
for m in 1..crdata.crnum
if((crdata.crname[m] == cn)&&(crdata.node1[m]==c1)&&(crdata.node2[m]==c2)) then
crdata.crqdat[m] += oddata.od_dat[i][j]
end # if
end # m
end # l
end # if
end # j
end # i
# リンク交通量の出力
print "リンク交通量算出結果\n"
print "リンク番号","\t","交通量","\n"
for i in 1..ldata.lnum
print ldata.lname[i],"\t",ldata.linkqdat[i],"\n"
end # i
# 交差点方向別交通量の出力
print "交差点方向別交通量の算出結果\n"
print "交差点","\t","node1","\t","node2","\t","status=","\t","方向別交通量","\t","上流リンク","\t","下流リンク","\n"
for i in 1..crdata.crnum
print crdata.crname[i],"\t",crdata.node1[i],"\t",crdata.node2[i],"\t",crdata.status[i],"\t",crdata.crqdat[i],"\t",crdata.crlnk1[i],"\t",crdata.crlnk2[i],"\n"
end # i
end