Abstracts of Papers


Dissertation: "Computational Algebraic Analyses for Unimodular or Lawrence-Type Integer Programs


There have been a number of studies of the application of computational
algebraic approaches to solve integer programming problems, using
Gr{\"o}bner bases or standard pairs. By connecting these methods with
existing combinatorial methods for integer programming problems, we can
understand both methods deeply, and they have allowed new analysis of
their structures and construction of algorithms.

For an ideal over a polynomial ring, Gr{\"o}bner bases and the set of
standard pairs have duality as a Gr{\"o}bner basis is a generator of
the initial ideal, while the standard pair decomposition is a nice
decomposition of the set of monomials which does not contained in the
initial ideal. Such duality and consideration of a subclass of integer
programming problems where the duality theorem holds might give deeper
relation of two methods, and yield complexity bounds by making use of
the characteristics of the subclass, which could not be derived for
general integer programming problems. This thesis focuses on subclasses
where the coefficient matrix is unimodular or of the Lawrence type.

Problems in which the coefficient matrix $A$ is unimodular are a
mathematically nice subclass in the sense that the system $yA\leq c$
becomes totally dual integral (TDI) and each standard pair corresponds
to a dual feasible basis. In this dissertation, the method using
standard pairs is shown to be equivalent to calculation of the reduced
cost for each basis. Therefore, the number of standard pairs, which is
equal to that of dual feasible bases, gives the complexity of this
approach. The maximum number of dual feasible bases can be described by
the normalized volume of the polytope, defined by homogenizing
$A$. These results give a unified approach to analyze the number of
vertices of dual polyhedron via Gr{\"o}bner bases and volume
computations.

We also focused on transportation problems and minimum cost flow
problems. The Gr{\"o}bner basis approach for minimum cost flow
problems is a variant of the classical cycle-canceling algorithm: i.e.,
for any feasible flow the polynomial size of negative-cost cycles in the
residual network is chosen based on various rules and the flow is
augmented along these cycles as great a degree as possible. On the other
hand, the standard pair approach first finds the set of standard pairs,
and solves linear systems of equations for each standard pair until a
non-negative integer solution is obtained.

For transportation problems, several results about the number of
primal and dual feasible polyhedra have been reported. We give
computational algebraic proof for these results using above
approach. Furthermore, we study minimum cost flow problems on acyclic
tournament graphs, which are the most fundamental type of directed
graphs. The size of dual feasible bases for minimum cost flow problems
is shown to be less than the Catalan number, and the lower bound for the
size of primal feasible bases is shown to be of exponential order. For a
network optimization problem, the duality between the Gr{\"o}bner basis
and the set of standard pairs corresponds to the relation between
circuits and dual feasible co-trees, dually, cutsets and primal feasible
trees. As this relation has not been clarified previously, our results
using the computational algebraic duality are of interest.

On the other hand, in combinatorial optimization, Lawrence-type matrices
arise in many situations, e.g., in capacitated integer programming
problems and some multidimensional transportation problems. Furthermore,
Lawrence-type matrices are used in mathematical statistics in sampling or
enumeration of multi-way contingency tables of type $2\times
M\times\cdots \times N$ with fixed marginal sums. The problem that
counts the number of 2-dimensional contingency tables with fixed
marginal sums has been shown to be \#P-complete. On the other hand,
Markov Chain Monte Carlo methods that have polynomial-time mixing times
have been studied for tables of type $2\times\cdots\times 2\times N$.

While the relationship between vector matroids defined by matrices of
Lawrence type and Gr{\"o}bner bases has been studied in detail, there
have been few investigations of standard pairs for matrices of Lawrence
type. This dissertation focuses on standard pairs that correspond to
dual feasible bases. We present here a bijection between the set of such
standard pairs and the set of bases of the vector matroid, and describe the
matroidal structure of these standard pairs. In particular, in cases in
which the matrix is unimodular, this relation indicates that the number
of dual feasible bases is equal to the number of bases of the vector
matroid. As a corollary, we analyze (i) the number of dual feasible
bases for the capacitated minimum cost flow problem on an acyclic
tournament graph, (ii) the number of dual feasible bases for
multidimensional transportation problems of type $2\times
2\times\cdots\times 2\times M\times N$, and (iii) the number of primal
feasible bases for multidimensional transportation problems of type
$2\times \cdots\times 2\times 2\times N$.

博士論文:「単模および Lawrence 型整数計画問題に対する計算代数的解析」


整数計画問題に対して,近年 Gr{\"o}bner 基底や standard pair を用いた計算
代数的手法が研究されている.これらの手法と既存の組合せ的手法の橋渡しを行
うことにより,双方の手法の理解が高まり,新たな構造解析手法やアルゴリズム
の構築が期待される.

多項式環上のイデアルにおいて,Gr{\"o}bner 基底は初項イデアルの生成系であ
り,standard pair の集合は初項イデアルに含まれない単項式の集合の分解であ
るため,双対の関係にあると言える.このような双対性に着目し,さらに双対定
理の成り立つ整数計画問題のクラスを考えることにより,より豊かな橋渡しがで
き,一般的な整数計画問題からは得られないような計算量の上下限を得ることが
できると期待される.本論文では,そのような整数計画問題のクラスとして,係
数行列が単模のとき,および Lawrence 型であるときに着目する.

係数行列 $A$ が単模であるような問題は,不等式系 $yA\leq c$ が完全双
対整数性 (TDI) を満たし,さらに各 standard pair が双対実行可能基底に対応
する,という点で性質の良い問題のクラスである.本論文では,係数行列が単模
であるような整数計画問題に対して standard pair を用いた方法が,その
standard pair に対応する基底での被約コストを計算することと等価であること
を示す.よって,standard pair の数(つまり,双対実行可能基底の数)がこの方
法の計算量を与える.さらに,双対実行可能基底の数の最大値が,行列 $A$ を
斉次化して定義される多面体の正規化体積で表せることを示す.これにより,
Gr{\"o}bner 基底から体積計算を通じて双対多面体の頂点数を解析するという統
一的なアプローチを与えることができる.

さらに,本論文では特に輸送問題,および最小費用流問題に着目する.これらの
問題に対する Gr{\"o}bner 基底を用いたアプローチは,既存の負閉路消去アル
ゴリズム,つまり実行可能流に対して残余ネットワーク内の負閉路を見つけて流
し変えていく方法の変形である.一方,standard pair を用いたアプローチでは,
まず standard pair の集合を求め,非負整数解が得られるまで,各 pair に対
応する線型連立方程式を解く方法である.

輸送問題の主問題および双対問題の実行可能領域の頂点数に関しては,これまで
に既存の結果が知られているが,ここでは上のアプローチによる計算代数的な証
明を与える.さらに,無閉路トーナメントグラフ上の最小費用流問題に着目し,
最小費用流問題に対する双対実行可能基底の数が高々 Catalan 数となること,
および主実行可能基底の数が少なくとも指数オーダになることを示す.ネットワー
ク最適化問題において,Gr{\"o}bner 基底と双対実行可能基底の関係はサーキッ
トと双対実行可能補木(双対的には,カットセットと主実行可能木)の関係に対応
する.これらの関係はほとんど明らかにされていないので,この結果は計算代数
的双対性を用いた解析の面白い結果である.

一方,組合せ最適化において,Lawrence 型の行列は容量付き整数計画問題やあ
る多次元輸送問題など,多くの問題に現れる.また,数理統計学において,各行
和を固定した $2\times M\times\cdots\times N$ 型の多次元分割表のサンプリ
ングや数え上げに Lawrence 型の行列が用いられることが知られている.行和の
固定された2元分割表を数え上げる問題が \#P-complete であることが知られて
いる一方で, $2\times 2\times \cdots\times 2\times N$ 型の分割表に対して,
mixing time が多項式時間となるマルコフ連鎖モンテカルロ法が提案されている.

Lawrence 型の行列に対して,行列の定めるベクトルマトロイドと Gr{\"o}bner
基底との関係は良く研究されているが,standard pair については良く分かって
いない.そこで本論文では,特に双対実行可能基底に対応する standard pair
に着目する.まず,双対実行可能基底に対応する standard pair の集合とベク
トルマトロイドの基集合の間の全単射を与え,さらにそのような standard pair
たちのマトロイド的な構造を示す.特に,この関係は双対実行可能基底の数とベ
クトルマトロイドの基の数が等しいことを表している.さらにその系として,無
閉路トーナメントグラフ上での容量付き最小費用流問題に対する双対実行可能基
底の数,$2\times 2\times\cdots\times 2\times M\times N$ 型の多次元輸送問
題に対する双対実行可能基底の数,$2\times 2\times\cdots\times 2\times
2\times N$ 型の多次元輸送問題の主実行可能基底の数を解析する.

無閉路トーナメントグラフのトーリックイデアルに対するグレブナ基底の解析 / Analysis of Groebner Bases for Toric Ideals of Acyclic Tournament Graphs


Applications of Groebner bases to some computationally hard problems
in combinatorics using the discreteness of toric ideals have been studied
in recent years. On the other hand, the properties of graphs may give
insight into Groebner bases. Although toric ideals of undirected
complete graphs and bipartite graphs, which are homogeneous ideals, have
been studied well, those of other graphs are not well understood. For
the case of directed graphs, their universal Groebner basis
corresponds to the set of all the circuits of the graphs, but their
toric ideals are not homogeneous with respect to ordinary grading. Thus
toric ideals of directed graphs are interesting to study in graph
theory. In this thesis, we analyze toric ideals of acyclic tournament
graphs, which are the most fundamental directed graphs. We focus
especially on the degree and the number of elements of its reduced
Groebner bases.

We first give the positive grading which makes the toric ideals
homogeneous. We next give reduced Groebner bases for toric ideals
with respect to some term orders for both this grading and ordinary
grading. We show that there exist term orders for which reduced
Groebner bases remain in polynomial order by characterizing reduced
Groebner bases in terms of circuits. Note that the universal
Groebner basis for these graphs is of exponential size.

We next analyze the number of elements and degree of reduced Groebner
bases with respect to various term orders. Generally the degree of reduced
Groebner bases for toric ideals is at most of exponential order, but
in both cases of these two gradings, the degree remains in polynomial order
since the matrix is unimodular. We are interested in how the number of
elements can be bounded for the toric ideals of acyclic tournament
graphs. Using properties of the cycle space of graphs, we show that the
Groebner bases we have given above are the examples achieving minimum
number of elements or maximum degree in the case of ordinary grading. We
next calculate for graphs with small number of vertices, and give upper
bounds for the number of elements in the case of the grading whose toric
ideal become homogeneous. We also analyze the number of elements for the
purely lexicographic order.

We finally discuss applications to the minimum cost flow
problem. Algorithms for integer programming using Groebner bases have
been studied recently, and those complexity depends on the size of the
corresponding Groebner basis. We apply our results using these
algorithm to the minimum cost flow problem, analyze the complexity of
algorithms and relate to the complexity of minimum mean cycle-canceling
algorithm in minimum cost flow problem.

近年,トーリックイデアルの離散性を用いて Groebner 基底を組合せ論にお
ける計算困難な問題に適用する研究が行われている.逆に,グラフの性質を用い
て Groebner 基底に関する面白い知見が得られる可能性もある.無向完全グ
ラフや無向完全二部グラフのトーリックイデアルは同次イデアルになるため多く
の研究がなされているが,他のグラフについてはほとんど研究されていない.有
向グラフの場合,普遍 Groebner 基底はグラフのサーキット全体の集合に対
応するが,一般の次数付けではトーリックイデアルは同次イデアルにならない.
故に,有向グラフのトーリックイデアルの研究はグラフ理論的に面白い.本研究
では,中でも最も基本的な有向グラフである無閉路トーナメントグラフのトーリッ
クイデアルについて解析する.特に,Groebner 基底の次数や要素数に着目する.

まず,トーリックイデアルが同次イデアルになる次数付けを与え,その次数付け
および一般の次数付けに対して、いくつかの項順序に対するトーリックイデアル
の被約 Groebner 基底を与える.我々は被約 Groebner 基底をサーキット
により特徴づけることにより,被約 Groebner 基底の要素数が多項式オーダ
になるような項順序が存在することを示す.ここで,このグラフに対する普遍
Groebner 基底は指数サイズになることに注意しておく.

次に,任意の項順序に対する被約 Groebner 基底の要素数や次数を解析する.
一般にトーリックイデアルの被約 Groebner 基底の次数は高々指数オーダに
なるが,この2つの次数付けの場合,行列が単模になるため次数は多項式オーダ
になる.我々は,無閉路トーナメントグラフのトーリックイデアルの場合には,
要素数をどれだけ抑えることができるかに興味がある.本研究では,一般の次数
付けに対してグラフのサイクル空間の性質を用いることにより,上で与えた被約
Groebner 基底が要素数最小の例や次数最大の例になっていることを示す.ま
た,トーリックイデアルを同次イデアルにする次数付けに対して,頂点数の少な
いグラフに対して実験を行い,要素数の上限を考える.さらに,項順序を辞書式
順序に限定したときの要素数についても解析する.

さらに,これらの結果の最小費用流問題への応用を考える.近年,整数計画問題に
対して Groebner 基底を用いたアルゴリズムが示されており,その計算量は
対応する Groebner 基底のサイズに依存する.本研究では,このアルゴリズ
ムを用いて我々の結果を最小費用流問題に適用し,計算量を解析し,さらに最小
費用流問題での最小平均サイクルキャンセリングアルゴリズムの計算量と関連づける.


トーナメントグラフのトーリックイデアルのグレブナ基底 / Groebner Bases for Toric Ideals of Tournament Graphs


Application of Groebner bases to combinatorics through toric ideals
has been studied in recent years. On the other hand, the properties of
graphs may give insight for Groebner bases. So the toric ideals of
graphs have been studied. However, for special graphs, for example the number
of elements of their reduced Groebner basis have not been
analyzed. In this paper we enumerate, for the case of acyclic
tournament graphs, reduced Groebner bases with respect to some term
orders and analyze the number of elements. We also analyze the degree
and the number of elements in reduced Groebner bases with respect to
general term orders. Finally, we discuss an application to the shortest
path problem for acyclic tournament graphs.

近年,トーリックイデアルを通して Groebner 基底を組合せ論に適用する研
究が行われている.逆に,グラフの性質を用いて Groebner 基底に関する面
白い知見が得られる可能性もある,そこで,グラフのトーリックイデアルに
ついての研究が行われている.グラフを特化した場合でも,例えば既約 Groebner 基
底の要素数の解析はほとんど行われていない.本稿では,無閉路トーナメントグ
ラフについて,ある項順序での Groebner 基底を列挙し,要素数を解析する.
また,一般の項順序に対する既約 Groebner 基底の次数や要素数について解
析する.最後に,このグラフの最短路問題への適用について考察する.


無閉路有向グラフのトーリックイデアルに対するグレブナ基底の複雑度/ Complexity of Groebner Bases for Toric Ideals of Acyclic Directed Graphs


Applications of Groebner bases to some computationally hard problems in
combinatorics using the discreteness of toric ideals have been studied in
recent years. On the other hand, the properties of graphs may give
insight into Groebner bases. In this paper, we analyze toric ideals of
acyclic tournament graphs, which are the most fundamental directed
graphs. We focus especially on the number of elements of its reduced
Groebner bases. We show that there exist term orders for which reduced
Groebner bases remain in polynomial order by characterizing the bases in
terms of circuits. We next analyze the number of elements of reduced
Groebner bases with respect to various term orders. We finally discuss
applications to the minimum cost flow problem.

近年,トーリックイデアルの離散性を用いて組合せ論における計算困難な問
題に Groebner 基底を適用する研究が行われている.逆に,グラフの性質を
用いて Groebner 基底に関する面白い知見が得られる可能性もある.本論文
では,最も基本的な有向グラフである,無閉路トーナメントグラフのトーリ
ックイデアルを解析する.特に,被約 Groebner 基底の数に注目する.まず,
Groebner 基底をサーキットで特徴づけることにより,被約 Groebner 基底の
要素数が多項式オーダになる項順序が存在することを示す.次に,一般の項
順序に対する被約 Groebner 基底の要素数を解析する.最後に,最小費用流
問題への応用を議論する.


無閉路トーナメントグラフのグレブナ基底とベキ単行列の群上の超幾何系/ Groebner Bases of Acyclic Tournament Graphs and Hypergeometric Systems on the Group of Unipotent Matrices


Gelfand, Graev and Postnikov have calculated the number of independent
solutions of hypergeometric systems on the group of unipotent matrices.
These hypergeometric systems are related with the vertex-edge incidence
matrices of acyclic tournament graphs. In this paper, we show that the
results of Gelfand, Graev and Postnikov can be obtained by analyzing the
Groebner bases for toric ideals of acyclic tournament graphs. Moreover,
we study an open problem given by Gelfand, Graev and Postnikov.

Gelfand, Graev and Postnikov はベキ単行列の群上の超幾何系の線形独立な
解の数を計算した.この超幾何系は無閉路トーナメントグラフの点枝接続行
列に関係している.本論文では,無閉路トーナメントグラフのトーリックイ
デアルの Groebner 基底を解析することにより,Gelfand, Graev and Postnikov
の結果が得られることを示す.さらに,Gelfand, Graev and Postnikov によ
る未解決問題についても考察を行う.


無閉路有向グラフのグレブナ基底と Conti-Traverso アルゴリズムにおける簡約 / Groebner Bases of Acyclic Directed Graphs and Reductions in Conti-Traverso Algorithm


Algebraic approaches to some optimization problems on graphs applying
Conti-Traverso algorithm to Groebner bases of finite graphs have been
studied in recent years. On the other hand, the complexity of normal
form algorithms in Conti-Traverso algorithm is not well understood.
In this paper, we study the number of steps of reductions in Conti-
Traverso algorithm. We especially focus on the minimum cost flow
problems and the transportation problems on acyclic directed graphs,
and experiment the number of reductions in Conti-Traverso algorithm.

近年,グラフ上の最適化問題に対して,有限グラフの Groebner 基底に Conti
-Traverso のアルゴリズムを適用することによる代数的なアプローチが研究さ
れている.一方で,Conti-Traverso アルゴリズムにおける normal form アル
ゴリズムの計算量は解析されていない.本論文では,Conti-Traverso アルゴ
リズムにおける簡約の回数について調べる.特に,無閉路有向グラフ上での最
小費用流問題と輸送問題に着目し,Conti-Traverso アルゴリズムの簡約の回
数を実験を通して調べる.


無閉路有向グラフのトーリックイデアルのグレブナ基底と最小費用流問題への応用 / Groebner Bases for Toric Ideals of Acyclic Directed Graphs and their Applications to Minimum Cost Flow Problem


Applications of Groebner bases to some computationally hard problems
in combinatorics using the discreteness of toric ideals have been
studied in recent years. On the other hand, the properties of graphs
may give insight into Groebner bases. In this paper, we analyze toric
ideals of acyclic directed graphs, which are the most fundamental
directed graphs. We focus especially on the number of elements of
their reduced Groebner bases. We show that there exist term orders for
which reduced Groebner bases remain in polynomial order by characterizing
the bases in terms of circuits of graphs. We next analyze the number of
elements of reduced Groebner bases with respect to various term orders.
We finally discuss applications to the minimum cost flow problem.

近年,組合せ論における計算困難な問題に対して,トーリックイデアルの離散
性を用いて Groebner 基底を適用する研究が行われている.一方で,グラフの
性質を用いて Groebner 基底に関する新しい知見を得る可能性もある.本論文
では,最も基本的な有向グラフである,無閉路有向グラフのトーリックイデア
ルを解析する.特に,被約 Groebner 基底の要素数に着目する.まず,Groebner
基底をグラフのサーキットで特徴づけることにより,要素数が多項式オーダに
なるような項順序が存在することを示す.次に,任意の項順序に対する被約
Groebner 基底の要素数を解析する.最後に,最小費用流問題への応用について
議論する.


Toric ideal の standard pair 分解と最小費用流問題 / Standard pair decompositions of toric ideals and minimum cost flow problems


To integer programming problems, computational algebraic approaches
using Gr{\"o}bner bases or standard pairs via the discreteness of toric
ideals have been studied in recent years. Although these approaches do
not give improved time complexity bound compared with existing methods
for solving integer programming problems, these give algebraic analysis
of structure of integer programming problems. In this paper, we focus
on the minimum cost flow problems, whose structure is well-known, and
analyze using standard pairs. Especially, using results about Gr{\"o}bner
bases for toric ideals and hypergeometric functions, we show that the
number of vertices of the (nondegenerate) dual polyhedra for minimum
cost flow problems on acyclic directed graphs is more than 1 and less
than the Catalan number.

近年,整数計画問題に対してトーリックイデアルの離散性により,グレブナ基
底や standard pair を用いた計算代数的アプローチが研究されている.これら
のアプローチは既存の整数計画問題の解法に比べて計算量の改善を与えるもの
ではないが,整数計画問題の構造について代数的な解析を与えている.本論文
では,構造の知られている最小費用流問題に着目し,standard pair を用いた
解析を行う.特に,トーリックイデアルのグレブナ基底および超幾何関数の結
果を用いて,有向閉路を持たない有向グラフにおける最小費用流問題の(退化し
ていない)双対多面体の頂点数の最小値が1になること,および最大値がカタラ
ン数になることを示す.


最小費用流問題の双対問題におけるトーリックイデアルの解析 / Analysis of toric ideal on dual problem of minimum cost flow


Recently algebraical approaches using toric ideal have been carried out,
and now the methods with Gr{\"o}bner basis and standard pair are paid
attention to. In this study, we focus to minimum cost flow problem on an
acyclic tournament graph and investigate its dual problem. First we prove
that universal Gr{\"o}bner basis of toric ideal is associated with circuit.
Next we focus the case that a cost vector is negative, we explain that the
size of Gr{\"o}bner basis becomes minimum, that by standard pairs generated
by Gr{\"o}bner basis arithmetic degree is $(d-1)!$ where $d$ is the number
of vertices, and that one standard pair corresponds to one feasible spanning
tree in the graph in primal problem. Then we suggest a conjecture that
arithmetic degree in dual problems is of exponential order even in minimum
cases, as opposed to primal problems.

近年,整数線形計画問題に対して代数的な視点からトーリックイデアルを用いた
アプローチが行われており,具体的にはそのグレブナ基底やstandard pairを用
いた手法が注目されている. 本研究では,無閉路トーナメントグラフ上の最小費
用流問題を対象とし, その双対問題を考察する.まずトーリックイデアルの全て
のグレブナ基底はサーキットをなすことを示す.次いで特にコストベクトルが負
であるときを取り上げ,この時グレブナ基底のサイズが最小であること,またグ
レブナ基底より得られたstandard pairより $d$を点の数としてarithmetic degree
が$(d-1)!$となること,およびstandard pairと主問題における実行可能な全域
木が対応することを示す. また,双対問題のarithmetic degreeは主問題と異な
り,最小の場合でも指数オーダーになるとの予想を提示する.


3次元多面体の geometric shellings / Geometric Shellings of 3-polytopes


A total order of the facets of a polytope is a geometric shelling if
there exists a combinatorially equivalent polytope in which the corresponding
order of facets becomes a line shelling. The subject of this paper is
(geometric) shellings of 3-polytopes. Recently, a graph theoretical
characterization of geometric shellings of 3-polytopes was given
by Holt & Klee and Mihalisin \& Klee. Then we show sufficient conditions for a shelling to be geometric: Simple 3-polytopes allow perturbations of facets, thus might have more
chance a shelling is geometric. As sufficient conditions for this case
we show: nongeometric shelling of a (simplicial) 3-polytope was first shown by Smilansky. The discussions proceed in the polar setting: as total orders of vertices of
the polar polytope. All of our main results can be stated in graph theoretical
terms. The proof techniques used are elementary topology, graph theory, network
flows and local changes of polytopes.

多面体のファセットの全順序が幾何的シェリングであるとは,ある組合せ的に
同値な多面体が存在して,対応するファセットの順序が直線シェリングになる
ことをいう.本論文の対象は,3次元多面体の(幾何的)シェリングである.最近
Holt & Klee, Mihalisin & Klee により,3次元多面体の幾何的シェリングのグ
ラフ論的特徴付けが示された. 次に,シェリングが幾何的であるための十分条件: を示す.
単純3次元多面体はファセットの微小移動を許すため,シェリングが幾何的にな
る可能性が高い.この場合の十分条件として, ことを示す.
(単体的)3次元多面体の幾何的でないシェリングは Smilansky によって最初に示
された. 議論は,対極(ポーラー)の場で行う:つまり,対極多面体の頂点の全順序を考え
る.すべての結果はグラフ理論的な言葉で表される.証明で用いられる技法は,
初等的トポロジー,グラフ理論,ネットワークフロー,多面体の局所変換である.


2地点での車両観測情報からの全域的交通流解析 / Analysis of Traffic Flow Using Vehicle Data Sequences at Two Observation Points


本研究では,ITS 実現へ向けて,交通量情報の実時間獲得を念頭に,旅行時間の
実時間推定および車両の同定への新手法を提案する.具体的には,同一路線の
2 地点で収集した車長・車高の時系列データから,各車両の対応付けを推定し,
旅行時間を求めるアルゴリズムを考える.本研究では,車両の対応付け問題を
2 次元の文字列アライメント問題に帰着し,動的計画法 (Dynamic Programming: DP)
を用いて解くアルゴリズムを提案し,その実用性を実験によって検証する.さらに,
車両の画像情報も利用することによって,車両同定の精度向上を図る.

Getting the real time information of traffic is one of the important steps
towards realization of ITS. For this purpose, we propose a new method for
estimating travel time between designated two points and detecting the
correspondances of vehicles, by utilizing the observed lengths and heights
of vehicles.We formulate the problem of detecting the correspondances of
vehicles as the pairwise sequence alignment problem, by ignoring changes of
the order of vehicles. We also consider the utilization of image information
to improve the accuracy of correspondance. We examine the practicality of
our formulation by several experiments.


2地点車両観測情報からの全域的交通流解析アルゴリズム / An Algorithm of Traffic Flow Analysis Using Vehicle Data Sequences at Two Observation Points


本研究では,ITS 実現へ向けて,交通量情報の実時間獲得を念頭に,旅行時間の
実時間推定および車両の同定への新手法を提案する.具体的には,同一路線の
2 地点で収集した車長・車高の時系列データから,各車両の対応付けを推定し,
旅行時間を求めるアルゴリズムを考える.本研究では,車両の対応付け問題を
2 次元の文字列アライメント問題に帰着し,動的計画法 (Dynamic Programming; DP)
を用いて解くアルゴリズムを提案し,その実用性を実験によって検証する.

Getting the real time information of traffic is one of the important steps
towards realization of ITS. For this purpose, we propose a new method for
estimating travel time between designated two points and detecting the
correspondances of vehicles, by utilizing the observed lengths and heights
of vehicles.We formulate the problem of detecting the correspondances of
vehicles as the pairwise sequence alignment problem, by ignoring changes of
the order of vehicles. We examine the practicality of our formulation by
several experiments.


Back to Papers / Papers のページに戻る
Takayuki Ishizeki
Last Update: 11 June, 2002.