最適輸配送計画問題への数理計画法の適用
西田大，中川 賀津也，相川剛，熊本 和浩，小西 仲之

Iri…lllF川…＝＝‖‖＝＝‖＝＝‖‖＝＝‖‖‖＝‖＝＝＝＝＝＝‖＝＝＝‖＝＝‖＝＝＝‖＝＝‖＝＝＝‖＝＝‖＝＝＝‖＝＝‖＝‖‖＝＝＝‖＝＝‖＝＝‖‖＝＝＝‖＝＝‖＝＝＝‖＝＝‖‖＝‖＝＝‖＝‖＝‖‖＝＝‖＝‖‖＝‖＝＝‖＝‖＝＝‖＝＝＝＝＝＝＝＝＝‖＝＝＝＝＝＝＝＝＝＝＝＝州…＝＝＝＝＝＝＝＝刷

体最適化へと移行することにより，物流コストと1． はじめにCO2排出先の人帖な削減を尖現した（統介配小⑪はサiミ要製造業における物流コストは，20（）0隼度の調

たで読」J■Jiの約7．8％である．また，1ミ要製造業物流

ントリー㈱の登録商標）．
㈱住友／糾威システムソリューションズ数和枝術羊は，コストの機能別構成比率（輸送曹・保管曹・その他）

この紋付触巨⑪システムの小核をなす拠一・．1川りの最適輸において，輸送曹は約6割を11iめている［1］．すなわ

配送計両問題の解はを，数理計l呵はを清川して新たにち，開発した．数理叔術1ミでは，こjLまで什友令械グルー

1シ要製造業の売上高のうち，5％弱は輸送費である． これを製造業の経・浩ネl益率、巨均の2∴う％［2］と比プをl†Ⅰ心として，多柿多様な形態の往藻・物流に対し較すると，仮に輸送費を1（）％削減できれば，経常利て，OR理論をill川Jし最過化を図ってきている．特に，益が20％以ト唱えるという計附こなる．このように，

数理計l廟法をil千川した冊列としては，製鋼l二場におけ

輸配送コストは企業の総コストにIliめる割合が高いたる最適作業付帯決定［3］や，歩留最大化のための材料め，その削減による企業業絨への貢献度は■高し、．また，取合せ計画［4］などがある．

／1三産分野と比較して効＊化・最適化の余地が大きい．

本稿では，まず統合配車⑪システムについてそのビ加lえて，近隼の国際社会からのCO21伸滅をはじめジネスモデルを小心に概説したのち，最適輸配送計1叫とした環墳関越に対する要請は厳しくなる−一〟である．

関越の概安と解法開発の曹景を述べ，その解法を詳説

それに付い，行企業の環境問題に対する1i欄1．み姿勢は，する．

その企業イメージをノlミイrするほど重要性を増している．
一ノノ，物流・交通等を含む輸送分野のCO2排日量は，ll本の仝排甘量の約2剖をlJiめるといわれており，梢

2．統合配車⑪システムの概要
サントリー㈱及びサントリーロジスティクス㈱にお戟率IJり卜・走行蹄離知髄且どの輸配送効率化に什う

ける統合配二・1i⑪システムは，配坤センターでの一元管CO2排‖1騒削減効果は少なくない．この∴l．（からも，雌と，最適輸配送計画を特徴とした，サントリーグル

物流効率化の1「1iからの環塙関越への1†蛸Lみは，企業にープの拠′・1川り輸送の効率化システムである．現在では，とって梅めて求要であるといえる．

稼動1初のサントリーグループに加え，Web 卜でのサントリー㈱及びサントリーロジスティクス㈱では，社内及びグループ会社のl二域や物流拠点，サプライヤ求貨求ヰシステムによる多数の参加企業を得て，効率的なjIル胴融配送システムへと進化・発展している．

答礼等の柑宜問の物流に対して，1997年に純イ洒己小⑪

