あらすじ
前回、制約のない配送設定（TSP）から始まり、現実世界のシナリオでも戦えるように、出発時間・到着時間制約（VRP）と容量制約（CVRP）を導入しました。さらに、小型な車両を使用することで容量制約をより厳しくした（CVR-HALF）シナリオの影響を紹介しました。
Nagoya問題例では、基礎値である13,591円から帰着時間を考慮することで14,472円（6.5%）まで上昇し、容量50個の制約を導入することで14,507円（6.8%）に増加しました。さらに厳しい容量制約を設定することで16,547円（21.8%）まで増加しました。
| Nagoya | 台数 | 時給(総移動時間) | 燃料費(総移動距離) | 合計 | 基準との差分 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| TSP | 1 | 10303(34343) | 3288(134694) | 13591(169037) | - | ||||||||
| VRP | 4 | 10986(36619) | 3486(142828) | 14472(179447) | +3台 +6.5% | ||||||||
| CVRP | 4 | 10996(36654) | 3511(143851) | 14507(180505) | +3台 +6.7% | ||||||||
| CVRP-HALF | 8 | 12421(41403) | 4126(169042) | 16547(210445) | +7台 +21.7% | ||||||||
| $\hspace{38em}$ | |||||||||||||
Optimindの問題例では、基礎値である4,447円から帰着時間を考慮することで4,564円（2.6%）まで上昇し、容量50個の制約を導入することで4,709円（5.9%）に増加しました。さらに厳しい容量制約を設定することで5,238円（17.8%）まで増加しました。
| Optimind | 台数 | 時給(総移動時間) | 燃料費(総移動距離) | 合計 | 基準との差分 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| TSP | 1 | 3513(11709) | 935(38292) | 4448(50001) | - | ||||||||
| VRP | 3 | 3624(12081) | 940(38512) | 4564(50593) | +2台 +2.6% | ||||||||
| CVRP | 4 | 3749(12495) | 961(39349) | 4710(51844) | +3台 +5.9% | ||||||||
| CVRP-HALF | 8 | 4124(13746) | 1114(45635) | 5238(59381) | +7台 +17.8% | ||||||||
| $\hspace{38em}$ | |||||||||||||
台数と費用増加を許容したことで、より現実世界に近づきましたが、それでもまだまだ現実とは遠いです。今回は、よりお客様の利便性を高めるために、時間枠指定制約の導入に伴う代償を紹介します。
Vehicle Routing Problem with Time Windows: 時間枠指定
お客様が限られた時間帯でしか対応できない場合、特定の時間帯内での訪問が必要となります。この制約を加えた配送問題は、「(Capacitated) Vehicle Routing Problem with Time Windows（CVRP-TW）」として知られています。他にも、複数な時間帯を考慮する問題は「(Capacitated) Vehicle Routing Problem with Multiple Time Windows（CVRP-MTW）」であり、時間枠に対して遅れをある程度許容できる問題は「(Capacitated) Vehicle Routing Problem with Soft Time Windows（CVRP-STW）」も存在します。今回は、CVRP-TWのみを扱います。
待機時間
時間枠の開始時間前に到着する場合、以下の二つの行動が考えられます：
- 時間枠を無視して指定された時間前に荷物を届ける。
- 時間枠の開始時間まで待つ。
事前の連絡やお客様に迷惑がかかる上で1は現実のシナリオでも発生することがありますが、基本的には2で計画を組むことが望ましいと考えられます。
待機時間による不自然な計画
例えば、配送する車両が自社ではなく、燃料費が自社の負担ではなく、時給だけを支払えばいい設定を考えると、距離に対して費用がかからないため、開始時間と到着時間が同じ場合、下記の両方の計画が同じ費用になってしまいます。現実世界では非常に不自然に見えるかもしれませんが、最適化問題の観点では設定上、コストが同じなので同じく「良い」計画として出力されることがあります。
この問題を解決するために、待機時間にかかる費用（待機時間料）を時給費よりも小さい値に設定することで、待機時間が長い計画が費用が安いと認識されるようにできます。距離に対する費用があれば、余計な行き戻りが悪いと判定され、より現実的かつ効率的な計画が作られます。
計算実験1
日本では基本的に以下の時間枠が選択可能となっています。
- 9:00-12:00
- 12:00-14:00
- 14:00-16:00
- 16:00-18:00
- 18:00-20:00
- 指定なし
前回に紹介したCVRPの設定に加え、各配達先に対して、上記の６通りの時間枠の中からランダムに一つを付与しました。この問題例をCVRP-TWと呼びます。
| CVRP-TW | Nagoya | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Driver | 配達件数 | 開始時間 | 到着時間 | 時給(総移動時間) | 時給(待ち時間) | 燃料費(総移動距離) | 時給+燃料費 | ||||||
| Alice | 22 | 06月1日08:00:00 | 06月1日16:36:15 | 2279(7597) | 3053(10178) | 790(32349) | 6122 | ||||||
| Bob | 45 | 06月1日08:00:00 | 06月1日20:16:59 | 4254(14181) | 911(3038) | 1418(58098) | 6584 | ||||||
| Charles | 43 | 06月1日08:00:00 | 06月1日20:11:10 | 4374(14581) | 1047(3489) | 1496(61266) | 6917 | ||||||
| David | 44 | 06月1日08:00:00 | 06月1日20:11:07 | 3962(13205) | 1279(4262) | 1245(51013) | 6485 | ||||||
| Eve | 46 | 06月1日08:00:00 | 06月1日20:14:20 | 3835(12782) | 1103(3678) | 1361(55758) | 6299 | ||||||
| 18704(62346) | 7394(24645) | 6310(258484) | 32407 | ||||||||||
| $\hspace{55em}$ | |||||||||||||
| CVRP-TW | Optimind | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Driver | 配達件数 | 開始時間 | 到着時間 | 時給(総移動時間) | 時給(待ち時間) | 燃料費(総移動距離) | 時給+燃料費 | ||||||
| Alice | 50 | 06月1日08:00:00 | 06月1日20:11:42 | 1701(5670) | 2470(8232) | 485(19889) | 4656 | ||||||
| Bob | 50 | 06月1日08:00:00 | 06月1日19:29:18 | 1365(4551) | 2042(6807) | 392(16076) | 3800 | ||||||
| Charles | 50 | 06月1日08:00:00 | 06月1日19:59:17 | 1535(5116) | 2412(8041) | 438(17942) | 4385 | ||||||
| David | 50 | 06月1日08:00:00 | 06月1日19:46:25 | 1450(4833) | 2266(7552) | 398(16320) | 4114 | ||||||
| 6051(20170) | 9190(30632) | 1714(70227) | 16955 | ||||||||||
| $\hspace{55em}$ | |||||||||||||
訪問したい時に訪問できないため、その場で数分待たなければならず、時間効率が低下します。
すぐ近くに配達先があっても（例: 12(左)/40(右), 14(左)/41(右)）、時間枠内でなければ訪問できないため、後で再び同じエリアに戻らなければなりません。そのため、移動が多くなり、移動効率が低下します。
| CVRP | CVRP-TW |
|---|---|
 |
 |
