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

事例研究［論文］

ボロノイ分割を用いた加盟店舗への動的な注文割り当て手法
川本

卓樹，蓮池

隆

ものとする．

1. 研究背景および目的

このような形態で商品を販売している組織では，EC

スマートフォンや PC を代表としたインターネット

サイト企業が顧客から注文を受けた後，どの加盟店にデバイスが地域・世代問わず広範にわたって普及した対して依頼された注文を割り当てるべきかを考える必

現代において，EC サイトを通じて商品やサービスの要があるが，この割り当てを考える際にはさまざまなこ

恩恵を受ける消費者は年々増加傾向にある [1]．経済産とを考慮しなければならない．代表的な例として，割業省 [2] が行った EC サイトに関する市場調査によれ

り当てた先の加盟店が注文内容をすべて満たすことがば，企業も消費者のニーズに呼応する形で，EC サイ

できるか，割り当てた先の加盟店と配送先までの距離

トを新規に開設し，EC サイト市場全体の規模もます

は現実的に配送可能であるか，加盟店がロイヤリティ

ます大きくなってきている．特に，店頭販売による売に対して不平等を感じないように割り当てることがでり上げは市場の成熟化によって近年伸び悩んでしまっ

きているかなどが挙げられる．

ているため，企業が販売の場を実店舗から EC サイト

現在，特に配送距離に関して考える際に，郵便番号

へと拡大することによって，新しい客層を確保するこによって地域区分を行い，その区分けによって注文のとが狙いであろう．

割り当てを行っている事例が存在する．これは，EC

EC サイトを導入することで新規の顧客を獲得するサイトで注文を依頼する顧客が入力する顧客情報の中ことが期待されるが，その反面，サイトを導入するにに，郵便番号が含まれており，この情報が大まかな地域

至るまで，あるいは導入後にもさまざまな障壁が存在のまとまりを考えるのに適しているためである．しかする．たとえば，サイトを導入するために必要な初期し，郵便番号での地域の区分けでは，県や市区町村を費用や，導入した後も安定してサイトを運営するためまたいだ割り当てが優先されづらくなってしまい，市の運用コストなどのコストの問題が挙げられる．また，境や県境など，郵便番号の変化する境の近辺を配送先

サイトを運営していくために必要なノウハウがその企とする注文が，非効率な配送になってしまっている可

業に備わっているかどうかという問題も存在する．こ能性が考えられる．また，配送店舗を決める際に，諸うしたさまざまな障壁を乗り越えるために，昨今ある制約を鑑みながら注文を各加盟店へ割り当てる業務の一つの EC サイト運営企業が EC サイトの開発や運営

一部をオペレータが手動で行っているケースも少なくを担当し，その企業に対して，これまで店頭販売しかないが，オペレータが手動で割り当ててしまうと，よ

行ってこなかった個人店舗や企業などが「加盟」し，開り配送先との距離が近い加盟店が存在するにもかかわ発されたプラットフォームを利用することによって，らず，異なる店舗に注文を依頼してしまうなど，人的EC サイトで商品を取り扱うことを可能にするようなな判断によるロスが発生している可能性も考えられる．

販売形態をしている組織も存在しつつある．本研究でまた，注文割り当ての公平性については，オペレー

は，特定の商材を取り扱う EC サイトについて考える．

タによる割り当てによって，加盟店従業員との間の親

なお，各加盟店で商材ごとに品質の違いが生まれない

密さなどから，意図せずオペレータが同じ加盟店にば

かわもと たかき，はすいけ たかし
早稲田大学大学院創造理工学研究科〒 169–8555 東京都新宿区大久保 3–4–1

taka1023@suou.waseda.jp
thasuike@waseda.jp
受付 22.4.14 採択 22.8.19

2022 年 11 月号

かり割り当ててしまう場合も存在する．
そこで本研究では，ボロノイ分割を利用した提案手法による新たな配送地域の区分けによって，より効率的な地域区分を実現する．さらに，この提案手法を含
んだ注文割り当てアルゴリズムを構築することによっ
Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited. （53）619

て，現状オペレータによってマンパワーで行われていは定性的にしか示されてこなかったが，丹下は単独物る注文割り当て業務に代わるような，自動で加盟店へ

流と共同物流を比較し，積載率がどれほど向上したか，

注文の割り当てを行うアルゴリズムを構築する．以上

作業の効率化がどれほどなされたかを定量的に示し，を実現することで，マンパワーに依存しない注文の割

共同物流形態の有用性を示した．

り当て方や，より効率的な割り当て方の模索を行い，オ

また，共同物流のモデル化についてもすでにいくつペレータの注文割り当て業務の支援や，オペレータやかの研究が行われている．共同物流は巡回路型のモデ

加盟店の負担軽減への貢献につなげることを本研究のルで書き表すことができることから，巡回セールスマ目的とする．

ン問題や，より複雑な問題状況を表現することができる

2. 問題状況および関連研究

配送計画問題で定式化されることがある．小野山ら [4]は，マルチステージ GA を用いることで，共同物流網

2.1 問題状況

配送計画問題を実用的な時間内に求解まで導いている．

関連研究を述べる前に，本研究が想定する問題状況

また，内田ら [5] は，共同物流センターを建設せず，配について記述を行う．本研究では，EC サイト運営企

送中に他の企業（他デポ）に立ち寄ることを許すことで業が，店舗ごとに商材の品質に違いが生まれないよう

共同配送計画を実現させる「他企業デポ立寄り型共同

な，ある特定の商材を取り扱う EC サイトの開発や運配送」の数理モデルを，Simulated Annealing と Tabu

営を担当し，その企業に対し実際に商材を取り扱う店

Search を組み合わせたヒューリスティック探索によっ舗が「加盟」することにより，EC サイトでの販売をて求解まで導いている．

実現しているような組織・販売形態に焦点をあてる．

また，2.1 節の問題状況は，すでに配置されている各よって，注文を依頼する加盟店を顧客ではなく EC サ

