臺灣博碩士論文加值系統

近年來，由於COVID-19疫情的蔓延，電子商務蓬勃發展，突顯了城市物流的重要性。物流配送速度和整體物流配送品質已成為評估物流績效的關鍵指標。考慮到實時交通壅塞狀況和產品回收的複雜性，逆向物流中的車輛途程問題(Vehicle Routing Problem, VRP)必須規劃運輸路線、降低整體成本、減少運輸過程中的碳排放，同時滿足時窗限制和同時收送貨(Simultaneous Pickups and Deliveries)的需求。本研究依據問題特性與限制建構數學規劃模型，目標為最小化總配送車輛數、總配送距離以及每趟次司機的薪資成本。利用作業研究最佳化軟體(AIMMS)針對小規模測試案例進行求解，以驗證模型的正確性。由於模型的複雜性以及實際案例中據點數量眾多，本研究發展適應性基因演算法(Adaptive Genetic Algorithm, AGA)以求解物流公司65個門市據點的實際案例，並根據其案例進行敏感度分析。敏感度分析比較不同變因對成本及車輛選擇結果的影響，發現需求量、固定成本以及收貨量比例顯著影響各項成本及車輛選擇結果。根據敏感度分析，物流公司可以依據這幾個變因進行調整，並且提供給決策者作為參考依據。

In recent years, the COVID-19 pandemic has significantly boosted e-commerce, highlighting the importance of urban logistics. The speed and quality of logistics delivery have become key performance indicators. Considering real-time traffic congestion and the complexity of product returns, the Vehicle Routing Problem (VRP) in reverse logistics must optimize routes, reduce overall costs, and minimize carbon emissions while meeting time window constraints and the need for Simultaneous Pickups and Deliveries. This study develops a mathematical model based on the problem characteristics and constraints, aiming to minimize the total number of delivery vehicles, total delivery distance, and driver salary costs per trip. The model is validated using the operations research optimization software AIMMS on small-scale test cases. Due to the model's complexity and the large number of nodes in real cases, an Adaptive Genetic Algorithm (AGA) was developed to solve a real case involving 65 logistics company outlets. Sensitivity analysis was conducted to compare the effects of different variables on costs and vehicle selection. The analysis revealed that demand, fixed costs, and the ratio of pickup to delivery volume significantly impact costs and vehicle selection. Based on this sensitivity analysis, logistics companies can adjust these variables and provide decision-makers with valuable insights.

摘要...i
Abstract...ii
誌謝...iii
目錄...iv
表目錄...vii
圖目錄...ix
第一章 緒論...1
1.1 研究背景與動機...1
1.2 研究目的...3
1.3 研究架構...3
1.4 研究範圍...4
1.5 研究流程...5
第二章 文獻回顧...7
2.1 車輛途程問題(VRP)...7
2.1.1 車輛途程問題定義...7
2.1.2 VRP的延伸問題...8
2.2 收送貨問題...10
2.3 同時收送貨之車輛途程問題(VRPSPD)之文獻回顧...13
2.4 適應性基因演算法(Adaptive Genetic Algorithm, AGA)...23
2.4.1 基本概念...23
2.4.2 演算法流程...24
第三章 數學模型...31
3.1 定義問題...31
3.2 建構數學規劃模型...32
3.3 測試問題...36
第四章 研究方法...41
4.1 適應性基因演算法...41
4.1.1 初始化參數設定...43
4.1.2 編碼...43
4.1.3 建構初始群體...43
4.1.4 計算與評估適應值...44
4.1.5 終止條件...45
4.1.6 染色體的選擇...45
4.1.7 交配...45
4.1.8 突變...46
4.1.9 產生新群體...47
4.2 測試環境...47
4.3 適應性基因演算法參數設定...48
4.3.1 迭代次數...48
4.3.2 參數組合...48
第五章 實務案例...52
5.1 案例說明...52
5.2 適應性基因演算法規劃結果...59
5.2.1 迭代次數設定...59
5.2.2 案例配送規劃結果...60
5.3 參數敏感度分析...62
5.3.1 據點需求量之影響...62
5.3.2 車輛固定成本之影響...71
5.3.3 收貨量和送貨量的差異比例分析...75
第六章 結論及建議...81
6.1 結論...81
6.2 建議...82
參考文獻...83
附錄A...89
Extended Abstract...105