本システムでは，拠点聞の荷物（輸送依頼）を，従システムを運用開始した．従前の運送会利毎の輸配送

水の運送会社別への分配・配二小計l叫・小l■加齢保・輸送計両の個別最適化から，仝運送会利の輸配送．汁両の仝という業務フローから，配巾センターにおける一拍配ーIi（最適輸配送計巾）と各社での小l紬確保・輸送といにしだ はじめ，くまもと かずひろ，こにし のぶゆき㈱什友金捕システムソリューションズ 数f国史術1ミ〒660」）856 兵庫県尼崎llJ水l仙裾西之町1
なかがわ かづや

http：／／www．suntorylogistics．co．jp／より・］＝H）［5］．

サントリー（柵ロジスティクス推進部を積載した美中将軌，〒1り7（）（）51束甘酢巷Iメニノ亡ル坂ト2−3

いま，飲料上場Aとビール＝易Bの相互間に荷物があいだ っよし

う新たなビジネスモデルへの転換を図っている（図1，これによ町得られる効果を例ホする． →は荷物は空中移動をホすとする．

「代‖1興業（楯ある場合，従来は，その2つの荷物が異なる物流会社〒554−り（）2ニう 人阪IIJ此花♪り封十■裾南148に輸送依枇された場合は，2否の小両がそれぞれを輸

22（22）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

表1最適輸配送計画問題の分類記法の意味
デポの個数が複数
ル
同軍宵宮

顧客（要求）がEDGEに与えられる

EDGE

／でレット

汝朋

タイムウインドウ制約有り

叫／

感電呈ニ㌍

使用可能車両台数が動的に変化
車両積載可能容量が車両毎に異なる

J乃

C叩f

車両毎に稼動時間帯が異なる
ルートの可能時間帯が異なる

rwf

糾朝奴

血r′

地吐餉樹サ・∴−d′r

ネットワークが有向グラフである／

オーダ分割が可能≧1β／貨

1車両複数回転可能乃」

複数デポを経由するルートが可能」「

受入車種制限有り

SumCゎ

目的関数に車両コストを含む（台数）Sumf）f何〃rノ 目的関数にルート時間を含むO︒ノ一瞥醜藤

珊纏画論疲
♯輌確細‥

■dmこ−†、0も、、、

deフn㌧畠Depot鸞貴所饗鱒欒飽触齢

図1統合配車⑧の概念

整ヨ
J．gβGg．■】書‡†．≧lβ仇β」．●l●1．u．−！事】■．し〕，0，■】蠣

図2 拠点間最適輪配送計画問題とVRP送したのち，各々空移動で発倉庫に戻るという輸送を行っていた．すなわち，A→B・・・A及びB→A…Bであった．しかし，統合配車Rにより1台の車両でl，EDGE，tu7jlm，C励，∧tu）t，durtldir，／，≧1D侃

往復，すなわちA→B→Aという輸送が可能となる．

DA，AVIsumCi，Sum書（duri）

このように，全運送会社の荷物という広い探索空間と記述できる．表1に各項目の意味を記述する．の中で，往復ルートや三角ルートを積極的に採用する

このうち，本間題を特徴づける要素は，ことにより，拠点間輸送の効率化を進めるのが統合配・J：複数デポ車⑧の基本思想である．

・EDGE：オーダが区間で与えられる
・≧1上）／斤：複数回転

3．最適輸配送計画問題

・βA：複数デポ経由ルート可能

3．1VRPの分類と最適輸配送計画同席である．これらは，本間題が拠点間のFTL（Full

統合配車⑧における拠点間の最適輸配送計画問題は，Truckload）型のタイプであることを表現している．

VehicleRoutingProblem（VRP）の一つと捉えるこ

図2にこのタイプと，一般的なVRP問題の概念図をとができる．VRPの分類方法については，いくつか比較した．の文献で提唱されているが，ここではM．Desrochers

