車輛路徑問題在團膳出貨與回收上之應用

An Application of Vehicle Routing Problem with Deliveries before Pickups in Catering Business

蘇菈雅(Soraya Ayu Chumaira)

指導教授 ： 洪暉智

國立交通大學/管理學院/工業工程與管理系所/碩士(2020年)

摘要

車隊路徑管理是外送餐飲業務的重要議題之一。 通過找到車輛最佳路線，可以通過最小化距離來獲得最小化運輸成本。這類問題被稱為車輛路徑問題（Vehicle Routing Problem, VRP）。 本文提出了車輛路徑問題的變體。即有一般貨品派送的去程，及帶餐具回收的回程的車輛路徑問題（VRPB）。VRPB問題的這種變體，改編自滿足餐飲業務行為的需求。一般外送餐飲業務，基於衛生安全的考量，多將遞送任務優先於回收任務。本研究開發了具有拆分（Split）、插入（Insert）、路徑縮減（Saving）和路徑合併（combination）的啟發式演算方法來解決該問題。該算法通過21個實例進行了測試。對於所有情況，最著名的解決方案與結果之間的平均差距為17％。此外，我們也探索了另一個VRP問題的變種，具有兩種不同優先順序的產品交付問題（VRP-2TD）。並使用VRP-2TD來查找VRPB問題的最佳值下限。

關鍵字

車輛路徑問題 ； 回程 ； 運輸計劃 ； 啟發式演算方法

並列摘要

Managing routing is one of the essential components in the catering business. Minimize the cost of transportation will obtain from minimizing distance by finding the optimal route. This problem called the vehicle routing problem. This paper presents the vehicle routing problem variants; that is VRP with backhauls, single depot, homogenous vehicle, a single trip for each vehicle (VRPB). This variant of VRP adapted from catering business behavior that prioritized deliveries than pickups. Heuristic with split, insert, saving, and combined have been developed to solve the problem. The algorithm tested by 21 instances. For all instances, the average gap between the best-known solution and the result is 17%. VRP with two types delivery product problem are used to find the lower bound the catering business problem.

並列關鍵字

vehicle routing problem ； backhauls ； transport planning ； catering

參考文獻

Azis, Z., & Mawengkang, H. (2017). Time Dependent Heterogeneous Vehicle Routing Problem for Catering Service Delivery Problem. Journal of Physics: Conference Series, 890, 012103. https://doi.org/10.1088/1742-6596/890/1/012103

Casco, D. O., Golden, B. L., & Wasil, E. A. (1988). Vehicle routing with backhauls: Models, algorithms and case studies. Elsevier.

Chapter 4 Catering and Food Service Management. (2018). National Council of Educational Research and Training.

Clarke, G., & Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568–581.

Crainic, T. G. (Ed.). (2013). Fleet management and logistics (softcover reprint of the orig. 1st ed. 1998). Springer.