進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-1606202018202600
論文名稱(中文) 以啟發式演算法求解具有時窗限制之群眾運輸問題
論文名稱(英文) A Heuristic Algorithm for Crowdshipping Problem with Time Windows
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系
系所名稱(英) Department of Industrial and Information Management
學年度 108
學期 2
出版年 109
研究生(中文) 劉騏賢
研究生(英文) Chi-Hsien Liu
學號 R36084029
學位類別 碩士
語文別 中文
論文頁數 67頁
口試委員 指導教授-張秀雲
口試委員-蔡丁鴻
口試委員-陳明德
中文關鍵字 混合整數規劃  群眾運輸  臨時駕駛員車輛路徑問題  滾動式時窗 
英文關鍵字 Mixed Integer Programming  Crowdshipping  Vehicle Routing Problem with Occasional Drivers  Rolling Horizon 
學科別分類
中文摘要 電子商務的興起帶動了大量包裹配送的需求,如何降低運輸成本一直是電子商務在思考的議題,同時隨著環保意識的抬頭,許多物流業者也開始考量如何降低碳排放,一種新興的物流方式為「群眾運輸」,將物流配送外包給一般群眾(即臨時駕駛員),在其原始行程的路徑中稍微繞路或是順路地完成包裹配送,此問題為臨時駕駛員車輛路徑問題(Vehicle Routing Problem with Occasional Drivers, VRPOD),由於該配送模式有降低運輸成本及碳排放等優點,故近來有越來越多考量群眾運輸的相關文獻及研究。
本研究將群眾運輸應用到物品共享的配送上,考量在物品共享的平台上需求者及供給者的配對,並提供包括群眾運輸的三種配送方式:自行取貨、宅配和鄰近取貨,每一種配送方式都有不同的成本及收益,在考量需求者、供給者及臨時駕駛員的時窗限制下,媒合需求者及供給者並選擇最佳的配送模式以最大化平台的利益。透過建立一個混合整數規劃的數學模型,以及另一個選取最佳運輸組合的數學模型做為比較,研究結果發現使用運輸組合的數學模型求解效率較佳,可求解的問題規模也較大。
對於更大例題,本研究透過M1:限制(臨時)駕駛員路徑數輛、 M2:將節點透過k-means分類及M3:減少鄰近取貨需求者組合三個方法來減少產生運輸組合的數量並減少求解時間,結果顯示M2較容易因不同例題受限於集群數,進而影響求解效果,相較之下M1求解效果則較穩定,而M3適合與其他方法搭配使用,且在大例題中效果較為顯著。雖然減少越多運輸組合,找到的解較容易變差,但是根據例題測試,三個方法搭配使用可以保留各自優點達到互補的效果。另外,本研究使用滾動式時窗做為另一啟發式解法的比較,其得到的解差於使用其他三種方法,因此較不適用於本研究探討的問題。
英文摘要 The boom of e-commerce has promoted a great demand for delivery. Meanwhile, with the rise of environmental awareness, many logistics companies start to ponder how to reduce carbon emission. A new logistics way is “crowdshipping” that package delivery is outsourced to the crowd, or occasional drivers. They deliver parcels through a detour from their original route or on their way. This problem is called Vehicle Routing Problem with Occasional Drivers (VRPOD). This thesis applies crowdshipping to delivery of item-sharing platform. It assigns the supplied items to compatible requesters and decides a best delivery pattern for each shared item among three alternatives, including self-sourcing, home delivery and neighborhood delivery, to maximize the platform’s profit. We proposed a mixed integer programming model and another “best transportation combinations” model and made a comparison. The results show that the latter has better efficiency and can solve larger-scale problems. As for still larger instances, we adopted three heuristic methods based on the second model to reduce the number of transportation combinations and solution time. The results indicate that heuristic methods can acquire a solution within a reasonable time. Besides, combining three methods can retain their respective advantages and they complement one another well. Finally, we applied rolling horizon to this problem but it’s not suitable for this problem owing to its poorest solution quality.
論文目次 摘要 i
Extended Abstract ii
致謝 vi
表目錄 ix
圖目錄 x
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 4
1.3研究範圍與限制 5
1.4研究流程與論文架構 5
第二章 文獻探討 7
2.1車輛路徑問題(VRP) 7
2.2收送貨相關文獻 8
2.2.1回程取貨車輛路徑問題(VRPB) 8
2.2.2收送貨車輛路徑問題(VRPPD) 10
2.3多商品收送貨問題(m-PDTSP) 11
2.4臨時駕駛員車輛路徑問題VRPOD 12
2.5共享經濟 15
2.5.1影響共享經濟參與的因素 15
2.5.2共享經濟應用之相關文獻 17
2.6小結 20
第三章 研究方法 22
3.1問題描述 22
3.2研究假設 24
3.3符號定義 26
3.4混合整數規劃模型建構 28
3.5演算法建構 33
3.5.1運輸組合模型 33
3.5.2啟發式方法 42
3.5.3滾動式時窗(rolling horizon) 44
第四章 例題測試與數據分析 47
4.1例題與參數介紹 47
4.2模型求解結果 50
4.2.1模型一、二求解結果 50
4.2.2啟發式方法求解效果 52
4.2.3滾動式時窗求解效果 58
4.3小結 60
第五章 結論 61
5.1研究結論 61
5.2未來研究方向 62
參考文獻 63
參考文獻 社團法人台灣協作暨共享經濟協會(民107年7月25日),2017台灣暨亞太地區共享經濟發展白皮書,取自https://issuu.com/seataiwan/docs/________________。
Agatz, N., Erera, A., Savelsbergh, M. and Wang, X. (2012), Optimization for dynamic ride-sharing: A review, European Journal of Operational Research, 223(2), 295-303.
Ai, T. J. and Kachitvichyanukul, V. (2009), A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 36(5), 1693-1702.
Allahviranloo, M. and Baghestani A. (2019), A dynamic crowdshipping model and daily travel behavior, Transportation Research Part E: Logistics and Transportation Review, 128, 175-190.
Archetti, C., Savelsbergh, M. and Speranza M.G. (2016), The vehicle routing problem with occasional drivers, European Journal Operational Research, 254 (2), 472-480.
Arslan, A.M., Agatz, N., Kroon, L. and Zuidwijk, R. (2019), Crowdsourced Delivery—A Dynamic Pickup and Delivery Problem with Ad Hoc Drivers, Transportation Science, 53(1), 222-235.
Barr, A. and Wohl, J. (2013, March 28), Exclusive: Wal-Mart may get customers to deliver packages to online buyers, REUTERS – Business, from https://www.reuters.com/article/us-retail-walmart-delivery/exclusive-wal-mart-may-get-customers-to-deliver-packages-to-online-buyers-idUSBRE92R03820130328
Behrend, M. and Meisel, F. (2018), The integration of item-sharing and crowdshipping: Can collaborative consumption be pushed by delivering through the crowd?, Transportation Research Part B: Methodological, 108, 122-140.
Behrend, M., Meisel, F., Fagerholt, K. and Andersson, H. (2019), An exact solution method for the capacitated item-sharing and crowdshipping problem, European Journal of Operational Research, 279(2), 589-604.
Berbeglia, G., Cordeau, J.-D. and Laporte, G. (2010), Dynamic pickup and delivery problems, European Journal of Operational Research, 202(1), 8-15.
Böcker, L. and Meelen, T. (2017), Sharing for people, planet or profit? Analysing motivations for intended sharing economy participation, Environmental Innovation and Societal Transitions, 23, 28-39.
Cattaruzza, D., Absi, N., Feillet, D. and Vigo, D. (2014), An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows, Computers & Operantions Research, 51, 257–267.
Cheung, R. K. and Hang, D. D. (2001), Multi-attribute label matching algorithms for vehicle routing problems with time windows and backhauls, IIE Transactions, 35(3), 191-205
Cordeau, J.-F. and Laporte, G. (2007), The dial-a-ride problem: Models and algorithms, Annals of Operations Research, 153 (1), 29-46.
Dahle, L., Andersson, H., Christiansen, M. and Speranza, M. G. (2019), The pickup and delivery problem with time windows and occasional drivers, Computers & Operations Research, 109, 122-133.
Dantzig, G.B. and Ramser, J.H. (1959), The truck dispatching problem, Management Science, 6(1), 80-91.
Dell'Amico, M., Hadjicostantinou, E., Iori, M. and Novellani, S. (2014), The bike sharing rebalancing problem: Mathematical formulations and benchmark instances, Omega, 4, 7-19.
D'Onfro, J. (2015, June 16), Amazon might start paying normal people to deliver its packages, BUISNESS INSIDER, from https://www.businessinsider.in/Amazon-might-start-paying-normal-people-to-deliver-its-packages/articleshow/47694738.cms
Gajpal, Y. and Abad, P.L. (2009), Multi-ant colony system (MACS) for a vehicle routing problem with backhauls, European Journal of Operational Research, 196(1), 102-117.
Gdowska, K., Viana, A. and Pedroso, J.P. (2018), Stochastic last-mile delivery with crowdshipping, Transportation Research Procedia, 30, 90-100.
Goetschalckx M. and Jacobs-Blecha (1989), The vehicle routing problem with backhauls, European Journal of Operational Research, 42(1), 39-51.
Hernández-Pérez, H. and Salazar-González, J.-J. (2009), The multi-commodity one-to-one pickup-and-delivery traveling salesman problem, European Journal of Operational Research, 196(3), 987-995
Hernández-Pérez, H. and Salazar-González, J.-J. (2014), The multi-commodity pickup-and-delivery traveling salesman problem, Networks, 63(1), 46-59
Kloimüllner, C. and Raidl, G. R. (2017), Full‐load route planning for balancing bike sharing systems by logic‐based benders decomposition, Special Issue: Special Issue on Vehicle Routing and Logistics Optimization, 69(3), 270-289.
Lai, M. and Cao, E. (2010), An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows, Engineering Applications of Artificial Intelligence, 23(2), 188-195.
Macrina, G., and Guerriero, F. (2018), The Green Vehicle Routing Problem with Occasional Drivers, New Trends in Emerging Complex Real Life Problems, 357-366.
Marcucci, E., Pira, M. L., Carrocci, C. S., Gatta, V. and Pieralice, E. (2017), Connected shared mobility for passengers and freight: Investigating the potential of crowd- shipping in urban areas, 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), 839–843.
Miller, J., Nie, Y. M. and Stathopoulos, A. (2017), Crowdsourced urban package de- livery: Modeling traveler willingness to work as crowdshippers, Transportation Research Record: Journal of the Transportation Research Board, 2610(1), 67–75.
Min, H. (1989), The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transportation Research Part A: General, 23(5)377-386.
Muren, Li, H., Mukhopadhyay, S.K., Wu, J., Zhou, L. and Du, Z. (2019), Balanced maximal covering location problem and its application in bike-sharing, International Journal of Production Economics, doi: https://doi.org/10.1016/j.ijpe.2019.09.034
Najmi, A., Rey, D. and Rashidi, T. (2017), Novel dynamic formulations for real-time ride-sharing systems, Transportation Research Part E: Logistics and Transportation Review, 128, 175-190.
PiggyBee, Retrieved November 13, 2019, from https://www.piggybee.com/en/
Punel, A., Ermagun, A. and Stathopoulos, A. (2018), Studying determinants of crowd- shipping use, Travel Behaviour and Society, 12, 30–40..
PwC (2018), Share Economy 2017 – The New Business Model, from https://www.pwc.de/de/digitale-transformation/share-economy-report-2017.pdf
Rieck, J., Ehrenberg, C. and Zimmermann J. (2014), Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery, European Journal of Operational Research, 236(3), 863-878
Roland Berger (2016), China's Car-Sharing Mobility Market 2018, from https://www.rolandberger.com/nl/Publications/China's-Car-Sharing-Mobility-Market-2018.html
Savelsbergh, M. W. P. (1995), The General Pickup and Delivery Problem, Transportation Science, 29(1), 17-29.
Uber Eats, Retrieve March 23, 2020, from https://www.ubereats.com/blog/zh-TW/taipei/delivery-partner-basic-fare-tn/
Wade, A.C. and Salhi, S. (2002), An investigation into a new class of vehicle routing problem with backhauls, Omega, 30(6), 479-487.
Wu, W., Tian, Y. and Jin, T. (2016), A label based ant colony algorithm for heterogeneous vehicle routing with mixed backhaul, Applied Soft Computing, 47, 224-234.
Yang, J., Jaillet, P., and Mahmassani, H. (2004), Real-Time Multivehicle Truckload Pickup and Delivery Problems, Transportation Science, 38(2), 135-148.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2024-06-16起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2024-06-16起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw