臺灣博碩士論文加值系統

隨著網路零售營業額成長與購物環境的變化大量的送貨到府的需求使得物流業面臨極大的挑戰。其中，「最後一哩運送」攸關消費者之顧客滿意度的重要關鍵之一。然而，在實務上時常出現顧客因為各樣因素而延遲取貨、最後導致送貨失敗，甚至取消訂單，使廠商增加營運成本。因此，如何在有限的時間內針對隨機的顧客狀態合理地調度送貨員，在滿足客戶需求的情況下使得總運營最小而得到最佳利潤為物流業者重要的課題。
本研究的目標為開發出一個可考量利潤與隨機顧客之車輛模型（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.

誌謝 i
摘要 ii
ABSTRACT iii
CONTENTS iv
LIST OF FIGURES vi
LIST OF TABLE viii
Chapter 1 Introduction 1
1.1 Background Information and Motivation 1
1.2 Research Objective 3
1.3 Research Structure 3
Chapter 2 Literature Review 4
2.1 Vehicle Routing Problem with Profits 4
2.2 Variants of Vehicle Routing Problem with Profits 6
2.3 Vehicle Routing Problem with Stochastic Customers 11
2.4 Summary 12
Chapter 3 Research Methodology 14
3.1 Overview 14
3.2 Basic Assumptions 15
3.3 Mixed-integer Programming model 15
3.3.1 Network Formulation 15
3.3.2 Model Formulation 19
3.4 Heuristic Algorithm 25
3.4.1 First-stage method 28
3.4.1.1 Insertion method 28
3.4.1.2 Genetic algorithm 29
3.4.2 Second-stage method 30
Chapter 4 Computational Result 38
4.1 Test instances 38
4.2 Results 40
Chapter 5 Conclusions and Future research 51
REFERENCE 53

