制約と誓約: ラストワンマイルにおける制約（誓約）とその代償


# はじめに

Hunter x Hunterのファンとして、物流の開発者としてこの記事を書いています。出てくるデータや結果には特定の人物や団体と一切関係はありません。

「制約と誓約」とは、1998年より週刊少年に連載中の冨樫先生の有名作品であるHunter x Hunterに出てくる力（念能力）の概念の一つです。ルール（制約）を決めて、それを心に誓って遵守することで、力の威力や精度が飛躍的に向上することができます。制約が厳しいほど、それによる恩恵も大きいですが、最悪の場合は「命」を落とすこともあります。

法律で定められる勤務時間の制約、車両の大きさに関連する容量の制約、会社の規模によって決まる人数の制約、配達先の希望により発生する配達希望時間枠の制約など、物流業界もさまざまな制約によって力（満足度、信頼性、働きやすさなど）を得ています。

この記事では、弊社の配送最適化サービスLoogiaを使ってさまざまな制約と物流会社の運用費との関係を解析したいと思います。制約のない設定から始め、段階的に制約を追加し、運用費の増加を示します。

しかし、物流業界は広範囲であり、配達先の数や住所の密度、配達物の重さ、大きさや車種によって作業時間や移動時間は大きく異なります。そのため、今回はあくまで一例を調査します。皆さんには、「こんな分析ができるのか」という意気込みで読んでいただけると幸いです。

## データの準備
今回は話題のChatGPTに配達データを作っていただきました。

配達先は、弊社を中心とした半径2km以内のランダムな200座標（便宜上Optimind問題例と呼びます）と、名古屋市内のランダムな200座標（便宜上Nagoya問題例と呼びます）の2つのケースもChatGPTに提供していただきました（文字制限のため、50座標ずつ4回に分けました）。
    
- 日本では配達員は1時間あたりどれくらい稼ぎますか？
    (How much does a delivery man earns per hour in Japan?)
    宅配業者の時給は、勤務先の会社や経験・資格、配送業務の種類（通常配送、速達配送など）などによって異なります。日本の厚生労働省によると、2021年4月現在、日本の「宅配便業界」に勤務する労働者の平均時給は1,064円です。ただし、これはこの業界に勤務する全従業員の平均値であり、配達員の実際の賃金は、彼らが働く職場や雇用主によって異なります。日本の都市部、特に東京などの高コストな地域では生活費が高いため、これらの賃金で生計を立てることに苦労する宅配業者もいるかもしれません。
        
- 日本の配達員は1日に何個の荷物を配達しますか？
    (How many packages does a delivery man deliveries in a day in Japan?)
    宅配業者が1日に配達するパッケージ数は、その配達業者が働く会社や地域、その日の状況などによって異なります。しかし、一般的には、日本の宅配業界では、一人の配達員が1日に50〜100個程度のパッケージを配達することが多いようです。ただし、大型の荷物や重量物、配達先が遠い場合などは、1日に配達するパッケージ数が少なくなることもあります。
        
- 日本の都市部で走行するトラックの平均燃費はどれくらいですか？
    (How much is the average fuel efficiency of a truck driving in urban area in Japan?)
    日本の都市部で運転されるトラックの平均燃費は、トラックのサイズや重量、交通状況、運転スタイルなど、さまざまな要因によって異なります。しかし、日本自動車工業会（JAMA）が2021年に行った調査によると、2020年に日本で販売された新しい重量ディーゼルトラックの平均燃費は、都市部での走行条件で5.12キロリットルあたり（ガロンあたり12マイル）でした。ただし、この数字は販売された新しいトラックの平均値であり、実際に使用されているトラックの燃費は異なる場合があることに注意してください。
        
- 日本では1リットルのディーゼル燃料はいくらですか？
    (How much a liter of diesel costs in Japan?)
    現在の日本の平均的なディーゼル燃料価格は、地域や時期によって異なりますが、おおよそ 125 円から 145 円程度（2023年5月現在）で取引されています。ただし、価格は変動するため、正確な価格については、現地のガソリンスタンドや燃料会社などに確認することをおすすめします。

- 日本で商品を配達するために顧客が選択できる最も一般的な配達時間枠は何ですか？
    (What are the most common time windows for delivery available to the customer to choose for delivery goods in Japan?)
    日本では、顧客が選択できる配送時間帯として最も一般的なものは、以下のとおりです：
    1. 9:00-12:00
    2. 12:00-14:00
    3. 14:00-16:00
    4. 16:00-18:00
    5. 18:00-20:00
    6. なし
- 日本のOptimind社を中心とした2km半径内で、ランダムに50個の座標のリストを提供してください。
    Optimind社の位置は35.16584867220015、136.8993250970483です。
    (Give a list of 50 coordinates at random, centered in Optimind Company in Japan, within a radius of 2km. Optimind is located at 35.16584867220015, 136.8993250970483)
    省略