加盟店を，施設配置可能な候補の集合と見立てること

イト企業側で選択できるものとする．

で，施設配置問題の p-メディアン問題に置き換える可そのような販売形態をとっている組織では，まず EC

能性も考えられる．

サイト運営企業が顧客から注文を依頼された際に，提以上の共同物流や p-メディアン問題を，本研究のよ携している加盟店に対して，さまざまなことを考慮しうな問題状況に適用するにはいくつか問題点が挙げらながら注文を割り当てるという手続きが発生する．

れる．まず，共同物流は，巡回路型のモデルであるたEC サイト運営企業から各加盟店へ注文が割り当て

め，距離の最小化を目的関数へ考慮する際には，加盟られた後，各加盟店がそれぞれの注文を満足する商品

店と注文の配送先の組合せに応じて距離を列挙した距を用意し，指定された配送先へ指定された日にその商離行列を考える必要がある．しかし，本研究では数多品を配送する．この際に発生する「配送料」は，商品

くの店舗が加盟し，店舗だけで何千店舗と存在してい代以外に顧客が事前に支払っている一律の手数料の内るため，注文一つ一つに対してすべての加盟店との距に含まれているものとする．したがって，配送距離の離を列挙していくことは，問題の規模が大きくなるほ

伸び縮みによって，配送料は変化しない．

ど困難になっていくと考えられる．

商品の配送が完了すると，一定期間ごとに各加盟店

また，共同物流と p-メディアン問題は，双方とも注へ割り当てられた注文の金額に応じて，各加盟店に対文（需要）が確定している状況で最適化問題を解かなしてロイヤリティが支払われる．

ければならないか，あるいは注文内容や届け先に関す

2.2 関連研究る情報が所与である状況から最適化問題を解くことが2.1 節で述べたような問題状況は，注文を配送する前提となるが，本研究はそのような前提が成り立たな店舗である配送元が複数存在する複数デポの物流形態

い問題状況である．本研究の問題状況では，顧客からであることから，共同物流における物流コスト最小化

次々と時系列で注文が依頼される（需要が時間を追うを目的とした最適化問題として書き表すことのできるごとに徐々に判明していく）状況において，その先ど可能性がある．このようなモデルは一般に共同物流モのような需要が発生するかわからない状態で注文を割デルとして知られ，研究が行われている．

り当てなければならない．また，逐次発生する需要の丹下 [3] は，日本の共同物流の端緒や最近の動向につ中には，当日配送のように喫緊に配送しなければならいて編んだ．丹下によると，共同物流はすでに日本におない注文も含まれている．以上から，需要がすべて判

いては相当に普及した概念であり，その端緒は 1970 年明している状況で問題を解くことができず，当日配送初頭といわれている．その後長らく，共同物流の効果のような突発的な需要も比較的頻繁に発生するため，

620（54）Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited.

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

注文をある程度溜める際の基準を設けることも難しい．

を加盟店へ割り当てる必要がある．そのため，規模の加えて，需要が逐次発生することで，巡回路型の問題

小さな店舗では次第に商品の在庫が減少し，注文を割を解く際にも，需要が新たに追加されるごとに再求解り当てられても，その注文の商品を準備することがでが行われるため，大きな計算コストをかけてしまう．

きないために，配送できない事態が生じてしまう．以以上を踏まえると，最適化問題を定式化し，そこへ上の事態を未然に防ぐため，繁忙期用商品に関してはある程度溜まった注文を入力するという方法ではなく，注文割り当て数の上限を設定し，繁忙期間中に受け入その段階においての最適な加盟店へ逐次動的に注文をれられる上限を超えて，注文が各加盟店へと割り当て

割り当てていくような手法であることが望ましい．

られることがないよう制約を設ける．ただし，繁忙期間中も取り扱っている通常商品に関しては，繁忙期用

3. 提案手法

商品とは別の商品という扱いであるため，特に上限の3.1 考慮する制約

対象とはならず，もし繁忙期用商品の上限に達してし注文を各加盟店へ割り当てる際，距離だけを考える

まっている店舗に対しても，通常商品は引き続き割りのではなく，さまざまな制約を考慮しながら割り当て
先の加盟店を決める必要がある．

当て可能であることとする．
以上のような制約を各期間で設け，注文の割り当て

本研究では，以下の制約を割り当て先加盟店選定時を自動で行うアルゴリズムを構築していく．

3.2 用いる既存手法の主な制約として定める．

1. 取り扱い品目を割り当て先加盟店が満たすことができるかどうか

本研究では，従来の郵便番号による地域区分に代わる新たな地域区分を生成する分割方法として，ボロノ

2. 架電する日（=注文を受けた日）に割り当て先加盟店が営業日かどうか

イ領域を生成するボロノイ分割 [6] と呼ばれる分割手法を用いる．ボロノイ領域は，それに対応するボロノ

3. 注文を配送する日に割り当て先加盟店が営業日でイ母点が最寄りとなる点の集合であるため，各加盟店

ある，あるいは営業日ではない場合に配送するこを母点とみなすことで，各注文の最寄りの加盟店に割とが可能な日であるかどうか

り当てることを可能とする．また，前述した制約を満

4. その他（組織脱退制約・手配の一時停止制約など）たさなかった際，隣接するボロノイ領域とボロノイ辺

5. （繁忙期用商品のみ）各加盟店の繁忙期間中におを共有するボロノイ領域をたどることで，近くの加盟

ける繁忙期用商品の注文割り当て数が上限に至っているかどうか

店を効率的に発見することに寄与する．
なお，本研究においては，緯度・経度を直交座標とし

本研究では，注文に対して比較的余裕をもって対処て用いてボロノイ分割を行っているため，球面上（地することができる「通常期」と，注文が殺到している

球楕円体上）では必ずしも正しい分割とはならない．

「繁忙期」についてそれぞれ考え，各期間に対して制約

