ダイクストラ法による交通配分プログラムです。プログラム言語は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