- 日本名古屋市以内で、ランダムに50個の座標のリストを提供してください。
    (Give a list of 50 coordinates at random in Nagoya City, Japan)
    省略
        
ChatGPTの答えをまとめると, 
- 時給: 平均1064 yen/hour ~= 0.3yen/s,
- 配達先数: 平均50個/person,
- 燃費費: 125[yen/l]/5.12[km/l] ~= 24.41 yen/km,
- 選択可能な時間枠:
    
    1. 9:00-12:00
    2. 12:00-14:00
    3. 14:00-16:00
    4. 16:00-18:00
    5. 18:00-20:00
    6. なし
    
- 出発時間: 08:00,
- 帰着時間: 21:00,
- 作業時間: 一律10分,

という問題設計になりました。

|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/6d198cc5-e828-047b-0bb0-395aef50149b.png" alt= “” width="500" height="500">|
| :-- |
|Nagoya問題例|

|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/c8f9b4b8-aa00-dbfd-dcc4-52e749caaaf7.png" alt= “” width="500" height="500">|
| :-- |
|Optimind問題例|

## 巡回セールスマン問題

巡回セールスマン問題（英: Traveling Salesman Problem, TSP）は物流における最も古典的な配送設定です。出発地点であるデポから出発し、全ての配送先を訪問してから再びデポに戻ります。
    
地域によっては、時間帯の混雑具合や通行不可の道路によって、2点間の移動時間や距離が変動する場合があります。この記事では、基本的には混雑や通行不可の影響を考慮した移動時間と距離を使用します。

| TSP | Optimind |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 合計 |
| Alice | 200 | 06月1日08:00:00<br />06月2日20:35:09 | 3513(11709) | 36000(120000) | 935(38292) | 4447 | 40447 |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/7ed9ab80-9af8-6fee-7735-4edae6dc407e.png" alt= “” width="500" height="500">

| TSP | Nagoya |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 合計 |
| Alice | 200 | 06月1日08:00:00<br />06月3日02:52:23 | 10303(34343) | 36000(120000) | 3288(134694) | 13591 | 49591 |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/5e40d074-dddd-b98c-f4ec-5307cae57cab.png" alt= “” width="500" height="500">

TSPは基本的には運用費が最も少なくなる設定であり、最もシンプルな形態です。ルートの選択だけでは作業時間を削減することはできないので、コストの増加は移動費と燃料費で評価されます。Optimind問題例では基本的な運用費は1ドライバー + 4447円であり、Nagoya問題例では基本的な運用費は1ドライバー + 13591円でした。

## Prize Collecting TSP: 訪問件数最大化・効率最大化
    
巡回セールスマン問題は制約がないように見えますが、「全ての配送先を訪問する」という制約があります。限られた時間内に効率的な配送先のみを訪問する問題はPrize Collecting TSP（PC-TSP）と呼ばれ、研究はされていますがTSPと比べてあまり有名ではありません。現実世界では、「全ての配送先を訪問する」ことは絶対に遵守されるべきであり、それを破ると致命的な影響がある恐れがあります。この記事では基本的には、未配送にならないように配達員を追加することで対応します。
    
| PC-TSP | Optimind |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 合計 |
| Alice | 72 | 06月1日08:00:00<br />06月1日20:57:43 | 1039(3463) | 12960(43200) | 261(10688) | 1300 | 14260 |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/2832c282-0e60-016a-b950-eb58332f272a.png" alt= “” width="500" height="500">

| PC-TSP | Nagoya |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 合計 |
| Alice | 61 | 06月1日08:00:00<br />06月1日20:51:34 | 2908(9694) | 10980(36600) | 850(34842) | 3759 | 14739 |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/8bd62bdb-042e-eae6-dce4-76b5bdd427fa.png" alt= “” width="500" height="500">
    
帰着時間が制約されている中で、できるだけ多くの配送を行うために密集している地域のみを訪問するようになりました。
    
Optimind問題例では、出発地点の北部に近い配送先が選択されました。結果として、72箇所の訪問先を1300円でこなすことができました（効率=1300/72=18円/訪問先）。元々は200箇所の訪問先を4447円（効率=4447/200=22円/訪問先）でした。
    
Nagoya問題例では、出発地点の東部が選択されました。ChatGPTの乱数が東部に偏っているためと思われます。Optimind問題例と比べると、訪問先の数が少なくなり、効率も3759/61=62円/配送先とかなり異なりました。元々は200箇所の訪問先を13591円（効率=13591/200=223円/訪問先）でした。遠くの配送を諦めたことで効率をかなり改善できたように見えます。
    
もし「今日はどんな仕事をするのか」を選択できるユースケースであれば、PC-TSPを検討することが効果的でしょう。
    