CVRPと比較して、Nagoya問題例では1台増加して32407-14507 = 17900（123.4%）の費用が増加し、待ち時間を無視しても17900-7394 = 10506（72.4%）が追加でかかりました。Optimind問題例では台数は増加していませんが、費用の増加は16955-4710 = 12245（260%）であり、待ち時間を除いて12245-9190 = 3055（64.9%）の費用が追加されました。
容量制約に比べて、時間枠指定制約の方が影響が大きいことが明らかになりました。
計算実験2
会社がより便利なサービスを提供するために、時間枠を2時間毎ではなく1時間毎、つまり選択可能な時間枠を倍にする場合、どれぐらいの費用が負担されるかを検証しました。この新しい設定をCVRP-TW-DOUBLEと呼びます。
| CVRP-TW-DOUBLE | Nagoya | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Driver | 配達件数 | 開始時間 | 到着時間 | 時給(総移動時間) | 時給(待ち時間) | 燃料費(総移動距離) | 時給+燃料費 | ||||||
| Alice | 7 | 06月1日08:00:00 | 06月1日11:14:09 | 1115(3716) | 1120(3733) | 398(16316) | 2633 | ||||||
| Bob | 40 | 06月1日08:00:00 | 06月1日19:44:35 | 4452(14839) | 1031(3436) | 1496(61300) | 6979 | ||||||
| Charles | 25 | 06月1日08:00:00 | 06月1日16:35:58 | 3179(10596) | 1609(5362) | 1114(45621) | 5901 | ||||||
| David | 42 | 06月1日08:00:00 | 06月1日20:15:35 | 4466(14886) | 1215(4049) | 1508(61785) | 7189 | ||||||
| Eve | 8 | 06月1日08:00:00 | 06月1日11:39:12 | 1303(4342) | 1203(4010) | 408(16731) | 2914 | ||||||
| Frank | 40 | 06月1日08:00:00 | 06月1日20:03:17 | 4424(14747) | 1395(4650) | 1571(64372) | 7390 | ||||||
| George | 38 | 06月1日08:00:00 | 06月1日19:37:33 | 4110(13701) | 1606(5352) | 1505(61656) | 7221 | ||||||
| 23048(76827) | 9178(30592) | 8001(327781) | 40227 | ||||||||||
| $\hspace{57em}$ | |||||||||||||
| CVRP-TW-DOUBLE | Optimind | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Driver | 配達件数 | 開始時間 | 到着時間 | 時給(総移動時間) | 時給(待ち時間) | 燃料費(総移動距離) | 時給+燃料費 | ||||||
| Alice | 42 | 06月1日08:00:00 | 06月1日18:26:28 | 1601(5336) | 2116(7052) | 489(20039) | 4206 | ||||||
| Bob | 50 | 06月1日08:00:00 | 06月1日19:56:08 | 2237(7455) | 1654(5513) | 675(27664) | 4566 | ||||||
| Charles | 49 | 06月1日08:00:00 | 06月1日20:10:55 | 1883(6277) | 2453(8178) | 570(23349) | 4906 | ||||||
| David | 48 | 06月1日08:00:00 | 06月1日20:13:15 | 2159(7197) | 2399(7998) | 646(26482) | 5205 | ||||||
| Eve | 11 | 06月1日08:00:00 | 06月1日11:11:02 | 305(1018) | 1153(3844) | 88(3623) | 1547 | ||||||
| 8185(27283) | 9776(32585) | 2469(101157) | 20430 | ||||||||||
| $\hspace{58em}$ | |||||||||||||
一つのエリアに小さい番号と大きい番号（つまり1日の中で違う時間帯で何回も訪問されている）や、何色も混ざっていることがコスト増加に大きな影響を与えています。
CVRP-TWと比較して、Nagoya問題例では2台増加して40227-32407 = 7820（24.1%）の費用が増加し、Optimindの問題例では1台増加して20430-16955 = 3475（20.5%）の費用が増加しました。
時間枠制約の導入自体と比較すると、差は大きくないですが、額としてはかなりの負担になります。そのため、時間枠の選択数を増やす前にはかなりな検討が必要になるでしょう。
まとめ
時間枠指定制約の代償は大きく、待ち時間による時間効率低下や複数回同じエリア訪問による移動効率低下は容量制約よりも重いことが見れました。時間枠をより細かくすることでお客様は喜ぶかもしれませんが、その代償は高いことも分かりました。
Nagoyaの問題例では、基礎値である13,591円から時間枠を考慮することで32,407円（138.4%）まで上昇し、時間枠をより細かくすることで40,227円（196.0%）に上昇しました。
Optimindの問題例では、基礎値である4,447円から時間枠を考慮することで16,955円（281.2%）まで上昇し、時間枠をより細かくすることで20,430円（359.3%）に上昇しました。
| Nagoya | 台数 | 時給(総移動時間) | 待ち時間費(待ち時間) | 燃料費(総移動距離) | 合計 | 基準との差分 | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| TSP | 1 | 10303(34343) | 0 | 3288(134694) | 13591(169037) | - | |||||||
| VRP | 4 | 10986(36619) | 0 | 3486(142828) | 14472(179447) | +3台+6.5% | |||||||
| CVRP | 4 | 10996(36654) | 0 | 3511(143851) | 14507(180505) | +3台+6.7% | |||||||
| CVRP-HALF | 8 | 12421(41403) | 0 | 4126(169042) | 16547(210445) | +7台+21.7% | |||||||
| CVRP-TW | 5 | 18704(62346) | 7394(24645) | 6310(258484) | 32407(345475) | +4台+138.4% | |||||||
| CVRP-TW-DOUBLE | 7 | 23048(76827) | 9178(30592) | 8001(327781) | 40227(435200) | +6台+196.0% | |||||||
| $\hspace{50em}$ | |||||||||||||
| Optimind | 台数 | 時給(総移動時間) | 待ち時間費(待ち時間) | 燃料費(総移動距離) | 合計 | 基準との差分 | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| TSP | 1 | 3513(11709) | 0 | 935(38292) | 4448(50001) | - | |||||||
| VRP | 3 | 3624(12081) | 0 | 940(38512) | 4564(50593) | +3台+2.6% | |||||||
| CVRP | 4 | 3749(12495) | 0 | 961(39349) | 4710(51844) | +3台+5.9% | |||||||
| CVRP-HALF | 8 | 4124(13746) | 0 | 1114(45635) | 5238(59381) | +7台+17.8% | |||||||
| CVRP-TW | 4 | 6051(20170) | 9190(30632) | 1714(70227) | 16955(121029) | +3台+281.2% | |||||||
| CVRP-TW-DOUBLE | 5 | 8185(27283) | 9776(32585) | 2469(101157) | 20430(161025) | +4台+359.3% | |||||||
| $\hspace{50em}$ | |||||||||||||
次回予告
次回は、現在の課題である休憩なしで毎日08:00から20:00の12時間以上働くといった労働時間の過酷さに対処するために、最大勤務時間と休憩制約を追加する予定です。