臺灣博碩士論文加值系統

諸如蘋果公司等企業，已將碳中和作為其目標政策，微軟甚至是目標更進一步之負碳排。此外，在2021年聯合國氣候變化大會（COP26）之後，日本、印度等國亦承諾實現淨零碳排。作為整條供應鏈中效率最低、成本最高之環節，最後一哩路配送勢必需要變革。
而近年來，在商業物流領域，無人航空載具，也被稱作無人機，亦經常被當作物流運載工具選項之一。無人機可在卡車路線上之節點發射及返回，與卡車協同服務，同時向客戶交付貨物，從而提高服務質量，降低物流成本。
本研究旨在透過建立搭載無人機之環保車輛路徑問題（GVRPD）模型來改善相關問題。此模型之目標為最小化交貨總成本，並將二氧化碳排放量換算為碳成本，作為其中一項成本來源。此外，模型也將透過基因演算法規劃卡車行進路線，進而指派無人機進行協同交付服務。
本研究隨機生成資料集以進行實驗，並分析在無無人機時，及導入無人機後兩者間之成本變化，並進而觀察二氧化碳排放數值變化。結果顯示GVRPD可節省成本支出，亦可同時兼顧二氧化碳排放，使其下降。此外，亦針對幾個特定參數進行進一步分析。

Many companies, such as Apple, have adopted carbon neutrality as a target policy, and even Microsoft’s goal is to further negative carbon emissions. Also, after the 2021 United Nations Climate Change Conference (COP26), Japan, India, and other countries pledged to commit to net-zero carbon emissions. As the least efficient and costliest part of the entire supply chain, it is need to reform the last mile delivery.
In recent years, in the field of commercial logistics, unmanned aerial vehicles (UAV), also known as drones, are often considered as a logistics vehicle option. Drones can be launched and returned at nodes on the truck's route, coordinate services with the truck, and deliver cargo to customers simultaneously, thereby improving service quality and reducing logistic costs.
This study intends to improve related issues by formulating a model for the Green Vehicle Routing Problem with Drones (GVRPD). The objective of the model is to minimize the total cost of delivery and convert the CO2 emission into carbon costs as one of the cost sources. In addition, the model will also arrange the route of trucks through the Genetic Algorithm, and then assign drones for collaborative delivery services.
This study randomly generates a data set for experimentation and analyzes the cost changes at the no-drone state and after introducing drones, then further observes the variation in the value of the CO2 emission. The results show that GVRPD not only can lessen the total cost but meanwhile also reduce the CO2 emission. In addition, further analysis is carried out for several specific parameters.