よって，ボロノイ領域の境界付近の注文に関しては，必を設けることとする．

ずしも最短距離の店舗を選択できていない可能性も考

通常期は，制約 1〜4 のみを考慮して注文を割り当てる．通常期は顧客からの注文に対して比較的余裕をもって対処できるため，どの加盟店でも商品の在庫を切らすほど注文が殺到することはない．そのため，加えられる．これによる影響は大きくないものと考えられるが，上記の点に関して注意されたい．
また，各注文の点位置決定に際しては，Even-Odd

rule (Ray Casting Algorithm) [7] を用いる．

盟店ごとの注文割り当て数の上限は設定せず，注文を3.3 提案アルゴリズム

割り当てる．

2.2 節で述べた関連研究を本研究へ適用することは，

一方，繁忙期は制約 1〜5 を考慮して注文を割り当需要があらかじめ判明していないことなどから困難でてる．繁忙期は，通常期にも取り扱っている商品に加ある．そこで， 3.1 節の制約を考慮しながらボロノイ

えて，繁忙期にのみ取り扱っている商品も存在する．

分割を用いて注文を時系列で逐次割り当てるアルゴリ

本論文では通常期にも繁忙期にも取り扱っている商品

ズムの構築を行う．

を「通常商品」と呼び，繁忙期にのみ取り扱っている

特に本研究では，商品を「繁忙期用商品」と呼ぶこととする．繁忙期に• 加盟店の総配送距離がより短くなることに重点をは，特に繁忙期用商品の注文が殺到するため，注文が依頼された場合は，注文を溜める間もなく次々と注文

2022 年 11 月号

置いた「距離優先アルゴリズム」• 加盟店ごとに割り当てられた注文の総額がより等

Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited. （55）621

しくなることに重点を置いた「利益平準化優先ア

加盟店のうち，最も配送先との直線距離がルゴリズム」

近い加盟店へ注文を割り当てる．

の二つを提案する．

(b) 抽出された加盟店がない場合は，未配送とする．

以下に，二つのアルゴリズムの手続きを具体的に記述していく．

3.4 距離優先アルゴリズム
距離優先アルゴリズムは以下の手順を踏んで，依頼された注文を時系列で逐次動的に処理する．

5. 次の注文が依頼されたら Step2 へ．

4. 数値実験
提案アルゴリズムの実用性を検証するための数値実

1. 対象加盟店でボロノイ分割を行い，それぞれのボ験を実施する．実験に用いるデータは，実際に 2.1 節

ロノイ領域が隣接しているボロノイ領域をあらかで述べた問題状況のような販売形態で運営を行ってい

じめ特定する．

る組織において， 3.1 節で述べた制約を考慮しながら

2. 多角形の内外判定アルゴリズムにより，配送先がマンパワーで注文を割り振っている実績がある実デー

どのボロノイ領域の加盟店に最も近いか特定する．

タを用いる．提案した二つのアルゴリズムにより得ら

3. Step2 で特定された加盟店が制約をすべて満たしれた注文の割り当て結果と，オペレータが実際に割りているかどうかを判定する．

4. Step3 の判定により以下の分岐を行う．
(a) すべて満たした場合はその加盟店へ注文を割り当て，Step6 へ．

当てた実績の結果を比較することにより，提案アルゴ
リズムが実用に耐えうるものであるかの検証を行う．

4.1 通常期の実験条件
通常期の数値実験では，東京都・北海道の二つの地(b) 満たせない場合は，Step1 であらかじめ特域に対してそれぞれ提案した二つのアルゴリズムを適定した，その加盟店のボロノイ領域に隣接

用し，検証を行う．なお，どの地域においても通常期しているボロノイ領域のうち，すべて制約の実験対象期間はある年の 11 月 1 日〜11 月 30 日のを満たしている加盟店を抽出する．

1 ヵ月間とし，その期間に顧客から依頼された注文を実

5. Step4-(b) の抽出結果により以下の分岐を行う．

験対象の注文とする．また，考慮する制約は， 3.1 節(a) 抽出された加盟店のうち，最も配送先とのの制約 1〜4 の制約とする．加盟店や注文の配送先の直線距離が近い加盟店へ注文を割り当てる．

緯度経度に関するデータの一部は実データに存在しな(b) 抽出された加盟店がない場合は，未配送といため，Google Maps Platform [8] の API を利用すする．

6. 次の注文が依頼されたら Step2 へ．
3.5 利益平準化優先アルゴリズム
利益平準化優先アルゴリズムは以下の手順を踏んで，依頼された注文を時系列で逐次動的に処理する．

1. 対象加盟店でボロノイ分割を行い，それぞれのボ
ロノイ領域が隣接しているボロノイ領域をあらか
じめ特定する．

ることで緯度経度の取得を行った．

4.1.1 東京都における実験条件（通常期）[対象注文数] 7,425 件（配送先の郵便番号が東京都に該当している注文）[対象加盟店] 3,082 店（企業に加盟している全国の加盟店）
一度注文された後にキャンセルされた注文や，加盟店ではなくほかの配送業者に配送が委託された注文，

2. 多角形の内外判定アルゴリズムにより，配送先が顧客が注文の際入力した住所に何らかの大きな不備がどのボロノイ領域の加盟店に最も近いか特定する．

あり，Google Maps Platform からエラーが返ってき

3. Step2 で特定された加盟店と，Step1 であらかじ

た注文，Google Maps Platform から，明らかに異なめ特定した，その加盟店に隣接しているボロノイ

る都道府県の緯度経度が返ってきた注文などは実験で領域の加盟店のうち，制約をすべて満たしている対象とする注文から除いている．除いて残った注文の加盟店のみを抽出する．

うち，顧客が注文の際入力した配送先の郵便番号が東4. Step3 の抽出結果により以下の分岐を行う．
(a) 抽出された加盟店のうち，その段階で注文の総額が最も少ない加盟店へ注文を割り当