[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.
[6]Archetti, C., Bianchessi, N., Speranza, M. G., & Hertz, A. (2014a). The split delivery capacitated team orienteering problem. Networks, 63(1), 16-33.
[7]Archetti, C., Bianchessi, N., Speranza, M. G., & Hertz, A. (2014b). Incomplete service and split deliveries in a routing problem with profits. Networks, 63(2), 135-145.
[8]Blanchard, D. (2007). Supply chains also work in reverse. Industry Week, 1(1), 48-49.
[9]Boussier, S., Feillet, D., & Gendreau, M. (2007). An exact algorithm for team orienteering problems. 4or, 5(3), 211-230.
[10]Butt, S. E., & Cavalier, T. M. (1994). A heuristic for the multiple tour maximum collection problem. Computers & Operations Research, 21(1), 101-111.
[11]Campbell, A. M., Gendreau, M., & Thomas, B. W. (2011). The orienteering problem with stochastic travel and service times. Annals of Operations Research, 186(1), 61-81.
[12]Morganti, E., Seidel, S., Blanquart, C., Dablanc, L., & Lenz, B. (2014). The impact of e-commerce on final deliveries: alternative parcel delivery services in France and Germany. Transportation Research Procedia, 4(0), 178-190.
[13]eMarketer. (2020). E-commerce share of total global retail sales from 2015 to 2023. Retrieved from https://www.statista.com/statistics/534123/e-commerce-share-of-retail-sales-worldwide/
[14]eMarketer. (2020). Retail e-commerce sales worldwide from 2014 to 2023(in billion U.S. dollars). Retrieved from https://www.statista.com/statistics/379046/worldwide-retail-e-commerce-sales/
[15]eMarketer. (2020). Annual retail e-commerce sales growth worldwide from 2017 to 2023. Retrieved from https://www.statista.com/statistics/288487/forecast-of-global-b2c-e-commerce-growth/
[16]Alex Rolfe (2017, August 2). Worldwide retail e-commerce sales reach $1.9 trillion in 2016. Payments Cards & Mobile. Retrieved from: https://www.paymentscardsandmobile.com/retail-e-commerce-sales-reach-1-9-trillion/
[17]Evers, L., Glorie, K., Van der Ster, S., Barros, A.I. and Monsuur, H. (2014). A two-stage approach to the orienteering problem with stochastic weights. Computers & Operations Research, 43, 248-260.
[18]Gambardella, L. M., Montemanni, R., & Weyland, D. (2012). Coupling ant colony systems with strong local searches. European Journal of Operational Research, 220(3), 831-843.
[19]Garcia, A., Vansteenwegen, P., Souffriau, W., Arbelaitz, O., & Linaza, M. (2009). Solving multi constrained team orienteering problems to generate tourist routes.
[20]Gevaers, R., Van de Voorde, E., & Vanelslander, T. (2011). Characteristics and typology of last-mile logistics from an innovation perspective in an urban context. City Distribution and Urban Freight Transport: Multiple Perspectives, Edward Elgar Publishing, 56-71.
[21]Golden, B. L., Levy, L., & Vohra, R. (1987). The orienteering problem. Naval Research Logistics (NRL), 34(3), 307-318.
[22]Gunawan, A., Lau, H. C., & Vansteenwegen, P. (2016). Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2), 315-332.
[23]Hu, Q., & Lim, A. (2014). An iterative three-component heuristic for the team orienteering problem with time windows. European Journal of Operational Research, 232(2), 276-286.
[24]Ilhan, T., Iravani, S. M., & Daskin, M. S. (2008). The orienteering problem with stochastic profits. Iie Transactions, 40(4), 406-421.
[25]Jepsen, M. K. (2011). Branch-and-cut and branch-and-cut-and-price algorithms for solving vehicle routing problems.
[26]Labadie, N., Mansini, R., Melechovský, J., & Calvo, R. W. (2012). The team orienteering problem with time windows: An lp-based granular variable neighborhood search. European Journal of Operational Research, 220(1), 15-27.
[27]Lin, S. W., & Vincent, F. Y. (2012). A simulated annealing heuristic for the team orienteering problem with time windows. European Journal of Operational Research, 217(1), 94-107.
[28]Luo, Z., Cheang, B., Lim, A., & Zhu, W. (2013). An adaptive ejection pool with toggle-rule diversification approach for the capacitated team orienteering problem. European Journal of Operational Research, 229(3), 673-682.
[29]LM, M. R. G. (2009). Ant colony system for team orienteering problem with time windows. Foundations of Computing and Decision Sciences, 344, 287-306.
[30]Papapanagiotou, V., Montemanni, R., & Gambardella, L. (2014). Objective function evaluation methods for the orienteering problem with stochastic travel and service times. Journal of Applied Operations Research, 6(1), 16-29.
[31]Park, J., Lee, J., Ahn, S., Bae, J., & Tae, H. (2017). Exact algorithm for the capacitated team orienteering problem with time windows. Mathematical Problems in Engineering, 2017.
[32]Ritzinger, U., Puchinger, J., & Hartl, R. F. (2016). A survey on dynamic and stochastic vehicle routing problems. International Journal of Production Research, 54(1), 215-231.
[33]Sun, P., Veelenturf, L. P., Dabia, S., & Van Woensel, T. (2018). The time-dependent capacitated profitable tour problem with time windows and precedence constraints. European Journal of Operational Research, 264(3), 1058-1073.
[34]Tarantilis, C. D., Stavropoulou, F., & Repoussis, P. P. (2013). The capacitated team orienteering problem: a bi-level filter-and-fan method. European Journal of Operational Research, 224(1), 65-78.
[35]Tarantilis, C. D., Stavropoulou, F., & Repoussis, P. P. (2013). The capacitated team orienteering problem: a bi-level filter-and-fan method. European Journal of Operational Research, 224(1), 65-78.
[36]Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.
[37]Tsiligirides, T. (1984). Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9), 797-809.
[38]Vansteenwegen, P., Souffriau, W., Berghe, G. V., & Van Oudheusden, D. (2009). Iterated local search for the team orienteering problem with time windows. Computers & Operations Research, 36(12), 3281-3290.
[39]Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1-10.
[40]Vansteenwegen, P., & Gunawan, A. (2019). Orienteering problems: Models and algorithms for vehicle routing problems with profits. Springer Nature.
[41]Weber, C. L., Koomey, J. G., & Matthews, H. S. (2010). The energy and climate change implications of different music delivery methods. Journal of Industrial Ecology, 14(5), 754-769.
[42]Wang, X., Golden, B., & Gulczynski, D. (2014). A worst-case analysis for the split delivery capacitated team orienteering problem with minimum delivery amounts. Optimization letters, 8(8), 2349-2356.
[43]Li, Z., & Hu, X. (2011, August). The team orienteering problem with capacity constraint and time window. In The 10th International Symposium on Operations Research and its Applications (ISORA 2011) (pp. 157-163).
[44]瘋時尚（民108年8月14日）。德國網購退貨率居歐洲之首，Zalando、亞馬遜等電商紛紛採取應對措施。取自： https://ifashiontrend.com/zalando-amazon-return-policy/