隨著溫室氣體的排放量逐漸增加，全球暖化乃至氣候變遷都已是正在發生的議題。永續物流管理可以幫助減少溫室氣體排放量並減輕其對我們生活環境的影響。近年來，量子計算也越來越備受矚目，以使人工智慧進入到下一個世代。因此，在本文中我們使用了量子隨機數產生器來產生真隨機數，並嵌入在基因演算法中來解決永續供應鏈管理中的汙染運途問題。本論文汙染運途問題之目標式是以最小化二氧化碳之排放量，遵循由聯合國提出的17個永續發展目標之其中一項目標。
本論文中，我們提出一種兩階段的混合模型，其結合了改良的k-平均演算法與量子啟發之基因演算法，前者作為一種分群方法；後者則做為最小化貨車在運送路徑中產生的污染之最佳化引擎。我們也提出另外兩種混合模型來比較計算結果。其分別將最佳化引擎替換為禁忌搜索法與模擬退火法。為了比較三種混合模型的有效性，本研究使用30個汙染運途標竿問題來進行實驗。
根據實驗結果，我們發現所提出的三種混合模型針對於二氧化碳最小化的污染運問題，全都可以產生良好的解。並且三個模型對每個問題所產生的最優解都十分接近或甚至相同。其中以禁忌搜索法作為最佳化引擎的混合模型擁有最佳的穩定性，以量子啟發之基因演算法處理大型問題時則能以最少的迭代次數找到最佳解。因此，本論文提出的三種混合模型在解決組合最佳化問題時皆有良好的表現。

With increasing amount of greenhouse gases emission, global warming and even climate change is ongoing issues. Sustainable logistics and distribution management can help reduce greenhouse gases emission and lighten influence against our living environment. Nowadays, quantum computing has become more and more popular in recent years to advance Artificial Intelligence into next generation. Hence, we apply quantum random number generator to provide true random numbers for the genetic algorithm to solve the Pollution Routing Problems (PRPs) in sustainable supply chain management in this thesis. The objective of the PRPs is to minimize carbon dioxide emissions to follow one of 17 Sustainable Development Goals setting by the United Nations.
In this thesis, we develop a two-phase hybrid model combining a modified k-Means algorithm as a clustering method and a Quantum-inspired Genetic Algorithm as an optimization engine to solve the PRPs aiming to minimize pollution produced by trucks traveling along delivery routes. We also compare computation performance with the other two hybrid models by replacing different optimization engines, the Tabu Search Algorithm and the Simulated Annealing Algorithm. In order to verify and compare the effectiveness of three hybrid models, our research used 30 PRP benchmark problems to conduct our experiments.
From the experimental results, we find out that all the proposed hybrid models can provide good solution quality for CO2 emission minimization for the PRPs. Moreover, these three models had similar best results on each instance if not the same. Among three hybrid models, the one with the Tabu Search Algorithm as optimization engine had the best stability and the one with the Quantum-inspired Genetic Algorithm as optimization engine obtained optimal results with the least iterations for big scale problems. Hence, the hybrid models in this thesis have great performance in solving combination optimization problems.