京都に該当している注文を東京都の対象注文とした．
以下すべての地域の対象注文に対し，上述した方法によって前処理が行われている．

てる．ただし，注文の総額が等しい加盟店

東京都における数値実験では，全国の加盟店を対象が複数存在する場合，注文の総額が等しいの加盟店としてボロノイ分割を行い，注文割り当ての622（56）Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited.

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

図1

全国の加盟店を用いたボロノイ分割

図3

通常期東京都内の配送先の位置

配送先住所が北海道である注文が北海道以外の地域に属する加盟店へ割り当てられることは，配送距離や他県と隣接していないという特殊な地理状況を考えると現実的でないためである．実際，実データのオペレー
タ実績において，「配送先住所が北海道である注文が割り当てられた加盟店」に他県の加盟店が存在するかど
うかを事前に調べたところ，すべての注文が道内の加盟店へ割り当てられていることが確認できた．よって，
提案アルゴリズムにおいても，北海道では道内加盟店のみを割り当ての対象加盟店とした．
図2

東京都内加盟店のボロノイ図

道内加盟店のみを注文の割り当て対象とする際に，ダミー店舗を導入した．ダミー店舗の詳細は，付録を対象とした．対象を東京都内の加盟店のみとしない理

参照されたい．

由は，東京都の場合，都外の加盟店に対して割り当て

なお，隣接するボロノイ領域の判定を行う際に，配ることが最も効率的なケースが存在するためである．

送先店舗候補としてダミー店舗が選ばれることを防ぐ

たとえば，東京都町田市の注文を，町田市に隣接する

ため，ダミー店舗は取り扱うことのできる商品がなく，

神奈川県川崎市や相模原市の加盟店が配送することは

常に定休日であり配送可能な日も存在しないとあらか

往々にしてあるだろう．

じめ設定し，ダミー店舗へ注文が一切割り当てられな

全国の加盟店でボロノイ分割を行ったボロノイ図を
図 1 に示す．実験ではこのボロノイ図を用いて割り当てを行っている．なお，図 1 では東京近郊のボロノイ
領域が不明瞭であるため，東京都内のみの加盟店でボ
ロノイ分割を行ったボロノイ図を図 2 に示す．縦軸はいよう施す．
ダミー店舗を導入してボロノイ分割を行った図を
図 4 に示す．
北海道における対象期間の注文すべての配送先の位置を図 5 に示す．

4.2 繁忙期の実験条件

緯度，横軸は経度である．
また，対象期間の注文すべての配送先の位置を図 3 に示す．

繁忙期の数値実験においても，東京都・北海道の二地域に対してそれぞれ提案した二つのアルゴリズムを

4.1.2 北海道における実験条件（通常期）[対象注文数] 2,991 件（配送先の郵便番号が北海道適用し，検証を行う．なお，実データをご提供いただ
いている企業の繁忙期が 4 月初旬〜5 月中旬であるため，対象期間を通常期実験期間翌年の 4 月 1 日〜5 月に該当している注文）[対象加盟店] 245 店（加盟店のうち北海道内に位置）する加盟店（220 店）+ ダミー店舗（25 店）

31 日の 2 ヵ月間として実験する．
3.1 節で述べたように，繁忙期間中には大きく分け

北海道における数値実験では，道内加盟店のみを注て二つの商品が存在しており，本論文ではそのうちの文割り当ての対象加盟店として実験を行う．これは，一つを「通常商品」と呼び，もう一つを「繁忙期用商2022 年 11 月号

Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited. （57）
623

図4

ダミー店舗を追加した際のボロノイ図

図5

通常期北海道の配送先の位置品」と呼ぶこととする．通常商品は，繁忙期間中でも繁忙期の制約ではなく通常期の制約を考慮して注文の割り当てを行う．すなわち，通常商品は 2.2 節の制約

1〜4 までの制約を考慮しながら注文を割り当てる．一方，繁忙期用商品は加盟店ごとに「繁忙期間全体を通して注文を受け入れることが可能な件数」という上限件数があるため，制約 1〜5 までの制約を考慮しながら注文を割り当てる．

4.2.1 東京都における実験条件（繁忙期）[対象注文数] 41,978 件（配送先の郵便番号が東京都に該当している注文）[対象加盟店] 3,005 店（企業に加盟している全国の
加盟店）

図6

繁忙期東京都の配送先の位置

図7

繁忙期北海道の配送先の位置の位置を図 6 に示す．

4.2.2 北海道における実験条件（繁忙期）[対象注文数] 21,773 件（配送先の郵便番号が北海道に該当している注文）[対象加盟店] 240 店（加盟店のうち北海道内に位置）する加盟店（215 店）+ ダミー店舗（25 店）
繁忙期の北海道における実験条件も，通常期同様，道内加盟店のみを対象とし，ダミー店舗を適当な場所へ追加する．東京都同様，加盟店の位置およびボロノイ
図は，通常期の図 4 とおおよそ同様であるため，そちらを参照されたい．また，対象期間の注文すべての配送先の位置を図 7 に示す．

4.3 実験環境

対象期間が 2 ヵ月であることに加えて繁忙期間であ研究における数値実験は，OS: Windows10 64bit，ることから，通常期の実験条件と比較して対象注文数

CPU: Intel (R) Core (TM) i5-8250U Processor@が著しく増加していることがわかる．

1.60GHz，8.00GB RAM を搭載した PC で行った．

加盟店は，対象期間が通常期の実験を行った翌年にまた，実データを実験に供する際の前処理，ボロなったことで加盟店の組織への加盟・脱退があったもノイ分割や提案アルゴリズムの構築などはすべてのの，おおよそ通常期と同様である．そのため，加盟

Python3.7.4 を用いた．特にボロノイ分割を提案アル店の位置やボロノイ図については，図 1 および図 2 をゴリズムで用いる際には，scipy.spatial.Voronoi [9] を参照されたい．また，対象期間の注文すべての配送先利用してボロノイ分割を行った．