このタイプに対する研究論文は極めて少なく，文献の方法［6］に従って，この間題の特徴（拠点間輸配送）［6］で示された14個の分類事例にも該当するものは存を整理する．

在しない．同タイプに対する研究は，中国上海地区に文献［6］ではVRPを4つの観点から分類している．

すなわちaddresses（配送先とデポを含む拠点），おける，運送会社の港湾・駅・工場等拠点間の最適輸配送計画［7］が挙げられる程度である．

vehicle（車両），prOblem characteristics（制約条件3．2 最適輸配送計画開港の概要など），Objectives（目的関数）である．特に今回の日々の拠点間輸送依頼データ（出庫日・積卸地・重問題を特徴づけるのはaddresseesとproblem char−

量・容積・品目・各種制約条件値など）に対し，品acteristicsに関する項目である．

目・物流拠点・車両・車庫・車種・距離（時間・速本間題は，文献［6］の方法に従うと，2002年1月号

度）などの各マスターデータを参照し，制約条件を遵© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（23）23

守した上で，最適化要件（車両台数最小）が最適となから1箇所の卸地までの区間を走行し，全ての荷物をるように，車両へ積載する品目・量の明細（各区間卸す．そして次の横地までの空移動を繰返すという複毎）と，当該車両の運行ルートを決定する（図3）．

数回転が基本である．なお，車番毎の割当ではなく，以下，最適化要件，制約条件，運行ルート，積載品

まずは車両台数最小の計画を立案する．

目明細の順に解説する．

また，各車両・各区間の積載品目明細は，輸送依頼

最適化要件は，第1レベルとして車両台数最小化，データを分割あるいは組合せて，積載率を条件内で最第2レベルとして空移動時間や乗務員の残業時間等の大化としたものである．

重み付け線形和として与える．同じ台数であれば，で4．最適輸配送計画問題の解法

きるだけ第2レベルの線形和で表現された目的関数が小さくなるようにする．

4．1解法開発の背景

制約条件は，荷物（輸送依頼）に関するもの，物流一般的なVRPに対する解法の研究は極めて盛んで，拠点に関するもの，車両に関するもの，車庸に関する線形計画法・整数計画法・動的計画法等の厳密解法や，ものなど多種多様であり，主なものを表2にまとめた．

Saving，TabuSearch，NearestNeighbor等の近似解

運行ルートは，個々の車両について，1箇所の横地法に関する研究論文が多数ある［8］．
一方，拠点間の最適輸配送計画問題に関する研究は極めて少ないことは前述の通りである．文献［7］では，上海全体でオーダ数6，000−7，000，車両数3，400台の問題規模に対して，拠点毎（典型的な例で100オーダ，55台）の計画に縮退した上で，朝・夕2シフトの計画を立案している．解法としては以下2つの方法が提案されている．
（1）ヒューリステイクス手法ベースのアプローチ

横間題を車両の需要供給の輸送問題に近似する．すなわち，積が多い拠点には車両の供給が必要であり，卸が多い拠点からは車両が供給される．この輸送問題

配送計画

運行ルート

車両 812／16I

事を求解することにより，複数のサイクル状のルートを得る．ただし，このサイクル状のルートは，稼働時間などの制約条件を満たすことが保証されていないため，

事

嬢 京都 妄奈良 神巨
積載品目明細品目A7t品目B3t′

Greedyアルゴリズム等により，ルートを分割・継ぎ合せる必要がある．

軸姫路…神戸（2）最適化手法ベースのアプローチ

車番毎に，いくつかの候補ルートを列挙し，整数計画問題に定式化・求解する．候補ルート数は，十分小

図3 最適輸配送計画問題の概要

さな数でなければならず，最適性とのトレードオフに
表2 最適輸配送計画問題の主な制約条件

トなどを削除しておく必要がある．

着庫時間指定
荷物

物流拠点

車両車庫
24（24）

はなるが，空移動率の高いルートや，ありえないルー