摘要 I
ABSTRACT II
致謝 III
CONTENTS IV
LIST OF FIGURES VI
LIST OF TABLES VII
1. INTRODUCTION 1
1.1 Background and Motivation 1
1.2 Research Objective 2
1.3 Research Constraints 2
1.4 Thesis Organization 2
2. LITERATURE REVIEW 4
2.1 Vehicle Routing Problem 4
2.2 Vehicle Routing Problem with Drone 6
2.3 Green Vehicle Routing Problem 7
2.3.1 Pollution Routing Problem 7
2.3.2 Green-VRP 8
2.3.3 VRP in Reverse Logistics 8
2.4 Metaheuristic 9
2.4.1 Genetic Algorithm 9
3. METHODOLOGY 11
3.1 Mathematical formulation for the GVRPD 12
3.2 Notation 12
3.3 Mathematical formulation 14
3.4 GA for GVRPD 16
3.5 Performance evaluation 21
4. EXPERIMENTAL RESULTS 23
4.1 Test instances 23
4.2 Experiment and results 25
4.3 Significance 27
4.4 Independent Variables 28
4.4.1 Range of Area 28
4.4.2 Number of customers 29
4.4.3 Service ratio of drones 31
4.4.4 Drone velocity 32
4.5 Customer Density 33
4.6 Cost Breakdown 33
4.7 Summary 35
5. CONCLUSTIONS AND FUTURE RESEARCH RECOMMENDATIONS 36
5.1 Conclusions 36
5.2 Contributions 37
5.3 Future Research Recommendations 37
REFERENCES 39
APPENDIX 44

Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800. doi: 10.1016/S0305-0548(02)00051-5
Bateman, T., & Associated Press (2021, June 4). Drone delivery of vaccine doses speeds up COVID-19 vaccinations in remote areas of Ghana [Online news]. Retrieved from https://www.euronews.com/next/2021/06/04/drone-delivery-of-vaccine-doses-speeds-up-covid-19-vaccinations-in-remote-areas-of-ghana
Bauer, J., Bektaş, T., & Crainic, T. G. (2010). Minimizing greenhouse gas emissions in intermodal freight transport: an application to rail service design. Journal of the Operational Research Society, 61, 530–542. doi: 10.1057/jors.2009.102
Bektaş, T., & Laporte, G. (2011). The Pollution-Routing Problem. Transportation Research Part B: Methodological, 45(8), 1232–1250. doi: 10.1016/j.trb.2011.02.004
Belfiore, P., Tsugunobu, H., & Yoshizaki, Y. (2008). Scatter Search for Vehicle Routing Problem with Time Windows and Split Deliveries. In Caric, T. & Gold, H (Eds.), Vehicle Routing Problem. doi: 10.5772/5613
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem, Management Science, 6(1), 80-91. doi: 10.2307/2627477
Darwin, C. R. (1988). The Origin of Species. New York, NY: HarperCollins.
Dawkins, R. (1983). Universal Darwinism. In: D. S. Bendall (Eds.), Evolution From Molecules to Men. Cambridge, UK: Cambridge University Press.
Deutsche Post DHL Group. (2019). 2019 Sustainability Report. Retrieved from https://www.dpdhl.com/content/dam/dpdhl/en/media-center/responsibility/dpdhl-sustainability-report-2019.pdf
Directorate General of Highways, R.O.C. (2018). 路運綜字第1070072148號. Retrieved from http://www.route-permitted-truck.com.tw/upload/84b1532eb1b35e861eff0d769155b5ff.pdf
Environmental Protection Administration, R.O.C. (2021). 碳足跡排放係數. Retrieved from https://data.epa.gov.tw/en/dataset/cfp_p_02/resource/b3c28e40-3d97-45be-a02b-fc74dee5f47d
Erdoğan S., & Miller-Hooks, E. (2012). A Green Vehicle Routing Problem. Transportation Research Part E: Logistics and Transportation Review, 48(1) 100–114. doi: 10.1016/j.tre.2011.08.001
Figliozzi, M. A. (2017). Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO2e emissions. Transportation Research Part D: Transport and Environment, 57, 251-261. doi: 10.1016/j.trd.2017.09.011
Goldberg, D. E. (1984). Computer-aided gas pipeline operation using genetic algorithms and rule learning (Doctoral dissertation, University of Michigan).
Golden, B. L., & Assad, A. A. (1988). Vehicle Routing: Methods and Studies. Amsterdam, Netherlands: North-Holland.
Herrera, F., Lozano, M., & Verdegay, J.L. (1998). Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis. Artificial Intelligence Review, 12 (4), 265-319. doi: 10.1023/A:1006504901164
Holland, J. H. (1975). Adaptation in Natural and Artificial System, Ann Arbor, MI: The University of Michigan Press.
International Civil Aviation Organization. (2005). Global Air Traffic Management Operational Concept (Doc 9854). Retrieved from https://www.icao.int/Meetings/anconf12/Document%20Archive/9854_cons_en%5B1%5D.pdf
Kim, E. (2016, Jun 16). The most staggering part about Amazon's upcoming drone delivery service [Online news]. Retrieved from https://www.businessinsider.com/cost-savings-from-amazon-drone-deliveries-2016-6
Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M., & Brunese, P. A. (2019). Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering, 129, 14-30. doi: 10.1016/j.cie.2019.01.020
Kuo, R.J., Lu, S. H., Lai, P. Y., & Mara, S. T. W. (2021). Vehicle routing problem with drones considering time windows. Expert Systems with Applications, 191, 116264. doi: 10.1016/j.eswa.2021.116264
Laporte, G., Mercure, H., & Nobert, Y. (1986). An exact algorithm for the asymmetrical capacitated vehicle routing problem, Network, 16, 33-46.
Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. (2014). Survey of green vehicle routing problem: Past and future. Expert Systems with Applications, 41(4), 1118-1138. doi: 10.1016/j.eswa.2013.07.107
Miranda, D. M., & Conceição, S. V. (2016). The vehicle routing problem with hard time windows and stochastic travel and service time, Expert System with Applications, 64, 104-116. doi: 10.1016/j.eswa.2016.07.022
Mitchell, M. (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press.
Murray, C.C., & Chu, A.G. (2015). The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109. doi: 10.1016/j.trc.2015.03.005
Organisation for Economic Co-operation and Development. (2021). Effective Carbon Rates 2021 - Pricing Carbon Emissions through Taxes and Emissions Trading. Retrieved from https://www.oecd.org/tax/tax-policy/effective-carbon-rates-2021-0e8e24f5-en.htm
Oruc, B. E., & Kara, B. Y. (2018). Post-disaster assessment routing problem. Transportation research part B: methodological, 116, 76-102. doi: 10.1016 / j.trb.2018.08.002
Palmer, A. (2007). The development of an integrated routing and carbon dioxide emissions model for goods vehicles (Doctoral dissertation, School of Management, Cranfield University). Retrieved form https://dspace.lib.cranfield.ac.uk/bitstream/handle/1826/2547/Palmer%2c%20A%20PhD.pdf?sequence=1&isAllowed=y
Peng, K., Du, J., Lu, F., Sun, Q., Dong, Y., Zhou, P., & Hu, M. (2019). A Hybrid Genetic Algorithm on Routing and Scheduling for Vehicle-Assisted Multi-Drone Parcel Delivery. IEEE Access, 7, 49191-49200. doi: 10.1109/ACCESS.2019.2910134
Perera, S., Dawande, M., Janakiraman, G., & Mookerjee, V. (2020). Retail Deliveries by Drones: How Will Logistics Networks Change? Production and Operations Management. 27(9), 2019-2034. doi: 10.1111/poms.13217
Pronello, C., & André, M. (2000). Pollutant emissions estimation in road transport models (INRETS-LTE Report, Vol. 2007). Retrieved from Pennsylvania State University, College of Information Sciences and Technology website: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.622.9641&rep=rep1&type=pdf
Raff, S. (1983). Routing and scheduling of vehicles and crews: The state of the art. Computers & Operations Research, 10(2), 63-211. doi: 10.1016/0305-0548(83)90030-8
Raj, R., & Murray, C. (2020). The multiple flying sidekicks traveling salesman problem with variable drone speeds. Transportation Research Part C: Emerging Technologies, 120, 102813. doi: 10.1016/j.trc.2020.102813
Ritha, W., & Antonitte Vinoline, I. (2014). Environmentally Responsible Repair and Waste Disposal Inventory Models. Aryabhatta Journal of Mathematics & Informatics, 6(1), 1-9. doi: 10.1136/inpract.23.1.53
Rodrigue, J.-P., Comtois, C., & Slack, B. (2013). The geography of transport systems (3rd ed.). London, UK: Routledge, Taylor & Francis Group.
Rueter, T. (2020, August 31). Amazon Wins FAA Approval for Drone Deliveries [Online news]. Retrieved from https://progressivegrocer.com/amazon-wins-faa-approval-drone-deliveries
Sacramento, D., Pisinger, D., & Ropke, S. (2019). An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies, 102, 289-315. doi: 10.1016/j.trc.2019.02.018
Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. Philadelphia, PA: Society for Industrial and Applied Mathematics.
Tsang, E. P. K., Wang, C. J., Davenport, A., Voudouris, G., & Lau, T. L. (1999). A Family of Stochastic Methods for Constraint Satisfaction and Optimisation. Proceedings of the First International Conference on the Practical Application of Constraint Technologies and Logic Programming, London, 359-383. doi: 10.1.1.62.5319
Xiao, Y., Zhao, Q., Kaku, I., & Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers & Operations Research, 39(7), 1419-1431. doi: 10.1016/j.cor.2011.08.013
Yampolskiy, R. V. (2018). Why We Do Not Evolve Software? Analysis of Evolutionary Algorithms. Evolutionary Bioinformatics, 14, 1-11. doi: 10.1177/1176934318815906
Zhang, W., Gajpal, Y., Appadoo, S. S., & Wei, Q. (2020). Multi-Depot Green Vehicle Routing Problem to Minimize Carbon Emissions. Sustainability, 12(8), 3500. doi: 10.3390/su12083500
Zhu, R., & Zhai, Y. (2017). Research on the application of VRP theory in logistics transportation. MATEC Web of Conferences 100, 05064. doi: 10.1051/matecconf/201710005064