624（58）Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited.

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

表1

4.4 評価指標

通常期東京都の割り当て結果

距離優先アルゴリズム，利益平準化優先アルゴリズ

距離
[km]

ム，オペレータが実際に割り当てた実績それぞれの比較を行うための評価指標を設定する．評価指標には，

距離優先

距離と利益のばらつき具合の二つを用いる．

利益優先• 距離：注文の配送先とそれを配送する加盟店とのオペレータ

利益のばらつき

未配送

[円]

[件]

6,700.10
17,300.28
16,399.84

132,145.28
38,389.24
296,392.55

330

直線距離の合計• 利益のばらつき具合：対象期間，対象都道府県の加表2

通常期北海道の割り当て結果

盟店ごとに割り当てられた注文の総額の標準偏差

距離
[km]

距離は，注文の配送先の座標と，その注文を配送する加盟店の座標の緯度と経度を用いて，測地線距離と距離優先呼ばれる，楕円体における二点間の最短距離を評価値

利益優先としている．なお，測地線距離の計算には楕円体モデ

オペレータ

利益のばらつき
[円]

未配送
[件]

85,976.78
28,734.50
142,574.06

2
2
0

10,402.39
44,007.31
15,802.71

ルに WGS-84，計算アルゴリズムに Karney 法を使用した geopy.distance [10] を用いている．利益のばらつ
き具合は，対象都道府県の加盟店ごとに割り当てられた注文の総額の標準偏差を評価値としている．すなわ

5. 実験結果
5.1 通常期の割り当て結果

ち，東京都の通常期では 3,082 店を対象に注文を割り

4.3 節で述べた実験環境のもと，距離優先アルゴリ当てているが，利益のばらつき具合の評価の際には，分ズム・利益平準化優先アルゴリズムを実データに適用

母を東京都内の加盟店（343 店）として計算を行ってした．東京都の結果を表 1，北海道の結果を表 2 としいる．北海道は，実験条件の対象加盟店のうちダミーてそれぞれ示す．なお，表では距離優先アルゴリズム

店舗を除いた加盟店数で計算を行っている．

を「距離優先」，利益平準化優先アルゴリズムを「利益前述したように，東京都の場合，神奈川県や埼玉県

優先」，オペレータ実績を「オペレータ」と表記する．

など隣接する加盟店に注文を割り当てる場合が存在す，利
また，評価指標の単位はそれぞれ，距離を「km」

る．そのため，対象都道府県である「東京都内のみの

益のばらつき具合を「円」で表し，未配送となった注

加盟店」を評価の対象とすると，オペレータによる割文件数もともに示す．

り当てとアルゴリズムによる割り当てでは，注文全体

両表より，どちらの地域でも距離優先アルゴリズムの総額が一致しなくなるデメリットが生じる．しかし，の距離・利益のばらつき具合はオペレータ実績と比較

加盟店の対象を「注文が割り当てられた加盟店」とする

して，より優れた結果を示した．利益のばらつき具合と，東京都内の加盟店にもかかわらず，注文が一度もに関しては，距離優先アルゴリズム内では特に考慮し割り当てられなかった加盟店が対象とならない．すなていないが，オペレータ実績よりも小さくなる結果と

わち，最も利益を享受できていない加盟店が対象とななった．これは，オペレータ実績において明示されてらないため，注文の総額が一致しないというデメリッ

いない潜在的な制約も考慮して割り当てている可能性

トが生じるが，「注文が割り当てられた加盟店」ではな

や，エリアごとにオペレータが思い浮かべる加盟店がく，「対象都道府県の加盟店」に割り当てられた注文に存在し，そこへ無意識のうちに偏って割り当ててしまっ

関して，加盟店ごとの総額の標準偏差を求めるよう設ている可能性が考えられる．

定した．そのため，東京都内では注文の総額が一致し利益平準化優先アルゴリズムでは，特に利益のばらていないということに注意されたい．一方で，北海道つき具合がどちらの地域でもオペレータ実績や距離優は，必ず北海道内に位置する加盟店に割り当たるため，先と比較して優れた結果を示した．一方，距離の指標

注文の総額は一致している．よって，利益のばらつき

は東京ではオペレータ実績と比べやや劣った結果を示具合を比較する際には，特に北海道を参照されたい．

し，特に北海道では 3 倍程度劣った結果を示した．こまた，提案手法にて未配送となった注文が発生した

れは，東京など面積が小さな地域に加盟店が密に存在場合は，オペレータの評価の不利とならないよう，そした状況では，隣接するボロノイ領域の加盟店に注文の注文に関してオペレータの実績からも評価対象からを割り当てても距離が大きくは伸びない一方，北海道

除外する．

などの面積が大きな地域に加盟店が疎に存在した状況

2022 年 11 月号

Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited. （59）
625

表3

繁忙期東京都の距離優先アルゴリズム割り当て結果
距離

利益のばらつき

未配送

する注文も異なるため，アルゴリズムごとに結果を示

[円]

[件]

す．東京都の結果を表 3，表 4，北海道の結果を表 5，4320

表 6 としてそれぞれ示す．

[km]
距離優先
オペレータ

なり，それによってオペレータ実績で評価の対象外と50,014.54
94,333.05

376,731.14
742,227.57

結果より，距離優先アルゴリズムでは，両評価指標で優れた結果を示していることがわかる．また，利益

表4

繁忙期東京都の利益平準化優先アルゴリズム割り当て
結果

利益優先
オペレータ

距離

利益のばらつき

未配送

[km]

[円]

[件]

116,747.75
94,836.60

125,713.70
744,686.10

2390

平準化優先アルゴリズムでは，利益のばらつき具合が両地域で大きく改善された結果を示した．一方，北海道のように面積の大きな地域では，距離の指標が著しく劣った結果を示した．面積の大きな地域では，利益平準化優先アルゴリズムを用いて割り当てると，配送距離が非常に長くなってしまい，却って各加盟店の負担になってしまうことが推察される．

