本研究では,頂点容量制約付き有向全域木パッキング問題を扱う.この問題は入力として, 有向グラフ,ルート頂点,頂点容量,辺の始点側と終点側それぞれに消費量が与えられる.目的はルート頂点に流入する有向全域木のパッキング回数を最大化することである.ただし,有向全域木の各頂点に対する消費量の合計は,頂点容量を超えてはいけない.以前,我々はこの問題に対して2段階の発見的解法を提案した.このアルゴリズムは,1段階目に木の候補を生成し,2段階目に木のパッキング回数を決定する.本研究では,ラグランジュ緩和を用いることで1段階目を改善した.計算実験により,提案アルゴリズムは以前のアルゴリズムより速く木を生成でき,少ない木の候補でもよい解を得ることを確認した.