1.邱仕銘 (2006)，同時收送貨車輛配送問題之研究，長榮大學經營管理研究所，碩士論文。
2.洪維德 (2018)，考量生鮮配送之同時收送貨存貨途程問題，國立雲林科技大學工業工程與管理系，碩士論文。
3.莊英群 (2003)，應用禁忌搜尋法於混合送收貨之車輛途程問題，逢甲大學工業工程學所，碩士論文。
4.許文軒 (2015)，考量碳足跡之同時收送貨存貨途程配銷之決策支援系統，龍華科技大學資訊管理系碩士班，碩士論文。
5.項于軒 (2023)，考量時間窗及同時收送貨之異質性車輛途程問題，國立陽明交通大學運輸與物流管理學系，碩士論文。
6.趙致傑、韓復華 (2010)，以適應性門檻接受法求解同時收送貨之車輛路線問題之研究，國立陽明交通大學運輸與物流管理學系，碩士論文。
7.鄭雁嬬 (2009)，混合式演算法應用於同時收送貨之車輛途程問題，元智大學工業工程與管理學系，碩士論文。
8.Agrawal, Singh & Murtaza. (2015). A literature review and perspectives in reverse logistics Resources, Conservation and Recycling, Vol.97, pp.76-92.
9.Avci & Topaloglu. (2015). An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries Computers & Industrial Engineering, Vol.83, pp.15-29.
10.Avci & Topaloglu. (2016). A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery Expert Systems with Applications, Vol.53, pp.160-171.
11.Basak. (2020). A Rank based Adaptive Mutation in Genetic Algorithm ArXiv, Vol.abs/2104.08842.
12.Battarra, Cordeau & Iori. (2014). Pickup-and-Delivery Problems for Goods Transportation Vehicle routing: problems, methods, and applications, pp.161-191.
13.Berbeglia, Cordeau, Gribkovskaia & Laporte. (2007). Static pickup and delivery problems: a classification scheme and survey TOP, Vol.15, No.1, pp.1-31.
14.Coca-Cola. (2017). 2017 Sustainability Report. https://www.bing.com/ck/a?!&&p=c86ead5d8b7703d1JmltdHM9MTcwMjY4NDgwMCZpZ3VpZD0xODYxYjAyNy0wNmQxLTYzMTgtMTYwOS1iZjQ5MDc5NzYyYzUmaW5zaWQ9NTE3OQ&ptn=3&ver=2&hsh=3&fclid=1861b027-06d1-6318-1609-bf49079762c5&psq=Coca-Cola.+2017.+%3chttp%3a%2f%2fwww.coca-cola.com%2fglobal%2fglp.html%3e+(accessed+03.01.2017).&u=a1aHR0cHM6Ly93d3cuY29jYS1jb2xhY29tcGFueS5jb20vY29udGVudC9kYW0vY29tcGFueS91cy9lbi9yZXBvcnRzL3BkZi8yMDE3LXN1c3RhaW5hYmlsaXR5LXJlcG9ydC10aGUtY29jYS1jb2xhLWNvbXBhbnkucGRm&ntb=1
15.Damia, Esnaashari & Parvizimosaed. (2021, 19-20 May 2021). Adaptive Genetic Algorithm Based on Mutation and Crossover and Selection Probabilities. 2021 7th International Conference on Web Research (ICWR).
16.Dantzig & Ramser. (1959). The Truck Dispatching Problem Management Science, Vol.6, pp.80-91.
17.dell’Amico, Righini & Salani. (2006). A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection Transp. Sci., Vol.40, pp.235-247.
18.Derigs, Kabath & Zils. (1999). Adaptive Genetic Algorithms: A Methodology for Dynamic Autoconfiguration of Genetic Search Algorithms. In Voß, Martello, Osman, & Roucairol (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (pp. 231-248). Springer US.
19.Dethloff. (2001). Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up OR Spektrum, Vol.23, No.1, pp.79-96.
20.Dethloff. (2002). Relation between Vehicle Routing Problems: An Insertion Heuristic for the Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Applied to the Vehicle Routing Problem with Backhauls The Journal of the Operational Research Society, Vol.53, No.1, pp.115-118.
21.Dumitrescu, Lazzerini, Jain & Dumitrescu. (2000). Evolutionary computation. CRC Press.
22.Goksal, Karaoglan & Altiparmak. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery Comput. Ind. Eng., Vol.65, pp.39-53.
23.Goldberg. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc.
24.Gonzalez-Feliu (2008)，Models and Methods for the City Logistics: The Two-Echelon Capacitated Vehicle Routing Problem
25.Hassanat, Almohammadi, Alkafaween, Abunawas, Hammouri & Prasath. (2019). Choosing Mutation and Crossover Ratios for Genetic Algorithms—A Review with a New Dynamic Approach Information, Vol.10, No.12, pp.390.
26.Holland. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.
27.Holland. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press.
28.Intelligence. (2023). Freight and Logistics Market SIZE & SHARE ANALYSIS - GROWTH TRENDS & FORECASTS UP TO 2030. https://www.mordorintelligence.com/industry-reports/freight-logistics-market-study
29.Jafar-Zanjani, Inampudi & Mosallaei. (2018). Adaptive Genetic Algorithm for Optical Metasurfaces Design Scientific Reports, Vol.8, No.1, pp.11040.
30.Jebari. (2013). Selection Methods for Genetic Algorithms International Journal of Emerging Sciences, Vol.3, pp.333-344.
31.Kalayci & Kaya. (2016). An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery Expert Systems with Applications, Vol.66, pp.163-175.
32.Katoch, Chauhan & Kumar. (2021). A review on genetic algorithm: past, present, and future Multimedia Tools and Applications, Vol.80, No.5, pp.8091-8126.
33.Koç, Laporte & Tükenmez. (2020). A review of vehicle routing with simultaneous pickup and delivery Computers & Operations Research, Vol.122, pp.104987.
34.Lee & Takagi. (1995). A framework for studying the effects of dynamic crossover, mutation, and population sizing in genetic algorithms. Advances in Fuzzy Logic, Neural Networks and Genetic Algorithms, Berlin, Heidelberg Springer Berlin Heidelberg.
35.Leelertkij, Parthanadee & Buddhakulsomsiri. (2021). Vehicle Routing Problem with Transshipment: Mathematical Model and Algorithm Journal of Advanced Transportation, Vol.2021, pp.1-15.
36.Liang, Li, Bi, Ding & Zhao. (2020). An Improved Adaptive Parallel Genetic Algorithm for the Airport Gate Assignment Problem Journal of Advanced Transportation, Vol.2020, pp.1-17.
37.Liu, Wang, Gui, et al. (2023). A hybrid heuristic algorithm for urban distribution with simultaneous pickup-delivery and time window Journal of Heuristics, Vol.29, No.2-3, pp.269-311.
38.Min. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points Transportation Research Part A: General, Vol.23, No.5, pp.377-386.
39.Olgun, Koç & Altıparmak. (2021). A hyper heuristic for the green vehicle routing problem with simultaneous pickup and delivery Computers & Industrial Engineering, Vol.153, pp.107010.
40.Pilcher. (2023). A self-adaptive genetic algorithm for the flying sidekick travelling salesman problem ArXiv, Vol.abs/2310.14713.
41.Raj, Punia & Kumar. (2023). A comparative analysis of genetic algorithms on a case study of asymmetric traveling salesman problem International Journal of System Assurance Engineering and Management, Vol.14, No.6, pp.2684-2694.
42.Ropke & Pisinger. (2006). A unified heuristic for a large class of Vehicle Routing Problems with Backhauls European Journal of Operational Research, Vol.171, No.3, pp.750-775.
43.Salhi & Nagy. (1999). A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling Journal of the Operational Research Society, Vol.50, No.10, pp.1034-1042.
44.Subramanian, Drummond, Bentes, Ochi & Farias. (2010). A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery Computers & Operations Research, Vol.37, No.11, pp.1899-1911.
45.Subramanian, Uchoa, Pessoa & Ochi. (2013). Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery Optimization Letters, Vol.7, No.7, pp.1569-1581.
46.Toth & Vigo. (2002). VRP with Backhauls. In The Vehicle Routing Problem, pp. 195-224.
47.Yan, Li, Liu & Qi. (2020). Improved adaptive genetic algorithm for the vehicle Insurance Fraud Identification Model based on a BP Neural Network Theoretical Computer Science, Vol.817, pp.12-23.
48.Yun & Gen. (2003). Performance Analysis of Adaptive Genetic Algorithms with Fuzzy Logic and Heuristics Fuzzy Optimization and Decision Making, Vol.2, No.2, pp.161-175.
49.Zachariadis & Kiranoudis. (2011). A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries Expert Systems with Applications, Vol.38, No.3, pp.2717-2726.
50.Zachariadis, Tarantilis & Kiranoudis. (2009). A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service Expert Systems with Applications, Vol.36, No.2, Part 1, pp.1070-1081.