表5

繁忙期北海道の距離優先アルゴリズム割り当て結果
距離
[km]

距離優先
オペレータ

また，北海道では，利益平準化優先アルゴリズムの利益のばらつき

未配送

未配送件数が距離優先アルゴリズムと比較して少ない

[円]

[件]

にもかかわらず，オペレータ実績の距離が利益平準化

1170

優先アルゴリズムと比べて長い結果となった．これは，97,761.64
123,567.99

417,473.65
449,665.17

利益平準化優先アルゴリズムで未配送となった注文のうち，配送先との距離が非常に長い注文がオペレータ

表6

繁忙期北海道の利益平準化優先アルゴリズム割り当て
結果

利益優先
オペレータ

距離

利益のばらつき

未配送

[km]

[円]

[件]

349,959.92
123,506.81

142,647.98
452,006.20

530

実績に多く含まれていたためであった．
両アルゴリズムとも，対象注文数の増加に伴い，未配送となる注文件数が増加傾向にあることがわかる．
繁忙期における提案アルゴリズムでは，繁忙期用商品の割り当て数に上限が存在することによって，繁忙期の終盤になるにつれ割り当て可能な加盟店が減少していく．そのため，注文の配送先を縄張りとするボロノ

では，隣接するボロノイ領域に割り当てると距離が一イ領域の加盟店，そのボロノイ領域に隣接するボロノ

気に伸びてしまうためと考えられる．

イ領域の加盟店すべてが， 3.1 節 5 番目の制約を満た

また，未配送注文は両地域でほとんど発生することすことができなくなる．その結果，未配送となる注文がなかった．隣接するボロノイ領域までを候補となるの件数が通常期と比較して増加したと考えられる．

店舗群として考えれば，注文の多くを未配送とせずと以上から，提案アルゴリズムの適用によって，通常商も，提案アルゴリズムにより割り当てることのできる品のように注文の上限が存在しない商品は，隣接する

ことがわかる．なお，未配送注文に関して，両地域にボロノイ領域の加盟店と上手く連携をとりながら，おおいて提案手法の未配送件数がそれぞれ一致している

互いの領域をカバーできることが明らかになった．一が，これらは未配送となった注文内容そのものに関し方，繁忙期における繁忙期用商品のように，加盟店ごても，いずれも一致している．これは，提案アルゴリとに注文の割り当て上限を設定しなければならない商

ズム上，両アルゴリズムともその注文が属するボロノ品は，隣接する加盟店と連携をとったとしてもカバー

イ領域とそれに隣接するボロノイ領域までが配達可能

できず，未配送注文の件数が増加してしまうことが明範囲である点は同様であるため，特に未配送注文が少らかになった．

数のうちは，未配送となる注文が同様となることがあると考えられる．

5.2 繁忙期の割り当て結果

6. 追加実験
5.2 節で述べたように，繁忙期において提案アルゴ

繁忙期における，両地域の割り当て結果も通常期とリズムでは多くの未配送注文を発生させてしまう．し同様に示していく．なお，繁忙期は距離優先アルゴリ

かし，顧客から依頼された注文が未配送となることは，ズムと利益平準化優先アルゴリズムで未配送注文が異現実では避けなければならない事態である．そこで，626（60）Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited.

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

3.3 節のアルゴリズムに改良を施し，未配送注文を可能

表7

な限り発生させないアルゴリズムの構築を行う．ただ繁忙期東京都の距離優先 + 全探索アルゴリズム割り
当て結果
距離
[km]

し，利益平準化優先アルゴリズムと比較して，距離優先
アルゴリズムの方が両評価指標で安定した結果を示す
ことが明らかになったため，追加実験では特に 3.4 節の距離優先アルゴリズムを改良する．

提案
オペレータ

51,095.37
95,449.32

利益のばらつき

未配送

[円]

[件]

379,127.02
747,868.95

00

距離優先 + 全探索アルゴリズムは以下の手順を踏ん
で，EC サイトで依頼された注文を時系列で逐次動的に処理する．

表8

繁忙期北海道の距離優先 + 全探索アルゴリズム割り
当て結果
距離
[km]

1. 対象加盟店でボロノイ分割を行い，それぞれのボ
ロノイ領域が隣接しているボロノイ領域をあらか
じめ特定する．

2. 多角形の内外判定アルゴリズムにより，注文がど

提案
オペレータ

99,578.28
124,846.11

利益のばらつき
[円]

未配送
[件]

418,267.27
451,912.80

00のボロノイ領域の加盟店に最も近いか特定する．

3. Step2 で特定された加盟店が制約をすべて満たしているかどうかを判定する．

べて満たすことのできた加盟店のうち，最も直線距離が近い加盟店へ注文を割り当てるように処理する．こ4. Step3 の判定により以下の分岐を行う．
(a) すべて満たした場合はその加盟店へ注文を割り当て，Step7 へ．

のような手続きを追加することによって，ほとんどのケースで注文をいずれかの加盟店へ割り当てることが可能となる．ただし，非常に稀なケースではあるもの(b) 満たせない場合は，Step1 であらかじめ特の，注文数が対象加盟店すべての上限の合計を超えて定した，その加盟店のボロノイ領域に隣接

しまい，すべての加盟店が注文受け入れ不可能となる

しているボロノイ領域のうち，すべて制約

場合は未配送となるほか，すべての加盟店が満たせなを満たしている加盟店を抽出する．

い制約を含んだ注文も，未配送となる．

5. Step4-(b) の抽出結果により以下の分岐を行う．

距離優先 + 全探索アルゴリズムがどの程度実用に耐(a) 抽出された加盟店のうち，最も配送先とのえうるかを検証するため，実験を行った．対象地域は直線距離が近い加盟店へ注文を割り当て，

これまで同様，東京都，北海道の二地域において，実Step7 へ．

