dAi dBi sAi wA wBi

運送会社の引越し業務におけるチーム構成と案件配分に関する研究
高倉
大樹
（沼田一道
教授，松浦隆文
助教）
1．はじめに
運送会社における引越し業務は肉体労働である．肉体労働が中心の業務では，業務を実際に行う人
達(以下，メンバー)が持つなんらかの不満や，メンバー間での不和が作業効率に大きく影響する．ま
た，それに伴う作業時間の増加により会社に多くの人件費が発生してしまう．筆者がアルバイトをし
ている A 運送会社の引越し業務でもそれに準ずる 2 つの問題点がある． 1 つ目は，メンバーに割り
振られる仕事量が不平等であり，メンバーが不満を感じていることである．2 つ目は，残業による人
件費が多く生じていることである．そこで，本研究では A 運送会社の引越し業務を例にとり，チーム
構成と案件配分を最適にすることで，メンバーの不満を減らし，会社全体の残業費を減らすことを目
的とする．そのため，この問題を数理計画問題として捉え，解決策を検討する．
2． A 引越し会社の現状
A 運送会社では，案件の多い休日に残業代が増え，休日の案件数は約 10 件である． A 運送会社に
おける引越し業務を行うメンバーは能力が様々であり，ドライバー5 人，助手 5 人，作業員 10 人で構
成されている．これらのメンバーを 5 チームに分ける．各チームには，ドライバーと助手が一人ずつ
必要という条件がある．各チームは 2 人~5 人で構成され，それぞれのチームには 1 件~3 件の案件が
配分される．案件の処理時間は，梱包作業，運び出し，運び入れ，積込み，倉庫~案件の積地~案件の
卸地~倉庫間のトラックでの移動（図 2）に要する時間で決まる．チーム構成と，案件配分の例を図 1
に示す．
１0人
5人
メンバーを５チームに分ける
0人
ドライバー
助手
チーム1
作業員
チーム２
チーム３
チーム４
チーム５
10案件をチームに配分する
図1
案件配分と人員配置の例
3．問題設定
本研究の問題設定を示す．また，メンバーの能力，案件の仕事量を記号化する．
・案件を複数処理する場合、1 つの案件を処理した後，倉庫に戻り次の案件に向かうとする (図 2)．
・ i をドライバー(1~5)，助手(6~10)，作業員(11~20)のメンバー番号とする．
・ドライバー i の能力を積込技術，梱包技術，土地勘で表わし，それぞ
れ dAi ，dBi ，dCi とする．
積地
卸地
・助手 i の能力を体力，梱包技術で表わし，それぞれsAi , sBi とする．
・作業員 i の能力を体力，梱包技術で表わし，それぞれwAi ,wBi とする．
倉庫
・ j を案件番号とする．
図2
・案件 j の仕事量を全物量，梱包を要する物量(梱包量)，移動距離で表わし，れぞれ
移動距離
,
,
と
それぞれ
A
j
,
B
j
, C j 表わす．
仮に，ドライバー1，助手 6，作業員 11，作業員 12 で構成されたチームが案件 1，案件 2 を実行した
場合の作業時間は以下の式で表わす．
A1 + A2
B1 + B2
C + C2
+
+ 1
dA1 + sA6 + wA11 + wA12 dB1 + sB6 + wB11 + wB12
dC1
(1)
本研究の目的は，最も作業に時間のかかるチームの作業時間が最小となるような 5 つのチームの組合
せ，案件の配分を求めることである．しかし，このまま直接定式化をすると非線形計画問題となって
しまい，厳密解を求めることが難しい．そこで，問題を線形化するため，可能チーム構成(以下の条件
のもとで構成可能な人員の組合せ)を列挙し，それぞれの可能チーム構成が各案件を実行するのに要す
る時間をあらかじめ求めておく．
・チームは 2∼5 人のメンバーで構成され，かつ，ドライバー，助手は必ずチームに一人ずつ配置さ
れる．
・各チームが各案件を実行する時間は(1)式で計算される．
4.定式化
前節で示した内容を数理計画問題として定式化する．これは集合被覆問題，集合分割問題，そして割
り当て問題を組合せた問題と考えられる[1]．目的関数は Minimax 型で表わした．
<定数/データ>
・ i (i = 1,...,20) をメンバー番号とする．
・
j ( j = 1,...,10) を案件番号とする．
・ k (k = 1,..., n) を可能チーム候補番号とする．
・ n を可能チーム候補数とする．
・
・
d
aik
kj
を可能チーム候補 k が案件 j を処理するのに要する時間とする．
をメンバー i が可能チーム候補 k に含まれるならば１，そうでなければ 0 とする．
<決定変数>
k
をチーム候補 k を選択するならば１，そうでなければ 0 とする．
kj
をチーム候補 k が案件 j を実行するならば 1，そうでなければ 0 とする．
・
x
・
y
また，チーム構成と，案件配分を最適なものにするための問題は以下のように定式化される．
minimize
10
V = max ∑ d kj
k
n
∑x
subject
to subject to
i =1
k
j =1
y
kj
(2)
(3)
= 5 ( ∀k , ∀ j )
y ≤ xk kj
(4)
n
n
(5)
( ∀ j ) ( ∀k ) (6)
∑ y = 1 ∑ aik xk = 1 k =1
kj
i =1
(2)式は，選択されたチームの最大作業時間が最小となるような 5 つのチームの組合せを選ぶため，選
択されたチーム候補の各々が行う案件の作業時間の和の最大値を最小化する目的関数である． (3)式
は，チーム候補 n 個の中から 5 つのチームを選ぶことを示している．(4)式は，チーム候補 k が選ばれ
なければ，チーム候補 k は案件 j を実行することができない事を示している．(5)式は，案件 j を実行
するのは 1 チームのみということを示している．(6)式は，メンバー i は選択されたチーム候補の中の
ただ一つに属することを示している．
5．求解手順
前節の定式化をソルバーである GLPK[2]のモデルファイルとし，データファイルは Boland 社
の Delphi6 を用いて作成する．これらを GLPK により CPLEX ファイルに変換し，最終的に混合
整数計画ソルバーGurobi4.0.0[3]を用い最適解を求める．しかし，前節で示した定式化をそのま
ま用いて最適値を求めようとすると，可能チーム候補の組合せが多いことに加え，実行可能領域
が広いため，最適解を求めるためには計算処理に大きな時間を要する．そこで，上界値，下界値を定
め制約式に加えることで，実行可能領域を狭め，最適解を求めるための計算時間を短くする．以下，
一連の求解手順を示す．
手続き 1：<定数/データ>で示した d kj ，aik を用いて最適値を求める．この際，目的関数を(2)式，制
約式を(3)~(6)式とする．
手続き 2：手続き 1 ではチーム数が 2~5 人の全ての組合せの数となるが，求解に用いるチームの組合
せを削減するために，チームの能力を 5 段階に分類する．次に，チームのメンバーの能力
level(表 1，表 2，表 3)の和が平均的になるチームの組合せのみを抽出する．そして，抽出
したチーム候補のみで構成されるようにd kj ，
aikの k を k ( k ：メンバー数が 2~5 人，かつ，
能力の和が平均的となるチーム候補)に更新し d k j ，
aik とする． d k j ，aik を用いて最良値
を求める．この際，目的関数は(2)式，制約式は(3)~(6)式とする．
手続き 3：手続き 2 から得られた最良値を Z と置き，これを上界値として制約式として組み込む．新
たに組み込む式は以下のようになる．
V ≤Z
(7)
さらに，選択されたチーム候補が行う案件の処理時間の和が最大のものは，選択されたチ
ーム候補の案件の処理時間の平均よりも大きくなることを示す式を下界値として加える．
n
10
V ≥ ∑∑d kj y × 0.2 k =1 j =1
kj
(8)
新たに(7),(8)式を制約式に加え最適値を求める．この際，目的関数を(2)式，制約式を(3)~(8)
式とする．
表1
表2
ドライバーの能力値
助手の能力値
表3
作業員の能力値
6.実験・結果・考察
表 4
各メンバーの能力値と案件の仕事量を与え，数値実験を行った．
案件の仕事
用いたデータを表 1~表 4 に示す．表 5 に各手続きで得られた最適
値，可能チーム候補数 n ，最適値が得られるまでの計算時間を示す．
手続き 1 では，1 日以上計算を行ったが最適値を得ることはでき
なかった．最適値が得られなかった理由として，可能チーム候補数
が多すぎることが考えられる．そこで，可能チーム候補数の制限を
行い，最良値を求めるため計算を行う(手続き 2)．可能チーム候補数
を制限するために各チームのメンバーの Level の和の平均を求めると 26.6 となる．そこで，メンバー
の Level の和が 26~27 となるチーム候補のみを用いて計算を行った．その結果，チーム候補数は減少
し最良値 661 が得られた．手続き 2 で得られた最良解は可能チーム候補数に制限を与えているため，
真に最適な値とは言えない．そこで，手続き 2 で得られた最良値を上解値として加え( V ≤ 661 )，全
ての可能チーム候補を与え再度計算を行った．その結果，最適値 623 が得られた．
表 6 は手続き 3 で得られたチームのメンバー構成を示す．表 7 は選択され 5 チームが各案件を実行
するのに要する時間（分）が示されており，網掛けされている部分が，各チームが実際に実行する案
件である．表 5 の計算時間から分かるように，最適値を得るまでの時間は約 30 分くらいである．よ
って，前節に示した一連の求解手順は実際に A 引越し会社でも使用可能である．
表5
表7
実験結果
表6
チームのメンバー構成
選択された 5 チームが実行する案件とその合計時間(分)
7．まとめ
本研究は案件配分と，人員配置を同時に実行するモデルを扱った．その際，通常の定式化を用いる
と計算処理に大きな時間を要する．本研究では，それを克服するため一連の求解手順を提案した．提
案手順で実際の例を解いたところ，実用に耐える時間内で最適値を得ることが出来た．また，このモ
デルを実用化することができれば，本研究は残業の削減，仕事負担の均等化に役立つと考える．今後
の課題は，案件を複数処理する場合に案件間の距離を考慮したモデルを考えることである．
8．参考文献
[1]今野浩・鈴木久敏：整数計画法と組合せ最適化，日科技連，(1982)
[2]glpkで楽しく最適化しよう：http//mukun_mmg.at.infoseek.co.jp/mmg/glpk/index.html (最終閲覧
日 2010
10/1)
[3] Welcome to Gurobi Optimization：http://www.gurobi.com/(最終閲覧日 2011 1/3)

Download Report