A Heuristic Algorithm for Crowdshipping Problem with Time Windows

摘要

電子商務的興起帶動了大量包裹配送的需求，如何降低運輸成本一直是電子商務在思考的議題，同時隨著環保意識的抬頭，?多物流業者也開始考量如何降低碳排放，一種新興的物流方式為「群眾運輸」，將物流配送外包給一般群眾（即臨時駕駛員），在其原始行程的路徑中稍微繞路或是順路地完成包裹配送，此問題為臨時駕駛員車輛路徑問題(Vehicle Routing Problem with Occasional Drivers VRPOD)，由於該配送模式有降低運輸成本及碳排放等優點，故近來有越來越多考量群眾運輸的相關文獻及研究。 本研究將群眾運輸應用到物品共享的配送上，考量在物品共享的平台上需求者及供給者的配對，並提供包括群眾運輸的三種配送方式：自行取貨、宅配和鄰近取貨，每一種配送方式都有不同的成本及收益，在考量需求者、供給者及臨時駕駛員的時窗限制下，媒合需求者及供給者並選擇最佳的配送模式以最大化平台的利益。透過建立一個混合整數規劃的數學模型，以及另一個選取最佳運輸組合的數學模型做為比較，研究結果發現使用運輸組合的數學模型求解效率較佳，可求解的問題規模也較大。 對於更大例題，本研究透過M1：限制（臨時）駕駛員路徑數輛、 M2：將節點透過k-means分類及M3：減少鄰近取貨需求者組合三個方法來減少產生運輸組合的數量並減少求解時間，結果顯示M2較容易因不同例題受限於集群數，進而影響求解效果，相較之下M1求解效果則較穩定，而M3適合與其他方法搭配使用，且在大例題中效果較為顯著。雖然減少越多運輸組合，找到的解較容易變差，但是根據例題測試，三個方法搭配使用可以保留各自優點達到互補的效果。另外，本研究使用滾動式時窗做為另一啟發式解法的比較，其得到的解差於使用其他三種方法，因此較不適用於本研究探討的問題。

獎項日期	2020
原文	English
監督員	Shiow-Yun Chang (Supervisor)