験環境は 4.3 節と同様の環境で実験を行った．

(b) 抽出された加盟店がない場合は，全探索ア
ルゴリズムを用いて，すべて制約を満たしている加盟店のうち，最も配送先との直線追加実験における東京都の結果を表 7，北海道の結果を表 8 に示す．
表より，どの地域においても距離・利益のばらつき

距離が近い加盟店を特定する．

具合の評価指標ともに，オペレータ実績と比較してよ6. Step5-(b) の特定結果により以下の分岐を行う．

り優れた結果を示した．また，多く発生していた未配(a) 加盟店が特定できた場合は，その加盟店へ注文を割り当てる．

(b) 加盟店が一店舗も特定されない場合は，未送注文も，件数を 0 件に抑えることができた．

7. 結論
本研究では，主に EC サイト運営企業とそこに加盟配送とする．

7. 次の注文が依頼されたら Step2 へ．

している加盟店が成す組織の販売形態において，顧客

3.4 節の距離優先アルゴリズムと異なる手続きは，から注文を依頼された際に，どの加盟店へ注文を割り

Step5-(b) 以降である．距離優先アルゴリズムでは，隣当てることがより効率的であるかについて，従来の郵接するボロノイ領域ですべて制約を満たすことのでき

便番号による地域区分やオペレータによる手動の割りる加盟店が存在しない場合，未配送として注文を処理

当てに代わる，ボロノイ分割を用いた自動での注文割していた．一方，距離優先 + 全探索アルゴリズムでり当てアルゴリズムの構築を行った．

は，隣接するボロノイ領域のさらに外側に存在する加提案アルゴリズムでは，距離優先アルゴリズム，利盟店を含めたすべての加盟店に対して，制約をすべて

益平準化優先アルゴリズム，距離優先 + 全探索アルゴ

満たすことができるか判定を行う．その後，制約をす

リズムによるハイブリッドアルゴリズムの三つを構築

2022 年 11 月号

Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited. （61）627

した．構築したアルゴリズムについて， 2.1 節の形態

日の空いている注文に対しては，一度 EC サイト運営

で販売を行っている組織の実データを用いて数値実験

企業でその注文を溜め，その後の動的な割り当ての動を行い，オペレータ実績と比較してどの程度実用的な向やほかに溜まっている注文との兼ね合いなどを鑑み結果を示すか検証した．

ながら静的な割り当てを行うことで，さらに配送の効

その結果，通常期の距離優先アルゴリズムでは，距離と利益のばらつき具合それぞれの指標において，オ率性を上げるアルゴリズムを構築する必要があると考えられる．

ペレータ実績と比較して安定して優れた結果を示すこ

参考文献とができた．また，利益平準化優先アルゴリズムでは，注文数や加盟店数が少なく面積の大きい地域に対しては，配送距離が延びてしまう結果を示したが，東京都のように面積が小さく加盟店や注文の配送先が密集した地域に対しては，距離の指標もオペレータの実績と大きくは劣らない結果を示し，利益のばらつき具合の指標において，優れた結果を示すことができた．加えて，有用性の検証を行うことで，ボロノイ分割を用いた提案アルゴリズムが全探索アルゴリズムと比較して，注文の割り当てを 15 倍程度速く行うことができることも確認できた．また，通常商品に加えて加盟店ごとに上限の存在する繁忙期用商品を取り扱っている繁忙期においては，距離優先 + 全探索アルゴリズムを適用することで，距離優先アルゴリズムでは多く生じる未
配送注文の件数を可能な限り低く抑えつつ，オペレー
タ実績と両評価指標を比較して，一定の改善効果を示すことができた．
最後に本研究の今後の課題を挙げる．本研究は，計算機上で実験を行ったため，制約を満たす加盟店に割り当てられた場合は必ず注文が受け入れられる．しかし，実現場では，制約以外の諸般の事情から断られるケースも多々存在するため，実現場での検証を行う必要があると考えられる．
また，本研究は，直線距離によって距離を比較したが，河や山など自然による障害があることで，実際には直線距離とは大きく乖離した配送距離となるケースも存在する．したがって，直線距離ではなく実際の道
路状況に即した道路距離での比較を行い，ボロノイ分
割に地理的な情報を組み合わせることで，より現実の地形に即した地域区分を行う必要があるだろう．
また，有界なポリゴン生成手法の際に用いるダミー
店舗の設置に関して，よりシンプルで汎用的な方法をとる必要も考えられる．
また，本研究では，ある程度注文を溜めることはせず，どの注文も需要が発生した段階で割り当てが行われている．この発展として，顧客から注文を依頼された際，逐次加盟店へ動的に注文を割り当てることを原[1] 総務省，「平成 29 年版情報通信白書」， https://www.
soumu.go.jp/johotsusintokei/whitepaper/ja/h29/pdf/
29honpen.pdf （2020 年 12 月 18 日閲覧）
[2] 経済産業省商務情報政策局情報経済課，「平成 30 年度我が国におけるデータ駆動型社会に係る基盤整備（電子商取引に関する市場調査）報告書」，https://www.meti.go.jp/press/
2019/05/20190516002/20190516002-1.pdf （2020 年
12 月 18 日閲覧）
[3] 丹下博文， 日本の共同配送と米国の混載システムに関する研究， 経営管理研究所紀要，22, pp. 41–57, 2015.
[4] 小野山隆，前川拓也，久保田仙，鶴田節夫，薦田憲久， マ
ルチステージ GA による共同物流網における配送計画作成
手法， 電気学会論文誌 C（電子・情報・システム部門誌），
127, pp. 1460–1467, 2007.
[5] 内田哲也，鈴木卓，吉本一穂， 異なるサイズのトラックを有する企業における共同配送計画―SA，TS の Hybrid
Heuristic の適用（機械要素，潤滑，工作，生産管理など）―，
日本機械学会論文集 C 編，68，pp. 2825–2832, 2002.
『なわばりの数理モデル―ボロノイ図からの数[6] 杉原厚吉，
理工学入門―』，共立出版，2009.
[7] K. Hormann and A. Agathos, The point in polygon
problem for arbitrary polygons Computational Geometry, 20, pp. 131–144, 2001.
[8] Google Maps Platform, 「位置情報 API」，https://cloud.google.com/maps- platf orm/ （2020 年 12 月
18 日閲覧）[9] SciPy.org, scipy.spatial.Voronoi, https://docs.scipy.
org/doc/scipy/ref erence/generated/scipy.spatial.
Voronoi.html （2020 年 12 月 18 日閲覧）
[10] GeoPy, Calculating Distance, https://geopy.readth
edocs.io/en/stable/#module-geopy.distance （2020 年
12 月 18 日閲覧）付録
ダミー店舗について
母点集合 S に対して，S に属するすべての点を含む最小の凸集合を S の凸包 (Convex Hull) といい，C(S)で表すとき，ボロノイ分割を行った際に，C(S) の境界
上の母点は，ボロノイ領域が無限遠方まで延びるという性質がある [6]．
東京都の数値実験では全国の加盟店でボロノイ分割を行うが，東京都内およびその周辺の加盟店は Convex