本稿の拠点間最適輸配送計画問題と，文献［7］の計

出席時間指定倉庫稼動時間画問題の相違点は，問題規模・複数オーダの横合せの受入車種の制限有無，車番毎の計画か否か，など多数存在する．本問

単位時間当たりの入出庫台数
許容運行時間
許容空移動時間

題は横合せを実施し，車番の枠を取り払った計画のため組合せ数が増大する懸念がある上，問題規模は文献

車両移動時間［7］の数倍以上である．したがって，解法の開発は，許容出庫時間

組合せ爆発の防止と解の十分な準最適性の確保などに許容帰庫時間注意しながら，高い実射性を備えることを重視して進© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

れにより，本問題は極めて人規模な（ト1整数計画問題めた．

4．2 解法の概要

から，小・大規模の−・一般整数計画問題へ近似すること今回開発した解法は，組合せ爆発の川避と，制約変が‖†能である．セットのまとめ方を1二大すれば，十分更への柔軟な対応を‖†能とする，セット作成とルート実用的な近似が＝†能である．

隼成・選択からなる2段階の解法である．特に，l刈りさらに，組合せ爆発を避けるノノ策の一つとして，地毎の積載．■‖川明細を決定するセット作成を独、†二させる

f剛引こ近いセットを，優先的に個数を限定して連結すことにより，最適性を人きく損なうことなく，糾イナせることにより，できるだけ有望なルート（崩通解に含数を大幅に低減することが可能となる．

まれる‖†能性の高し、ルート）に絞り込んでルートを隼以卜，セット作成とルート隼成・選択に分けて，そ成することが考えられる．このノバ去によれば，ルート数を，れぞれ詳説する．

（セット数）×（指定個数）‖lけ）最人l‖購k）

4．2．1セット作成
1二車伸jに積載‖一能な．■，占しlの集まりをセットと定義する．セットイ竹戊では，仙々の輸送依椒に基づいて，所Jj一の車I妬こ積載叶能となるように，各．1J，lほ刹t合せ，を卜限として／巨成することができ，システムの実川的な運用が可能となる．

／巨成したルート ブは，ルートに含まれるIlijlメニl別のセあるいは分割する．この際，できるだけ軋斌および容ットノの個数仇をセット数分だけ並べたベクトルで積のIirj積載率が一三一言くなるような組合せを求めることに衣現する．いま，lズl封セット椎類数を〃，／1三成されより，必安となる車l叶吾数を削減できる．本解法では，たルート候補数を〟としたとき，Ⅳ×几仁行列としてビンパッキング問題の解法であるBest FitI）ecrease

ルート候補群行列Aを表現‖∫能であり，〃次元ベク法を応川したヒューリステイクス解はを構築した．

トルとして．甘価値Cを表現できる．

4．2．2 ルート生成・選択（2）ルート選択

前ステップで／巨成したセットを，1ないしは複数個

ルート選択では，ルート隼成の結果得られたルートを必安に応じて空移動を挟みながら庫列に連結したも候補才に対し，その選択台数∫〜・を変数する．選択ののをルートと定義する．セットを連結することにより，結米，終区瀾＝のセット散れを満たすような制約条

ルートの帳補を隼戊し（ルート隼成），／巨成されたル件のもとで，‖的関数（ユが最′J、となるように∬をート候補群から，輸送依椒を全て満足（セットを減れ決定する．抑的関数としては，台数最小のみで良い場なく選択）した卜で台数が最′トとなるルート候補の組

介は，（・z・＝1for∀オとし，それ以外の要素も考慮す合せを決定する（ルート選択）．この考え出ま，文献る場介は過、11な求み付けによる線形和とする．

［6］における最適化了一法ベースのアプローチと基本部

ルタ

Minimize ∑ciJ・i
J＝1分では卜i】様であるが，規模や各椎制約条件などの1甘題

特性卜，そのままの旭川は不可能であるため，様々な〃
Subjectto∑alJtrz・＝bj for∀j