Alander, J. T. (1992). On optimal population size of genetic algorithms. CompEuro 1992 Proceedings Computer Systems and Software Engineering, 65-70. (DOI: 10.1109/CMPEUR.1992.218485)
Augerat, P., Belenguer, J.M., Benavent, E., Corberan, A., Naddef, D., & Rinaldi, G. (1995). Computational results with a branch and cut code for the capacitated vehicle routing problem. Institut National Polytechnique, 38 – Grenoble, France.
Badeau, P., Guertin, F., Gendreau, M., Potvin, J. Y., & Taillard, E. (1997). A parallel tabu search heuristic for the vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 5(2), 109-122. (DOI: 10.1016/S0968-090X(97)00005-3)
Baños, R., Ortega, J., Gil, C., Fernández, A., & de Toro, F. (2013). A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows. Expert Systems with Applications, 40(5), 1696-1707. (DOI: 10.1016/j.eswa.2012.09.012)
Barbarosoglu, G., & Ozgur, D. (1999). A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 26(3), 255-270. (DOI: 10.1016/S0305-0548(98)00047-1)
Bergstorm, R. Y. (1993). An annotated essay: Environmental affairs. Production, 105(4), 36-41.
Bektaş, T., & Laporte G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45, 1232-1250. (DOI: 10.1016/j.trb.2011.02.004)
Brandão, J., & Mercer, A. (1997). A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal of Operational Research, 100(1), 180-191. (DOI: 10.1016/S0377-2217(97)00010-6)
Chávez, J., Escobar, J., Echeverri, M., & Meneses, C. (2018). A heuristic algorithm based on tabu search for vehicle routing problems with backhauls. Decision Science Letters, 7(2), 171-180. (DOI: 10.5267/j.dsl.2017.6.001)
Chen, J. C., Wu, C. C., Chen, C. W., & Chen, K. H. (2012). Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm. Expert Systems with Applications, 39(11), 10016-10021. (DOI: 10.1016/j.eswa.2012.01.211)
Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20(3), 309-318. (DOI: 10.1057/jors.1969.75)
Dahi, Z. A. E. M., Mezioud, C., & Draa, A. (2016). A quantum-inspired genetic algorithm for solving the antenna positioning problem. Swarm and Evolutionary Computation, 31, 24-63. (DOI: 10.1016/j.swevo.2016.06.003)
Dane, A. D., Veldhuis, A., Boer, D. K. G.de, Leenaers, A.J.G., & Buydens, L. M. C. (1998). Application of genetic algorithms for characterization of thin layered materials by glancing incidence x-ray reflectometry. Physica B: Condensed Matter, 253(3-4), 254-268. (DOI: 10.1016/S0921-4526(98)00398-6)
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. (DOI: 10.1287/mnsc.6.1.80)
Demira, E., Bektaş, T., & Laporte, G. (2014). The bi-objective pollution-routing problem. European Journal of Operational Research, 232(3), 464-478. (DOI: 10.1016/j.ejor.2013.08.002)
Deng, A., Mao, C., & Zhou, Y. (2009). Optimizing research of an improved simulated annealing algorithm to soft time windows vehicle routing problem with pick-up and delivery. Systems Engineering - Theory & Practice, 29(5), 186-192. (DOI: 10.1016/S1874-8651(10)60049-X)
Du, L., & He, R. (2012). Combining nearest neighbor search with tabu search for large-scale vehicle routing problem. Physics Procedia, 25, 1536-1546. (DOI: 10.1016/j.phpro.2012.03.273)
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)
Feynman, R. P. (1982). Simulating physics with computers. International Journal of Theoretical Physics, 21, 467-488. (DOI: 10.1007/BF02650179)
Forgy, E. W. (1965). Cluster analysis of multivariate data: efficiency versus interpretability of classifications. Biometrics, 21(3), 768-769.
Franceschetti, A., Demir, E., Honhon, D., Van Woensel, T., Laporte, G., & Stobbe, M. (2017). A metaheuristic for the time-dependent pollution-routing problem. European Journal of Operational Research, 259(3), 972-991. (DOI: 10.1016/j.ejor.2016.11.026)
Ganganath, N., Cheng, C. T., & Tse, C. K. (2014). Data clustering with cluster size constraints using a modified k-means algorithm. 2014 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery. (DOI: 10.1109/CyberC.2014.36)
Ghoseiri, K., & Ghannadpour, S. F. (2010). Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Applied Soft Computing, 10(4), 1096-1107. (DOI: 10.1016/j.asoc.2010.04.001)
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340-349. (DOI: 10.1287/opre.22.2.340)
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549. (DOI: 10.1016/0305-0548(86)90048-1)
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94. (DOI: 10.1287/inte.20.4.74)
Golden, B. L. (1975). Vehicle Routing Problems: Formulations and Heuristic Solution Techniques (No. TR-113). Massachusetts Institute of Technology.
Grefenstette, J. J. (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 16(1), 122-128. (DOI: 10.1109/TSMC.1986.289288)
Haghani, A., & Jung, S. (2005). A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 32(11), 2959-2986. (DOI: 10.1016/j.cor.2004.04.013)
Haw, J. Y., Assad, S. M., Lance, A. M., Ng, N. H. Y., Sharma, V., Lam, P. K., & Symul, T. (2015). Maximization of extractable randomness in a quantum random-number Generator. Physical Review Applied, 3, 054004. (DOI: 10.1103/PhysRevApplied.3.054004)
Herrero-Collantes, M., & Garcia-Escartin, J.C. (2017). Quantum random number generators. Reviews of Modern Physics, 89(1), 015004. (DOI: 10.1103/RevModPhys.89.015004)
Herreros, A., Baeyens, E., & Perán, J. R. (2002). Design of PID-type controllers using multiobjective genetic algorithms. ISA Transactions, 41(4), 457-472. (DOI: 10.1016/S0019-0578(07)60102-5)
Holland, J. (1975). Adaptation in natural and artificial systems: an introductory analysis with application to biology. Control and Artificial Intelligence.
Jennewein, T., Achleitner, U., Weihs, G., Weinfurter, H., & Zeilinger, A. (2000). A fast and compact quantum random number generator. Review of Scientific Instruments, 71(4), 1675. (DOI: 10.1063/1.1150518)
Kanniah, K.D., Zaman, N.A.F.K., Kaskaoutis, D.G., & Latif, M.T. (2020). COVID-19’s impact on the atmospheric environment in the southeast asia region. Science of the Total Environment, 736, 139658. (DOI: 10.1016/j.scitotenv.2020.139658)
Kirkpatrick, S., Gelatt Jr., C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680. (DOI: 10.1126/science.220.4598.671)
Koç, Ç. & Karaoglan, I. (2016). The green vehicle routing problem: a heuristic based exact solution approach. Applied Soft Computing, 39, 154-164. (DOI: 10.1016/j.asoc.2015.10.064)
Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408-416. (DOI: 10.1287/trsc.1090.0301)
MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Berkeley Symposium on Mathematical Statistics and Probability, 5.1, 281-297.
Majidi1, S., Hosseini-Motlagh, S.M., & Ignatius, J. (2018). Adaptive large neighborhood search heuristic for pollution-routing problem with simultaneous pickup and delivery. Soft Computing, 22, 2851-2865. (DOI: 10.1007/s00500-017-2535-5)
Maxie, E. (1994). Supplier performance and the environment. In Proceeding of 1994 IEEE International Symposium on Electronics and The Environment, 323-327. IEEE. (DOI: 10.1109/ISEE.1994.337238)
Narayanan, A., & Moore, M. (1996). Quantum-inspired genetic algorithms. University of Exeter, Exeter, United Kingdom.
Nurcahyo, G. W., Alias, R. A., Shamsuddin, S. M., & Md. Sap, M. N. (2002). Sweep algorithm in vehicle routing problem for public transport. Jurnal Antarabangsa (Teknologi Maklumat), 2, 51-64.
Ochi, L. S., Vianna, D. S., Drummond, L. M. A., & Victor, A. (1998). A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet. Future Generation Computer Systems, 14(5-6), 285-292. (DOI: 10.1016/S0167-739X(98)00034-X)
Schaffer, J. D., Caruana, R., Eshelman, L. J., & Das, R. (1989). A study of control parameters affecting online performance of genetic algorithms for function optimization. In Proceedings of the 3rd International Conference on Genetic Algorithms, 51-60.
Stefanov, A., Gisin, N., Guinnard, O., Guinnard, L., & Zbinden, H. (2000). Optical quantum random number generator. Journal of Modern Optics, 2000, 47(4), 595-598. (DOI: 10.1080/09500340008233380)
Symul, T., Assad, S. M., & Lam, P. K. (2011). Real time demonstration of high bitrate quantum random number generation with coherent laser light. Applied Physics Letters, 98, 23113. (DOI: 10.1063/1.3597793)
Tajik, N., Tavakkoli-Moghaddam, R., Vahdani, B., & Meysam Mousavi, S. (2014). A robust optimization approach for pollution routing problem with pickup and delivery under uncertainty. Journal of Manufacturing Systems, 33(2), 277-286. (DOI: 10.1016/j.jmsy.2013.12.009)
Tarantilis, C. D., & Kiranoudis, C. T. (2002). Distribution of fresh meat. Journal of Food Engineering, 51(1), 85-91. (DOI: 10.1016/S0260-8774(01)00040-1)
Tiwari, A., & Chang, P. C. (2015). A block recombination approach to solve green vehicle routing problem. International Journal of Production Economics, 164, 379-387. (DOI: 10.1016/j.ijpe.2014.11.003)
Tavakkoli-Moghaddam, R., Safaei, N., Kah, M. M. O., & Rabbani, M. (2007). A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing. Journal of the Franklin Institute, 344(5), 406-425. (DOI: 10.1016/j.jfranklin.2005.12.002)
Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problems. Discrete Applied Mathematics, 123(1-3), 487-512. (DOI: 10.1016/S0166-218X(01)00351-1)
Ramachandran, A., Marshall, E. S., Love, D. R., Baguley, B. C., & Shelling, A. N. (2009). Activin is a potent growth suppressor of epithelial ovarian cancer cells. Cancer Letters, 285(2), 157-165. (DOI: 10.1016/j.canlet.2009.05.010)
Weise, T., Podlich, A., & Gorldt, C. (2009). Solving real-world vehicle routing problems with evolutionary algorithms. In Natural Intelligence for Scheduling, Planning and Packing Problems (29-53). Springer, Berlin, Heidelberg. (DOI: 10.1007/978-3-642-04039-9_2)
Wren, A., & Holliday, A. (1972). Computer scheduling of vehicles from one or more depots to a number of delivery points. Journal of the Operational Research Society, 23(3), 333-344. (DOI: 10.1057/jors.1972.53)
Xiao, Y., & Konak, A. (2016). The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transportation Research Part E: Logistics and Transportation Review, 88, 146-166. (DOI: 10.1016/j.tre.2016.01.011)
Xiao, Y., & Konak, A. (2017). A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem. Journal of Cleaner Production, 167, 1450-1463. (DOI: 10.1016/j.jclepro.2016.11.115)
Xiao, Y., Zuo, X., Huang, J., Konak, A., & Xu, Y. (2020). The continuous pollution routing problem. Applied Mathematics and Computation, 387, 125072. (DOI: 10.1016/j.amc.2020.125072)
Yu, V. F., Perwira Redi, A. A. N., Hidayat, Y. A., & Wibowo, O. J. (2017). A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 53, 119-132. (DOI: 10.1016/j.asoc.2016.12.027)