考量利潤與隨機顧客之車輛途程問題

A Vehicle Routing Problem considering Profits and Stochastic Customers

趙浩雅(Hao-Ya Chao)

指導教授 ： 朱致遠

國立臺灣大學/工學院/土木工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202002814

摘要

隨著網路零售營業額成長與購物環境的變化大量的送貨到府的需求使得物流業面臨極大的挑戰。其中，「最後一哩運送」攸關消費者之顧客滿意度的重要關鍵之一。然而，在實務上時常出現顧客因為各樣因素而延遲取貨、最後導致送貨失敗，甚至取消訂單，使廠商增加營運成本。因此，如何在有限的時間內針對隨機的顧客狀態合理地調度送貨員，在滿足客戶需求的情況下使得總運營最小而得到最佳利潤為物流業者重要的課題。
本研究的目標為開發出一個可考量利潤與隨機顧客之車輛模型（Vehicle routing problem with profits and stochastic customers），並針對其特性與策略進行架構。在研究方法中，本研究在模型建立中進一步提出軟時間窗與容量限制考量，並建立出一個二階段整數規劃模式進行尋求解答方案。在觀察該問題特性後，本研究另外提出兩套演算法來加速求解過程。第一套演算法在第一階段運用插入式啟發演算法去進行第一階段的路徑建立並在第二階段用迭代區域搜索法進行各情境之優化；第二套演算法中，第一階段則改以遺傳演算法進行隨機初始選擇，並同於第二階段用迭代區域搜索法優化路徑。

關鍵字

物流問題 ； 考量利潤之車輛途程問題 ； 軟時窗 ； 混合整數規劃模型 ； 啟發式演算法

並列摘要

With the growth of internet retails and the changing of shopping environment in popularity, the large amount of home delivery brings with a new batch of ecommerce logistics challenges. "Last mile delivery" is one of the important factor to customer satisfaction and often leads to delivery failure due to the absence for customer, causing the increase of operating costs. Therefore, logistics enterprises are dedicating to the minimizing the total operation cost and optimum the profit, considering the best way to dispatch the deliveryman reasonably within a limited time.
The aim of this research was to develop an optimization model for Vehicle Routing Problem with Profits and Stochastic Customers (VRPPSC). In the thesis, soft time windows and capacity constraints are considered. A two-stage stochastic mixed-integer programming model was first proposed for the problem. Since the problem is NP-hard, two problem procedures are constructed for solving the generated problem. The first procedures is based on a combination of inserted heuristic and iterated local search algorithms, while the second using a genetic algorithm to do the randomizing of the first stage selection.

並列關鍵字

Logistic problem ； Vehicle Routing Problem with Profits ； Soft Time windows ； Mixed-integer Programming Model ； Heuristic Algorithm

參考文獻

[1] Aghezzaf, B., Fahim, H. E. (2014, June). The multi-constraint team orienteering problem with time windows in the context of distribution problems: A variable neighborhood search algorithm. In 2014 International Conference on Logistics Operations Management (pp. 155-160). IEEE.

[2] Archetti, C., Bertazzi, L., Laganà, D., Vocaturo, F. (2017). The undirected capacitated general routing problem with profits. European Journal of Operational Research, 257(3), 822-833.

[3] Archetti, C., Feillet, D., Hertz, A., Speranza, M. G. (2009). The capacitated team orienteering and profitable tour problems. Journal of the Operational Research Society, 60(6), 831-842.

[4] Archetti, C., Bianchessi, N., Speranza, M. G. (2013a). Optimal solutions for routing problems with profits. Discrete Applied Mathematics, 161(4-5), 547-557.

[5] Archetti, C., Bianchessi, N., Speranza, M. G. (2013b). The capacitated team orienteering problem with incomplete service. Optimization letters, 7(7), 1405-1417.