改良を加えている．以卜，ルート／l三成とルート選択につき，本解法の優代性を中心に述べる．

7■＝1x〜・：integer（3）（1）〜（3）式のモデルは，整数計画問題であり，例えば，（1）ルート／巨戌

まずLP緩和問題を求解し，LP緩和解からBranch

ルート隼成では，車両や拠J∴＝こ関する制約条件を考＆Bound法や近傍探索法などで，整数最適解または慮し，運行‖摘巨なルートのみを隼成し，卜i川寺にそのル準最適解を求める．このl牲題の求角利こは市販の数理計ートの効率（空移動時問など）に基づき評価植を設定

1叶パッケージソフトウェアを利目することも 夫際的にする．

は有用である．

この際，辞書式jl旺i列隼成などの方法で運行可能なルートを全て／lリ戊すると，ルート数が具人となり，ルー5．おわりにト選択における整数計画問題の求角勘こ時間がかかる，本解法は，サントリーロジスティクス㈱においてあるいはルート／ト成l上1体が終rしない恐れがある．

1997年から，統介配小⑧システムの心臓部として本番

そこで，ルート／ト成の際に，セット作成で／l三成した稼動している．新ビジネスモデル及び本解法の相乗効セットを区間毎・制約条什毎にまとめることにより，米により，必要二車両台数は14％滅となり，輸送コス／巨成ルート数を大幅に低減することが‖r能である．こ2（）02年11jり一© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（25）25

ト削減は十数億円にも達した．また，車両の運行距離［2］「法人企業統計牛車Ii（平成9年度）」，人蔵省．

短縮による燃料消費量の削減で，CO2排出量の削減［3］酉川，山刑ほか，「列生成法による鋳型設置場所割三l与問
題の解法」，【I本OR学会秋季研究発表会アブストラクトと省エネルギーを実現している．

㈱住友金属システムソリューションズ数理技術室では，1962年の住友金属工業㈱L‡］央技術研究所における発足以来，約40年にわたって，数理計痢法を中心とした各種のOR理論を，主として鉄鋼分野における生産・物流計画に通用し，コスト削減と環境問題への対応に取り組んできた．1990年代・、打ばより，それまでに蓄積してきたOR適別技術を活印し，多種多様な業梓を対象としてORコンサルティング活動を展開してきている．本事例は，サントリーグループと住友金属グループのコラボレーションによる成功事例である集，Pp．112−113，1996．

［4］N．Konishi，Y．Nakagawa，H．Nishida，N．Sakai，
MIP−Based Approach to the Cutting Stock Problem
for Koll and Long Strip Materials with Millimum
ProductionAmountConstrainttems，Nov1996．

［5］T．Aida，

ITinaDistributionBusiness，Logistics

Systems，Vol．10，No．4，2OOl．

［6］M．Desrochers，］．K．Lenstra，M．W．P．Savelsbergh，A Classification Scheme for Vehicle Routing andSchedulingProblemsと言えよう，InternationalConfer−ence on Advancesin Production Management Sys−

，EJOR46，pp．322→332，1990．

本事例は，OR理論により企業の物流コスト削減・［7］MarshallL Fisher，HuangJiegang，Tang Bao−

環境問題への取組みを進めたという点で，極めて意義

Xing， Scheduling Bulk−Pickup−Delivery Vehiclesin

深いといえる．今後も，このような事例を積み重ね，［8］M．A．A卜Fawzan，K．S．AlSultan，RoutingProblem：Survey

参考文献［1］「2000年度業穂別物流コスト実態調査報告書」，日本ロ26（26），INTERFACES Vol．16，No．2，pp．18−23，

1986．

OR分野の発展に寄与していきたい．

ジスティクスシステム協会，2001．1．

Shanghai

The Vehicle，Proceedingsof5thIndus−

trialEngineering Research Conference，pp．269L274，
1996© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