隨著工業蓬勃發展，溫室氣體排放量逐年成長。根據行政院統計，我國 2019 年的運輸排放占二氧化碳排放的 14.17%，故本研究從運輸方面下手，透過最佳化運送路徑，可以有效的減少油耗量，進而改善環境問題。本文的研究題目為雙目標汙染車輛路由問題，是由具時間窗的車輛路由問題所延伸；兩個目標為油耗量和時間。根據研究，車速越快的時候，所消耗的油量亦愈高，因此縮短時間與減少油耗量兩個目標存在衝突。本研究使用多目標演算法，能夠在一定的時間內，求得所需要的解集合。使用 NSGA-III 演算法，透過設立參考點的方式維持族群的多樣性。為了在一開始獲得較好的族群，使用最近鄰點法結合節省法的方式去建立良好的初始解。以動態規劃解碼生成路徑，配合改良的交配機制使得子代容易將優良的基因繼承下去。考慮到解空間過大的問題，本研究使用區域搜尋來探勘較優秀的解。為了避免多樣性下降，會移除表現較不好的重複個體。相較於過去的實驗結果，本研究能夠在計算成本與過去研究近似的情況下，得出更全面的柏拉圖凌越解集合。

行政院環保署。網址：https://www.epa.gov.tw/Page/81825C40725F211C/6a1ad12a-4903-4b78-b246-8709e7f00c2b上網日期：2018年9月9日。
T. Bektaş and G. Laporte, “The pollution-routing problem,” Transportation Research Part B, vol. 45, no. 8, pp. 1232–1250, 2011.
E. Demir, T. Bektaş, and G. Laporte, “The bi-objective pollution-routing problem,” European Journal of Operational Research, vol. 232, no. 3, pp. 464–478, 2014.
E. Demir, T. Bektaş, and G. Laporte, “An adaptive large neighborhood search heuristic for the pollution-routing problem,” European Journal of Operational Research, vol. 223, no. 9, pp. 346–359, 2012.
T. Bäck, “Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms,” Oxford university press, pp. 120, 1996.
B. Miller and D. Goldberg, “Genetic algorithms, tournament selection, and the effects of noise,” Complex Systems, vol. 9, no. 3, pp. 193–212, 1995.
G. Dantzig and J. Ramser, “The truck dispatching problem,” Management Science, vol. 6, no. 1, pp. 80–91, 1959.
P. Augerat, J. Belenguer, E. Benavent, A. Corberán, and D. Naddef, “Separating capacity constraints in the CVRP using tabu search,” European Journal of Operational Research, vol. 106, no. 2, pp. 546–557, 1998.
H. Li and A. Lim, “Local search with annealing-like restarts to solve the VRPTW,” European Journal of Operational Research, vol. 150, no. 1, pp. 115–127, 2003.
J. Renaud, G. Laporte, and F. Boctor, “A tabu search heuristic for the multi-depot vehicle routing problem,” Computers & Operations Research, vol. 23, no. 3, pp. 229–235, 1996.
Ç. Koç, T. Bektaş, O. Jabali, and G. Laporte, “The fleet size and mix pollution-routing problem”, Transportation Research Part B: Methodological, vol. 70, pp. 239–254, 2014.
C. Lin, K. Choy, G. Ho, S. Chung, and H. Lam, “Survey of green vehicle routing problem: past and future trends,” Expert Systems with Applications, vol. 41, no. 4, pp. 1118–1138, 2013.
J. Hickman, D. Hassel, R. Joumard, Z. Samaras, and S. Sorenson, “Methodology for calculating transport emissions and energy consumption(Report for the Projet MEET),” Transport Research Laboratory. Edinburgh, 1999.
J. Jemai, M. Zekri, and K. Mellouli, “An NSGA-II algorithm for the green vehicle routing problem,” European Conference on Evolutionary Computation in Combinatorial Optimization, vol. 7245, pp. 37–48, 2012.
K. Boriboonsomsin, A. Vu, and M. Barth, “Eco-driving: pilot evaluation of driving behavior changes among U.S. drivers,” University of California, 2010.
E. Adiba, E. Messaoud, and E. Ahemd, “A hybrid ant colony system for green capacitated vehicle routing problem in sustainable transport,” Journal of Theoretical & Applied Information Technology, vol. 54, no. 2, pp. 198–208, 2013.
S. Ropke and D. Pisinger, “An adaptive large neighborhood search for a vehicle routing problem with multiple routes,” Transportation Science, vol. 40, no. 4, pp. 393–546, 2006.
R. Kramer and A. Subramanian, “A matheuristic approach for the pollution-routing problem,” European Journal of Operational Research, vol. 243, no. 2, 2014.
A. Romero-Ocaño, M. Cosío-León, V. Valenzuela-Alcaraz, and C. Brizuela, “The impact of gradually replacing fossil fuel-powered vehicles with electric ones: a bi-objective optimisation approach,” Expert Systems with Applications, vol. 194, 2022.
Q. Zhang and H.Li, “MOEA/D: A multi-objective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712–731, 2007.
S. Kirkpatrick, C. Gelatt, and M. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.
F. Glover, “Future paths for integer programming and links to artificial intelligence,” Computers and Operations Research, vol. 13, no. 5, pp. 533–549, 1986.
D. Prisinger and S. Ropke, “An adaptive large neighborhood search heauristic for the pickup and delivery problem with time window,” Transportation Science, vol. 40, no. 4, pp. 455–472, 2006.
D. Pisinger and S. Ropke, “Large neighborhood search,” Handbook of metaheuristics, pp. 99–127, 2019.
P. Shaw, “A new local search algorithm providing high quality solutions to vehicle routing problems,” Department of Computer Science, vol. 46, 1997.
M. Diana and M. Dessouky, “A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows,” Transportation Research Part B: Methodological, vol. 38, no. 6, pp. 539–557, 2004.
A. Franceschetti, E. Demir, D. Honhon, T. Woensel, G. Laporte, and M. Stobbe, “A metaheuristic for the time-dependent pollution-routing problem,” European Journal of Operational Research, vol. 259, no. 3, pp. 972–991, 2017.
Ç. Koç, T. Bektaş, O. Jabali, and G. Laporte, “A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows,” Computers and Operations Research, vol. 64, pp. 11–27, 2015.
G. Clarke and J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, vol. 12, no. 4, pp. 568–581, 1964.
R. Karg and G. Thompson, “A heuristic approach to traveling salesman problems,” Management Science, vol. 10, no. 2, pp. 225–248, 1964.
D. Goldberg and R. Lingle, “Alleles, loci and the traveling salesman problem,” International Conference on Genetic Algorithms, vol. 1, no. 15, pp. 154–159, 1985.
F. Croce, R. Tadei, and G. Volta, “A genetic algorithm for the job shop problem,” Computer and Operation Research vol. 22, no. 1, pp. 15–24, 1995.
K. Deep and H. Mebrahtu, “New variations of order crossover for travelling salesman problem,” International Journal of Combinatorial Optimization Problems and Informatics, vol. 2, no. 1, pp. 2–13, 2011.
L. Hvattum, “Adjusting the order crossover operator for capacitated vehicle routing problems,” Computers and Operations Research, vol. 148, 2022.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiboective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.
H. Jain and K. Deb, “An improved adaptive approach for elitist nondominated sorting genetic algorithm for many-objective optimization,” International Conference on Evolutionary Multi-Criterion Optimization, pp. 307–321, 2013.
P. Auer, “Using confidence bounds for exploitation-exploration trade-offs,” The Journal of Machine Learning Research, vol. 3, no. 3, pp. 397–422, 2002.
K. Fialho, S. Kwong, and Q. Zhang, “Adaptive operator selection with bandits for a multi-objective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 1, pp. 114–130, 2014.
R. Gonçalves, C. Almeida, and A. Pozo, “Upper confidence bound (UCB) algorithms for adaptive operator selection in MOEA/D,” International Conference on Evolutionary Multi-Criterion Optimization, vol. 8, pp. 411–425, 2015.
C. Prins, “A simple and effective evolutionary algorithm for the vehicle routing problem,” Computers and Operations Research, vol. 31, no. 12, pp. 1985–2002, 2004.
M. Nawaz, E. Enscore, and I. Ham, “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem,” Omega, vol. 11, no. 1, pp. 91–95, 1983.
G. Croes, “A method for solving traveling-salesman problems,” Operations Research, vol. 6, no. 6, pp.791–812, 1958.
C. Coello, G. Lamont, and D. Veldhuizen, Evolutionary algorithms for solving multi-objective problems, vol. 5, no. 2, pp. 79–104, 2007.
R. Eshtehadi1, M. Fathian1, M. Pishvaee1, and E. Demir, “A hybrid metaheuristic algorithm for the robust pollution-routing problem,” Journal of Industrial and Systems Engineering, vol. 11, no. 1, pp. 244–257, 2018.
S. Majidi, S. Motlagh, and J. Ignatius, “Adaptive large neighborhood search heuristic for pollution-routing problem with simultaneous pickup and delivery,” Soft Computing, vol. 22, no. 9, pp. 2851–2865, 2018.