## CROWDDELIVER: Planning City-Wide Package Delivery Paths Leveraging the Crowd of Taxis

[crowddeliver: Planning City-Wide Package Delivery Paths Leveraging the Crowd of Taxis ](https://ieeexplore.ieee.org/abstract/document/7575702)

## Abstract
快遞需求量提升，本文提出經濟的快遞服務: **CROWDDELIVER** 。
設計分為兩階段，第一階段:透過**歷史計程車軌跡數據**來識別給定起終點的最短包裹傳遞路徑並估計時間。第二階段:開發**即時調度算法**，根據實時請求找出最佳路徑。

## Introduction
隨著快遞需求量提升，__減少遞送時間__、__降低遞送成本__，為首要目標，透過 **包裹與計程車乘客共乘** 的方式，在不提升成本的前提下，最大化計程車載客與送貨效益。

透過以上方法將有以下優點:
1. **遞送機會豐富**:計程車為目前城市主流的交通方式。
1. **全時段營業**:計程車在深夜等非尖峰時段仍會營業，因此這項遞送服務可以全天候不間斷運行。
1. **符合環保效益**:只需透過原在城市中的計程車進行遞送，不須額外指派車輛，造成跟多污染排放以及更多環境負擔。

**問題與挑戰** : 因為計程車載客的距離有限，無法達成遠距離的包裹遞送，因此需要多輛計程車進行多輛中繼傳遞，因此產生以下兩項問題與挑戰。
1. 中繼遞送的**時間估計**問題。
1. 乘客起始目的路線與包裹遞送的**路徑規劃調度**。

本文主要貢獻 :
1. 利用計程車之間 **非刻意** 合作達成遞送目標POI減少建設包裹儲存站之需求。註:(POI)熱門景點，如餐廳、商場、體育館等。
1. 透過 __CROWDDELIVER兩階段__ 路線規劃找出最佳路徑
* **階段一**:透過歷史計程車路線以及(NHPP)模型預測最短路徑與估計時間
* **階段二**:透過實時的叫車需求演算法(AdaPlan)所預估時間來與第一階段之時間做比較和優化。

## Assumptions
* **Assumptions 1**
計程車以載送乘客為主要目標，計程車尖峰時段不能被用以遞送包裹需求。

* **Assumptions 2**
假定在某種適當的激勵下，計程車司機都會願意接下遞送需求的訂單。

* **Assumptions 3**
所有包裹都經過追蹤與管理確保包裹損壞或遺失之問題能夠被解決。

## Problem Statement
**給定條件**
1. 道路網路 G(N,E) 和 包裹寄放站集合CS
1. 計程車歷史軌跡集合 Tr
1. 即時計程車訂單TOR、即時包裹訂單PR

==**目標 : 最小化包裹交付時間**==

**限制條件**
1. tor.tt > pr.tp 包裹訂單請求時間需早於計程車訂單請求時間。
2. 計程車須在完成當下包裹遞送任務後才能繼續接受遞送請求。

## Overview of CROWDDELIVER System
1. **Data Pre-processing**
對POIs進行篩選，先選擇**靠近道路兩側的POI**，並對於路網上的邊**每一個行駛方向只選擇一個POI**。將行駛軌跡轉換為一系列邊，並定義起始與目標邊以及行程開始結束之時間。
1. **Offline Trajectory Data Mining**
分析過去數據，乘客乘坐計程車的時段以及路徑來規劃包裹形成。選擇**適當的POI**作為中繼站最小化包裹遞送時程。
1. **Online Package Routing1**
透過**歷史資訊**與**即時數據**相互比較計算得出最佳路徑與時間。

## TWO-PHASE APPROACH
### **Phase I** : Offline Tragectory Data Mining

根據**歷史軌跡**做遞送路線規劃，首先先將一整天24h分成不同的time-slot，再根據不同的時段進行計算。

* **Step1 : 過濾出可遞送的歷史乘客軌跡**

<font color=#800000>*Ddist(Tri.o, loc(csi)) < δ (1)*
*Ddist(Tri.d, loc(csj)) < δ (2)*</font>

找出所有Csi-Csj之間的軌跡透過以上兩個方程式來**確保Csi、Csj和乘客的起終點不會過遠**。

* **Step2 : 計算Csi、Csj之間的權重(等待時間+寄送時間)**
篩選出可遞送的乘客軌跡後透過軌跡計算各Cs間權重。

<font color=#800000>*tc = WaitingTime + DrivingTime*</font>

WaitingTime由 **頻率倒數(1/λ)** 來表示平均等待時間。另外DrivingTime由**每一次兩站遞送時間做平均**來計算得。

將WaitingTime 和 DrivingTime 分開維度做圖表觀察，**等待時間低於一小時的行程只占總形成的7%**，然而**行車時間低於一小時的行程約佔總行程的70%**。
表示每段行程很大的比例花在**等待時間**。

#### Time-Dependent Routing Table Building:
有些車流量小甚至沒有車流量的區域可能會有Cs之間邊界權值有無限大的可能，因此可能需要透過其他 **熱門路線(hot-line)** 來達成，形成 **Virtual hot-line** 。

:::success
⛳**形成 Virtual hot-line 條件**
1. **Spatially Close**
若需要中繼站來進行轉送，兩個中繼站之間的距離要小於β。
1. **Move forward**
中繼站必須更接近目的地點。
1. **Limited number of transshipment**
中繼站的轉寄次數不能超過某常數C。
1. **Minimum time cost on virtual hot-line**
必須從所有virtual hot-line中選出邊界權值最小的一條。找到所有hot-line or Virtual hot-line之後透過 **Simple Top-K Algo**. 來規畫路徑。
:::

接著需要透過演算法(B. C. Dean, Continuous-time dynamic shortest path algorithms, M.S.thesis, Dept. Comput. Sci., MIT, Cambridge, MA, USA, 1999.) 製作 **Time-Dependent Routing Table** 來紀錄每一個包裹中繼站之間的**最短距離**，

因為並不是每條包裹遞送路徑都靠近Cs且能在**Time-Dependent Routing Table**查詢，因此需要**Simple Top-K Algo**。

**Simple Top-K Algo**
* **Step1** : 找出與包裹寄送點與目的點最近的K個中繼站。並將與**寄送點最近的前K個中繼站設為Set1**，與**目的點最近的前K個中繼站設為Set2**。
* **Step2** : 透過**All-Pairs Shortest path**最短路徑算法找到兩set中每個元素之間路徑，形成集合Path。
* **Step3** : 若path屬於空集合，則無路徑，若有**擇其最短路徑**。

### **Phase ll : Online Package Routing**

根據歷史行車軌跡以及上述演算法，我們可以依照路徑並等待叫車機會對貨物進行遞送，然而這樣的方法是**根據統計資料所得出的結果**，需要搭配**即時的叫車計畫來提高效率**。

**AdaPlan**
* **Step1**:在開始前會先依據PhaseI所安排的路線進行等待，若出現某即時行程之 **DrivingTime + 此行程目的地到包裹目的的RoutingTable預估時間** < **包裹從出發地到目的地之RoutingTable預估時間**，則將包裹安排於此行程。

* **Step2**:當此行程結束後，將包裹安置於**行程目的地附近的中繼站**，並將**包裹請求時間設為安置時間**，另外包裹之**出發地設為該中繼站**。
* **Step3**:最後重新**計算並更新RoutingTable**。

總結來說此演算法透過**過去乘客軌跡資訊**來建立基礎的路徑規劃及時間預測演算法，**根據基本預測動態的調整路徑規劃**來指引報果遞送路徑並達到更好的效果

## EVALUATION
為了評估Crowddeliver算法之效率，對案例進行研究並展示。

### Experimental Setup
1. **實驗數據**

對真實世界數據進行統計，統計中國杭州市7614台計程車的軌跡數據，以及確立POI包裹交換站與道路網絡等訊息。將資料分為測試集和訓練集以模擬實際計程車請求，測試AdaPlan效能。

3. **模擬**

在上述所蒐集的數據中並不包含**包裹交付訂單**和**計程車訂單請求**的資訊，因此本文透過一些方式來進行模擬。

在**包裹交付**的部分，透**過隨機生成起始與目的點的方式**來模擬訂單，此外產生後的模擬定待會替除掉**短距離訂單( short-distance OD pairs)**，因為這比較少出現也不符合效益。

另外在**即時叫車訂單**部分，因為所掌握的資料只有軌跡路徑，沒有實際叫車訂單資訊，因此透過*replay-and-sample*來做模擬。

Replay : 在測試時間內 Replay 所有計程車軌跡。
Sample : 以固定比例採樣認其軌跡為線上叫車訂單。

7. **測試指標**
本文設定兩個指標來評估AdaPlan algorithm
* **Success Rate**
Formula :
<font color=#800000>AdaPlan完成的包裹訂單中 (**運送時間<要求遞送時間** 之**訂單數量**) / (總包裹數量)。</font>
當 Success Rate 數值越高 AdaPlan效能越好。
* **Number of Transshipments**
表包裹中繼轉運的次數，越低的次數可能可以帶來較低的成本與風險。
Formula :
<font color=#800000>Numtrans = Numrelays = Nump_taxis − 1.</font>
(計程車載送次數 - 1)

### Baseline Algorithms
透過與 **FCFS** 以及 **DesCloser**兩種算法來比較並呈現CROWDDELIVER的性能表現。
* **FCFS**
如出現靠近包裹的計程車叫車訂單，就立刻把包裹分派過去。(未考慮靠近或遠離包裹目的地)
* **DesCloser**
如出現靠近包裹的計程車叫車訂單且**叫車目的能夠更加靠近包裹遞送目的**，則將包裹分派過去。

### Experimental Objectives
* Q1 : 遞送一個包裹需要多少運算資源(Computational Resource)?
* Q2 : 成功遞送率(**Success Rate**)為多少?
* Q3 : 轉送次數(**Number of Transshipments**)為多少?
* Q4 : CROWDDELIVER 和最佳解 (**optimal Sol.**)差距為多少?
* Q5 : 此系統一小時能夠遞送多少包裹 (Per Hours)

### Experimental Results
#### Results of Response Time
對於三種方法(FCFS、DesCloser、AdaPlan)之響應時間計算做以下分別討論。
* **FCFS** : 只需要符合 Ddist(tor.o, pr.o) < δ和Ddist(tor.d, {CS}) < δ 的 **第一輛** 車即可，因此運算較簡易。
* **DesCloser** : 除符合 Ddist(tor.o, pr.o) < δ和Ddist(tor.d, {CS}) < δ 外，還須計算 CS 是否**更加接近目的地**。
* **AdaPlan** : 需要在每個CS做**反覆的比較、查找並更新**，因此運算最為複雜。
▲在**不同採樣率**下不同演算法包裹遞送過程之**累計響應時間**統計圖。
由圖可簡單觀察，**Sampling Rate越高，Response Time越大**，原因很直觀，採樣率越高表越多計程車是透過叫車系統來載客，系統需花費更多時間來計算並篩選計程車是否符合條件，因此花費時間越多。
另一方面來看，在不同演算法的響應時間比較中可以觀察到FCFS雖看似計算最為基礎但所花費的總響應時間最多，作者猜測很可能是因為**FCFS需要更多的轉遞送次數(transshipments)**造成**計算次數增加**，進而**累積更長的響應時間**。

#### Results of Success Rate

* **Success Rate w.r.t Sampling Rate**

▲ **Success Rate 在 DesCloser 和 AdaPlan 算法下和Sampling Rate呈正相關**。FCFS則和Sampling Rate較無關聯。由此現象可推測原因為，**越多的叫車訂單能使等待時間降低**，進而提高 Success Rate，然而在**FCFS情況下，包裹可能會被遞送至遠離目的CS，造成更多轉運次數**而影響Success Rate。

##### **Success Rate w.r.t Region**
實驗前首先根據包裹**起始地區**與**目的地區**將不同訂單分為三大類別 :

**▲ Category I :** 由**熱門地區**送至**熱門地區**
**▲ Category II :** 由**非熱門地區**送至**熱門地區** or 由**熱門地區**送至**非熱門地區**
**▲ Category III:** 由**非熱門地區**送至**非熱門地區**

AdaPlan無論是任何Category下都表現最好的，即便是CategoryIII，都有六成的貨物能在六小時內送達。

* **Success Rate w.r.t Time**
▲在 **:sunny:DayTime** **Work Day相較於Rest Day有更短的平均遞送時間和更高的成功率**
相反的**在 :first_quarter_moon_with_face: NightTime Rest Day相較於Work Day有更短的平均遞送時間和更高的成功率**。
* **Number of Transshipments**
實驗結果顯示AdaPlan在不同地區條件下遞送貨物**皆有著最少的轉運次數**。另外在**夜晚遞送的轉運次數稍微較白天多一些**，平均皆在**四次**左右。
* **AdaPlan v.s. Optimal**
**Optimal 比較**
假設所有計程車與乘客資訊都是已知，計算所有包裹可到達路線從中選出最優解。
最優解的計算選擇過程平均需要**花費14280.9秒**，計算出可送達時間為**1.164小時**，相比之下**AdaPlan**只**需要0.8秒**即可計算完成，所規畫出來的平均遞送時間為**2.337小時**。
雖然使用AdaPlan所花費的**平均遞送時間為最佳規劃的兩倍**，但相比Optimal Sol.，AdaPlan計算所花的**響應時間非常微小**。
* **Transport Capacity**
系統的運輸能力(運輸量)是實際執行時的必要考量因素。
▲ 每小時產生包裹數量**小於1000**時，成功投遞的包裹數量和產生數量**呈正比**(約成功投遞9成)，然而每小時產生包裹超過1000時，能夠成功投遞的數量**逐漸趨緩**，**不再成正比增加**，說明了此系統一小時內在實驗假設情況下的運輸能力約為**每小時985個包裹**。
▲ **包裹轉運站數量**也相當程度的**影響著系統的運輸能力**。實驗將每小時包裹請求遞送數量設為定量**1200**可觀察到在**轉運站數量為50**的情況下，**運輸能力十分低落**，在大約700個轉運站能夠讓每小時運輸容量提升到約900個包裹。
實驗中隨機選取轉運站地點，雖然**轉運站地點的選擇也會影響運輸容量**，但無論如何選取，趨勢皆為 : **轉運站越多運輸容量越大。**
## Discussion
尚未解決的問題。
* **Package Delivery Request**
此研究專注於在**任何包裹遞送路徑**的情況下，尋求近似最佳路徑規劃，因此透過**隨機模擬**的方式產生遞送包裹來做實驗，可能會與現實有偏差，未來需要透過更多**實際數據來計算實際的包裹流向分布**且須透過更多**真實的包裹遞送請求數據**整合到整個系統架構中。

* **Real-time Taxi Ordering Request**

1. 關於計程車**訂單問題**，此研究並沒有收集到**手機叫車應用程式的相關資訊**，此資訊對於此系統極為重要，未來將蒐集更多關於**應用程式叫車訂單**相關的資訊。
2. 此外，未來可朝著**不須事先知道目的地**也可達成遞送任務的目標演算法前進。
3. 最後，由實驗可得知**AdaPlan和Optimal sol.的遞送時間仍有一段差距**，應可更優化算法來達成更好的效率。

* **Issues Regarding Data Sources**
系統所蒐集的數據包含**POI**、**道路網絡**、**車輛軌跡**都需要不斷**更新**，才能應對當下的遞送規劃。
* **Others**
**包裹大小**，**司機的獎勵機制**、**包裹容器**等都是其他需要考量的因素。