本論文使用多目標演化演算法NSGAIII求解雙目標汙染車輛路由問題 (Pollution Routing Problem)，此問題為車輛路由問題 (Vehicle Routing Prolbem) 的延伸。雙目標汙染車輛路由問題中物流車有最大容量 (capacity) 限制；客戶與倉庫都有最早開始服務時間 (ready time) 與最晚服務時間 (due time)，物流車必須在這段時間內抵達，此為時間限制。我們希望同時最小化總油耗量與最小化總花費時間，但速度在一定速度後越快變得越耗油，想要降低耗油會拉長花費時間，兩者無法同時下降。然而，我們可以求出非凌越解 (non-dominated solution)，這些解在目標空間中形成柏拉圖前緣 (Pareto front)，本論文的目標是求得接近此問題之真實解的柏拉圖前緣。
我們使用最近鄰點法 (Nearest Neighborhood, NN) 初始化方式來使初始解具備一定品質。多目標路線建構來提前使解具有多目標特性與更具多樣性。探討多種速度對於汙染車輛路由問題的影響性。使用NEH與2-Opt搜尋法的來增強最小化總行駛距離來接近真實解之柏拉圖前緣。
本論文提出的演算法在使解族群更具有多目標特性有較佳的效果。

[1]行政院環保署。網址：https://www.epa.gov.tw/ct.asp?xItem=10052&ctNode=31352&mp=epa
上網日期：2018年9月9日。
[2]P. Augerat, J. M. 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, pp. 546-557, 1998.
[3]S. Erdoğan and E. Miller-Hooks, “A green vehicle routing problem,” Transportation Research Part E：Logistics and Transportation Review, vol. 48, pp. 100-114, 2012.
[4]H. Li and A. Lim, “Local search with annealing-like restarts to solve the VRPTW,” European Journal of Operational Research, vol. 150, pp. 115-127, 2003.
[5]T. Bektaş and G. Laporte, “The pollution-routing problem,” Transportation Research Part B, vol. 45, pp. 1232 – 1250, 2011.
[6]D. Goldberg and R. Lingle, “Allels, Loci and the traveling salesman problem,” 1^st ICGA, pp. 154-159, 1985.
[7]I. M. Oliver, D. J. Smith and J. Holland, “A study of permutation crossover operators on the travelling salesman problem,” 2^nd International Conference on Genetic Algorithms and Their Applications, pp. 224-230, 1984.
[8]L. Davis, “Applying adaptive algorithms to epistatic domains, International Joint Conference on Artificial Intelligence, pp. 162-164, 1985
[9]E. Falkenauer and S. Bouffoix, “A genetic algorithm for job shop,” IEEE ICRA, pp. 824-829, 1991.
[10]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, pp. 346 – 359, 2012.
[11]E. Demir, T. Bektaş and G. Laporte, “The bi-objective pollution-routing problem,” European Journal of Operational Research, vol. 232, pp. 464 – 478, 2014.
[12]C. Lin, K. L. Choy, G. T. S. Ho, S. H. Chung and H. Y. Lam, “Survey of green vehicle routing problem: past and future trends,” Expert Systems with Applications, vol.41, no.4, pp.1118-1138, 2013
[13]Y. Xiao, Q. Zhao, I. Kaku and Y. Xu, ”Development of a fuel consumption optimization model for the capacitated vehicle routing problem,” Computers and Operations Research,vol.39, no.7, pp. 1419-1431, 2012.
[14]J. Jemai, M. Zekri and K. Mellouli, “An NSGA-II algorithm for the green vehicle routing problem,” In: European Conference on Evolutionary Computation in Combinatorial Optimization, vol.7245, pp.37-48, 2012.
[15]K. Boriboonsomsin, A. Vu and M. Barth, “Eco-driving: pilot evaluation of driving behavior changes among U.S. drivers,” University of California, Riverside, 2010.
[16]H. Aronsson and M. H. Brodin, “The environmental impact of changing logistics structures,” International Journal of Logistics Management, vol.17, no.3, pp.394-415, 2006.
[17]P. Bickel, R. Friedrich, H. Link, L. Stewart and C. Nash, “Introducing environmental externalities into transport pricing: Measurement and implications,” Transport Reviews, vol.26, no.4, pp.389-415, 2006.
[18]P. R. D. O. D. Costa, S. Mauceri, P. Carroll and F. Pallonetto, “A genetic algorithm for a green vehicle routing problem,” Eletronic Notes in Discrete Mathematic, vol.64, pp.65-75, 2018.
[19]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.
[20]E. B. E. I. Adiba, E. Messaoud and E. H. A. Ahemd, “A hybrid ant colony system for green capacitated vehicle routing problem in sustainbale transport,” Journal of Theoretical &Applied Information Technology, vol.53, no.2, pp.198-208, 2013.
[21]C. Y. Wu, T. Visutarrom and T. C. Chiang, “Green vehicle routing problem：the tradeoff between travel distance and carbon emissions,” 15th International Conference on Control, Automation, Robotics and Vision, Singapore, pp. 1659-1664, 2018.
[22]J. Jemai, M. Zekri and K. Mellouli, “Multi-objective genetic algorithm for the green vehicle routing problem：a comparative study,” Journal of Theoretical and Applied information Technology, vol. 95, pp. 6597-6607.
[23]K. Deb, S. Agrawal, A. Pratap and T. Meyarivan, “A fast elitist non-dominated sorting genetic algorithm for the multi-objective optimization：NSGA-II,” International Conference on Parallel Problem Solving from Nature, vol. 1917, pp.849-858, 2000.
[24]E. Zitzler, M. Laumanns and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” Computer Engineering and Networks Laboratory(TIK), TIK-report 103, 2001.
[25]E. Zitzler and S. Künzli, “Indicator-based selection in multiobjective search,” International Conference on Parallel Problem Solving from Nature, vol. 3242, pp. 832-842, 2004.
[26]A. Tiwari and P. C. Chang, “A block recombination approach to solve green vehicle routing problem,” International Journal of Production Economics, vol. 164,pp. 379-387, 2015.
[27]P. Shaw, “Using constraint programming and local search methods to solve vehicle routing problem,” Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming. Springer, New York, pp.417-431, 1998
[28]D. Prisinger and S. Ropke, ”A general heuristic for vehicle routing problems,”Computers & Operations Research, vol.34, no.8, pp.2403-2435, 2007
[29]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, 2006a,
[30]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, Springer, Berlin, Heidelberg, pp. 307-321, 2013.
[31]C. Prins, “A simple and effective evolutionary algorithm for the vehicle routing problem,” Computers & Operations Research, vol.31, no.12, pp.1985-2002, 2004.
[32]R. M. Chen, F. R. Hsieh, and D. S. Wu, “Heuristics based ant colony optimization for vehicle routing problem,” 7th IEEE Conference on Industrial Electronics and Applications (ICIEA), pp. 1039-1043, 2012.
[33]C. A. C. Coello, G. B. Lamont and D. A. Van Veldhuizen, Evolutionary algorithms for solving multi-objective problems, vol. 5, pp. 79-104, 2007.