Hull 境界上の点が存在しないため，この性質を意識す
ることなく提案アルゴリズムを用いることができる．
一方，北海道の数値実験では，道内店舗のみでボロノイ分割を行うため，必ず Convex Hull 境界上に存在する

則として行いながら，注文日から配送日までに大きく

628（62）Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited.

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

表9

有用性検証における各評価指標と実行時間の比較
距離
[km]

提案
全探索のみ

利益のばらつき

6,702.25
6,656.17[円]
132,275.01
133,276.63

実行時間

[秒]
404.006100.66

イ辺と交わり，領域を閉じることができる．ボロノイ領域が閉じていれば多角形と認識されるため，多角形の内外判定アルゴリズムにおいて望ましい結果が返される．
なお，ダミー店舗を追加すると，追加されたダミー店
図8

道内店舗における凸包 (Convex Hull)

舗が新たな Convex Hull 境界上の点となる．よって，
ダミー店舗のボロノイ領域は多角形の内外判定アルゴ
リズムを適用した際に，正しい結果を返さないということに注意されたい．ゆえに，注文がダミー店舗のボ
ロノイ領域に入らないよう，地域ごとの配送先となりうる範囲をあらかじめ考えながらダミー店舗を追加する必要がある．
提案手法の有用性検証
一般的に知られているアルゴリズムよりも優れた結果を示すかどうかを調べるため，代表的なアルゴリズ
ムとして「全探索アルゴリズム」を構築し，比較する
ことで，その有用性を検証する．全探索アルゴリズム

図9

道内店舗のみでのボロノイ図

では，距離優先アルゴリズムと同様，距離の指標を重視するため，「制約をすべて満たす加盟店のうち，最加盟店が発生してしまう．道内店舗における Convex

も直線距離が短い加盟店へ注文を割り当てる」というHull を図 8 として示す．

手続きに従って，アルゴリズムの構築を行った．実験

道内店舗における Convex Hull 境界上の加盟店は全

は 4.1.1 節とすべて同様の条件とする．なお，距離優部で 9 店舗あり，これらの店舗はボロノイ分割を行った

先アルゴリズムでは 3 件の未配送注文が発生するが，際にボロノイ領域が適切に生成されない．実際に道内両アルゴリズムを比較する際には，同様の配送件数で店舗のみでボロノイ分割を行ったボロノイ図を図 9 と比較を行うことが望ましい．したがって， 6 節の距離して示す．

優先 + 全探索アルゴリズムと，全探索のみを利用した

図 8 で Convex Hull 境界上に存在する母点のボロ

アルゴリズムとで比較を行う．距離優先 + 全探索アル

ノイ領域は，図 9 では，図の外側へと開いた状態で延ゴリズムと全探索のみのアルゴリズムの両評価指標おびるボロノイ辺が無限遠方へ延びていき，ボロノイ領

よび実行時間の比較を表 9 に示す．

域が閉じないことがわかる．本研究の提案アルゴリズ

各評価指標は，距離優先 + 全探索と全探索のみでおムでは，多角形の内外判定アルゴリズムを適用する際

おむね同様の結果を示した．やや結果が異なっているに，正しい判定結果を返すためには多角形であること

原因は，隣接するボロノイ領域の加盟店よりも隣接しが前提であるが，閉じていない領域は多角形とはいえていないボロノイ領域の加盟店の方が，直線距離上近ないため，望ましくない結果が返されてしまう．

くに存在するケースが稀にあるためと考えられる．そこの問題を解消するため，図 4 のように実際には存のほかにも，ボロノイ分割を行う際の，ボロノイ辺が在しない店舗をダミー店舗として Convex Hull のさ

必ずボロノイ領域として閉じるように調整する際に生らに外側に追加する．この操作を加えることで，追加

じる数値誤差が考えられる．

前に凸包境界上に存在していたボロノイ領域でも，無

表 9 より，ボロノイ分割を用いた提案アルゴリズム

限遠方へ延びていたボロノイ辺がダミー店舗のボロノの方が全探索のみのアルゴリズムと比較して 15 倍程

2022 年 11 月号

Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited. （63）629

度速い実行時間であることがわかる．ボロノイ分割をすべて計算しなければ，最も近い加盟店を特定できな用いた提案手法では，多角形の内外判定アルゴリズム

いため，次の処理へ進むまでに時間を要する．この違で，対象の点がいずれかのボロノイ領域の内側にある

いが，二つのアルゴリズムで実行時間に 15 倍程度のと判定された時点で次の処理へ進む．一方，全探索ア差を生んだと考えられる．

ルゴリズムでは各加盟店と配送先との直線距離を一度

630（64）Copyright © by ORSJ. Unauthorized reproduction of this article is prohibited.

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