## Vehicle Routing Problem: 出発時間到着時間制約
    
「全ての配送先を訪問する」制約に加え、デポから出発できる時刻やデポへの帰着時刻に制約を追加すると、問題の名称はVehicle Routing Problem（配送計画問題、VRP）と呼ばれます。車両数が1台のみの場合、先に説明したPC-TSPとなります。
    
| VRP | Optimind |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 小計 |
| Alice | 70 | 06月1日08:00:00<br />06月1日20:50:12 | 1264(4212) | 12600(42000) | 331(13547) | 1594 | 14194 |
| Bob | 59 | 06月1日08:00:00<br />06月1日18:56:55 | 1205(4015) | 10620(35400) | 313(12823) | 1518 | 12138 |
| Charles | 71 | 06月1日08:00:00<br />06月1日20:54:14 | 1156(3854) | 12780(42600) | 296(12142) | 1453 | 14233 |
|  |  | 合計 | 3624(12081) | 36000(120000) | 940(38512) | 4564 | 40564 |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/b982bd4f-c349-cc9a-3dfe-21a855c1b6a9.png" alt= “” width="500" height="500">

| VRP | Nagoya |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 小計 |
| Alice | 52 | 06月1日08:00:00<br />06月1日19:27:46 | 3020(10066) | 9360(31200) | 951(38956) | 3971 | 13331 |
| Bob | 57 | 06月1日08:00:00<br />06月1日20:20:12 | 3064(10212) | 10260(34200) | 1008(41309) | 4072 | 14332 |
| Charles | 59 | 06月1日08:00:00<br />06月1日20:25:36 | 2801(9336) | 10620(35400) | 871(35674) | 3672 | 14292 |
| David | 32 | 06月1日08:00:00<br />06月1日15:16:45 | 2102(7005) | 5760(19200) | 656(26889) | 2758 | 8518 |
|  |  | 合計 | 10986(36619) | 36000(120000) | 3486(142828) | 14472 | 50472 |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/73fe9b0f-fb57-2d67-8f1d-f8571df6cc7b.png" alt= “” width="500" height="500">

結果を見ると、最も注目しやすい点はルート（色）が密集していることです。複数の配達員が同じ道を何度も通らないように、配送先がエリアごとに分かれています。

Optimind問題例では、2日にわたってた計画が帰着時間が守れるようになり、配達員が3人必要となり、コストが4447円から4564円に増加しました（2.63%増加）。Nagoya問題例では、3日にわたってた計画が帰着時間が守れるようになり、配達員が4人必要となり、コストが13591円から14472円に増加しました（6.5%増加）。

## Capacitated Vehicle Routing Problem: 容量制約
    
車両のスペースは無限ではなく、VRPに「車両の容量を超えないように」制約を加える問題はCapacitated Vehicle Routing Problem(CVRP)と知られている. 
    
ここでは2つのシナリオを検討しました。1つ目は、各車両が最大50パッケージを持てる設定です。もう1つは、運営が小さい車体を検討しており、最大25パッケージを搭載する設定です（HALFと呼びます）。
    
| CVRP | Optimind |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 小計 |
| Alice | 50 | 06月1日08:00:00<br />06月1日17:12:03 | 937(3123) | 9000(30000) | 234(9605) | 1171 | 10171 |
| Bob | 50 | 06月1日08:00:00<br />06月1日17:20:34 | 1090(3634) | 9000(30000) | 293(11993) | 1383 | 10383 |
| Charles | 50 | 06月1日08:00:00<br />06月1日16:58:57 | 701(2337) | 9000(30000) | 177(7238) | 878 | 9878 |
| David | 50 | 06月1日08:00:00<br />06月1日17:16:41 | 1020(3401) | 9000(30000) | 257(10513) | 1277 | 10277 |
|  |  | 合計 | 3749(12495) | 36000(120000) | 961(39349) | 4709 | 40709 |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/bd7d5fce-9060-f190-3c32-5c52af6e52e8.png" alt= “” width="500" height="500">
    
| CVRP-HALF | Optimind |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 小計 |
| Alice | 25 | 06月1日08:00:00<br />06月1日12:33:52 | 430(1432) | 4500(15000) | 119(4883) | 549 | 5049 |
| Bob | 25 | 06月1日08:00:00<br />06月1日12:40:28 | 548(1828) | 4500(15000) | 158(6492) | 707 | 5207 |
| Charles | 25 | 06月1日08:00:00<br />06月1日12:31:28 | 386(1288) | 4500(15000) | 106(4359) | 493 | 4993 |
| David | 25 | 06月1日08:00:00<br />06月1日12:34:47 | 446(1487) | 4500(15000) | 131(5347) | 577 | 5077 |
| Eve | 25 | 06月1日08:00:00<br />06月1日12:46:54 | 664(2214) | 4500(15000) | 174(7120) | 838 | 5338 |
| Frank | 25 | 06月1日08:00:00<br />06月1日12:44:50 | 627(2090) | 4500(15000) | 162(6635) | 789 | 5289 |
| George | 25 | 06月1日08:00:00<br />06月1日12:42:45 | 590(1965) | 4500(15000) | 149(6121) | 739 | 5239 |
| Henry | 25 | 06月1日08:00:00<br />06月1日12:34:02 | 433(1442) | 4500(15000) | 114(4678) | 547 | 5047 |
|  |  | 合計 | 4124(13746) | 36000(120000) | 1114(45635) | 5238 | 41238 |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/3cf25de4-8627-f57d-67b7-b95fbe5ff370.png" alt= “” width="500" height="500">

| CVRP | Nagoya |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 小計 |
| Alice | 50 | 06月1日08:00:00<br />06月1日18:41:39 | 2550(8499) | 9000(30000) | 794(32526) | 3344 | 12344 |
| Bob | 50 | 06月1日08:00:00<br />06月1日19:10:33 | 3070(10233) | 9000(30000) | 1006(41224) | 4076 | 13076 |
| Charles | 50 | 06月1日08:00:00<br />06月1日19:13:43 | 3127(10423) | 9000(30000) | 1006(41209) | 4133 | 13133 |
| David | 50 | 06月1日08:00:00<br />06月1日18:24:59 | 2250(7499) | 9000(30000) | 705(28892) | 2955 | 11955 |
|  |  | 合計 | 10996(36654) | 36000(120000) | 3511(143851) | 14508 | 50508 |
    
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/dbaaae65-593d-e992-722b-8b7ffc8ec27f.png" alt= “” width="500" height="500">

| CVRP-HALF | Nagoya |  |  |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| Driver | 配達件数 | 開始時間<br />到着時間 | 時給(総移動時間) | 作業費(総作業時間) | 燃料費(総移動距離) | 時給+燃料費 | 小計 |
| Alice | 25 | 06月1日08:00:00<br />06月1日13:44:04 | 1693(5644) | 4500(15000) | 560(22945) | 2253 | 6753 |
| Bob | 25 | 06月1日08:00:00<br />06月1日13:26:18 | 1373(4578) | 4500(15000) | 440(18023) | 1813 | 6313 |
| Charles | 25 | 06月1日08:00:00<br />06月1日13:26:45 | 1382(4605) | 4500(15000) | 446(18285) | 1828 | 6328 |
| David | 25 | 06月1日08:00:00<br />06月1日13:47:49 | 1761(5869) | 4500(15000) | 648(26559) | 2409 | 6909 |
| Eve | 25 | 06月1日08:00:00<br />06月1日13:35:34 | 1540(5134) | 4500(15000) | 509(20868) | 2050 | 6550 |
| Frank | 25 | 06月1日08:00:00<br />06月1日13:40:18 | 1625(5418) | 4500(15000) | 528(21643) | 2154 | 6654 |
| George | 25 | 06月1日08:00:00<br />06月1日13:45:09 | 1713(5709) | 4500(15000) | 578(23684) | 2291 | 6791 |
| Henry | 25 | 06月1日08:00:00<br />06月1日13:24:06 | 1334(4446) | 4500(15000) | 416(17035) | 1750 | 6250 |
|  |  | 合計 | 12421(41403) | 36000(120000) | 4126(169042) | 16547 | 52547 |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3467420/353755e9-1c1b-7d3d-4434-b72a2710edf6.png" alt= “” width="500" height="500">

容量50個の制約を導入することで、クラスターの境界線がわずかに重なるようになりました。容量25個の制約ではクラスターの重なりが明確になりました。
    
Optimind問題例では、基礎値である4447円から帰着時間を考慮することで4564円（2.6%）まで上昇し、容量50個の制約を導入することで4709円（5.9%）に上昇しました。さらに厳しい容量制約を設定することで5238円（17.8%）まで増加しました。
    
Nagoya問題例では、基礎値である13591円から帰着時間を考慮することで14472円（6.5%）まで上昇し、容量50個の制約を導入することで14508円（6.8%）に上昇しました。さらに厳しい容量制約を設定することで16547円（21.8%）まで増加しました。
    
車体のサイズを大きくするか小さくするかは、他のコスト（メンテナンス、車庫、ドライバーなど）にも依存しますが、上記の差を上回らない限り、大きな車体を使用する方が経済的でしょう。
    
# まとめと今後の展望
    
今回は、最も基本的な配送設定から始めて、「全てを配る」制約、帰着時間制約、容量制約の運用費への影響を調査しました。問題設定によって最大で21%まで悪化することが観察できました。
    
次回は、希望配送時間帯制約、勤務時間制約、休憩時間制約の影響を調査します。