隨著溫室氣體的排放量逐漸增加，全球暖化乃至氣候變遷都已是正在發生的議題。永續物流管理可以幫助減少溫室氣體排放量並減輕其對我們生活環境的影響。在車輛路徑規劃問題中，傳統方法主要著重於最小化總行駛距離或車輛數量，然而這些方法未必能有效減少碳排放。本研究提出了一種考慮車輛載重對燃油消耗影響的汙染路徑規劃模型，目標為最小化運輸過程中的二氧化碳排放量，以響應聯合國永續發展目標中關於氣候行動的倡議。在模型中，我們特別考慮了車輛空重、每單位需求重量，以及載重對基礎油耗的影響係數等實際營運因素，使最佳化結果更符合實際運輸情況。
本論文提出一種創新的混合啟發式演算法，以傳統的螢火蟲演算法為基礎，進行改良並創新性地加入破壞重組策略，稱作改良式螢火蟲演算法。改良後的螢火蟲演算法採用基於漢明距離的吸引力計算機制，並結合遺傳算子來增強解的多樣性。此外，演算法會在最後執行破壞重組操作，以避免陷入局部最佳解。作為演算法的基礎架構，我們在所有測試演算法中皆採用掃描演算法產生良好初始解，並使用區域搜索策略進行解的優化。
為了驗證所提出方法的效能，提出另外兩種模型來比較計算結果。其分別將元啟發式演算法替換為基因演算法與蟻群演算法。本研究使用 30 個汙染路徑標竿問題來進行實驗。實驗結果顯示，本研究提出的混合螢火蟲演算法具有良好的解品質與收斂性能。通過分析最佳解的路徑結構與碳排放量，我們發現該方法能有效平衡載重分配，並在考慮運輸限制的情況下產生具有實用價值的配送方案。

Increasing greenhouse gas emissions have made global warming and climate change pressing issues. Sustainable logistics management can help reduce emissions and mitigate environmental impacts. In vehicle routing problems, traditional approaches focus on minimizing distance or fleet size, which may not effectively reduce carbon emissions. This study introduces a pollution routing model that considers the effect of vehicle load on fuel consumption, aiming to minimize CO₂ emissions. The model incorporates practical factors such as vehicle empty weight, demand weight per unit, and the load impact on base fuel consumption.
A hybrid metaheuristic algorithm is proposed, built upon an enhanced Firefly Algorithm that integrates a Hamming distance-based attraction mechanism, genetic operators for solution diversity, and a ruin-and-recreate strategy to escape local optima. A scanning algorithm is used to generate robust initial solutions, which are further refined through local search techniques.
To evaluate performance, two alternative models—based on Genetic Algorithm and Ant Colony Optimization—are compared using 30 benchmark pollution routing problems. Experimental results demonstrate that the proposed hybrid Firefly Algorithm achieves high-quality solutions with good convergence, effectively balancing load distribution while providing practical delivery routes under transportation constraints.

Abdellaoui, A., Benabbou, L., & Hallaoui, I. E. (2024). Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering. arXiv preprint arXiv:2403.14013.
Altabeeb, A. M., Mohsen, A. M., & Ghallab, A. (2019). An improved hybrid firefly algorithm for capacitated vehicle routing problem. Applied Soft Computing, 84, 105728. (https://doi.org/10.1016/j.asoc.2019.105728)
Alweshah, M., Almiani, M., Almansour, N., Al Khalaileh, S., Aldabbas, H., Alomoush, W., & Alshareef, A. (2022). Vehicle routing problems based on Harris Hawks optimization. Journal of Big Data, 9(1), 42. (https://doi.org/10.1186/s40537-022-00593-4)
Azad, T., & Hasin, M. A. A. (2019). Capacitated vehicle routing problem using genetic algorithm: a case of cement distribution. International Journal of Logistics Systems and Management, 32(1), 132-146.
Bektaş, T., & Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45(8), 1232-1250. (https://doi.org/10.1016/j.trb.2011.02.004)
Brandão, J. (2020). A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. European Journal of Operational Research, 284(2), 559-571. (https://doi.org/10.1016/j.ejor.2020.01.008)
Cai, J., Wang, P., Sun, S., & Dong, H. (2022). A dynamic space reduction ant colony optimization for capacitated vehicle routing problem. Soft Computing, 26(17), 8745-8756. (https://doi.org/10.1007/s00500-022-07198-2)
Cheng, L. H., & Wang, J. Q. (2010). Improved genetic algorithm for vehicle routing problem. Jisuanji Gongcheng yu Yingyong (Computer Engineering and Applications), 46(36), 219-221.
Costa, J. G. C., Mei, Y., & Zhang, M. (2022). Guided local search with an adaptive neighbourhood size heuristic for large scale vehicle routing problems. In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 213-221).
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. (https://doi.org/10.1287/mnsc.6.1.80)
Lübbecke, G., Desrosiers, J., & Solomon M. M., Eds. (2005). Column Generation, First Edition, Springer Nature Link. (https://doi.org/10.1007/b135457)
Ding, Q., Hu, X., Sun, L., & Wang, Y. (2012). An improved ant colony optimization and its application to vehicle routing problem with time windows. Neurocomputing, 98, 101-107. (https://doi.org/10.1016/j.neucom.2011.09.040)
Dorigo, M. (1992). Optimization, Learning and Natural Algorithms. Ph. D. Thesis, Politecnico di Milano.
Erdelić, T., & Carić, T. (2022). Goods delivery with electric vehicles: Electric vehicle routing optimization with time windows and partial or full recharge. Energies, 15(1), 285. (https://doi.org/10.3390/en15010285)
Falkner, J. K., & Schmidt-Thieme, L. (2023). Too Big, so Fail?--Enabling Neural Construction Methods to Solve Large-Scale Routing Problems. arXiv preprint arXiv:2309.17089.
Gentil, C., Basset-Mens, C., Manteaux, S., Mottes, C., Maillard, E., Biard, Y., & Fantke, P. (2020). Coupling pesticide emission and toxicity characterization models for LCA: application to open-field tomato production in Martinique. Journal of Cleaner Production, 277, 124099. (https://doi.org/10.1016/j.jclepro.2020.124099)
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340-349. (https://doi.org/10.1287/opre.22.2.340)
Giri, A. R., Chen, T., Rajendran, V. P., & Khamis, A. (2022). A metaheuristic approach to emergency vehicle dispatch and routing. In 2022 IEEE International Conference on Smart Mobility (SM) (pp. 27-31). IEEE.
Golden, B. L., Magnanti, T. L., & Nguyen, H. Q. (1977). Implementing Vehicle Routing Algorithms. (https://doi.org/10.1002/net.3230070203)
Gupta, A., Ghosh, S., & Dhara, A. (2022). Deep reinforcement learning algorithm for fast solutions to vehicle routing problem with time-windows. In Proceedings of the 5th Joint International Conference on Data Science & Management of Data (9th ACM IKDD CODS and 27th COMAD) (pp. 236-240).
Hanafi, R., Rusman, M., Mardin, F., Parenreng, S. M., & Azzazli, A. (2020, June). Distribution Route Optimization of a Capacitated Vehicle Routing Problem by Sweep Algorithm. In IOP Conference Series: Materials Science and Engineering (875(1), p. 012066). IOP Publishing.
Holland, J. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The MIT Press (https://doi.org/10.7551/mitpress/1090.001.0001)
Holló-Szabó, Á., & Botzheim, J. (2022). Bacterial memetic algorithm for asymmetric capacitated vehicle-routing problem. Electronics, 11(22), 3758. (https://doi.org/10.3390/electronics11223758)
Huang, Y. H., Blazquez, C. A., Huang, S. H., Paredes-Belmar, G., & Latorre-Nuñez, G. (2019). Solving the feeder vehicle routing problem using ant colony optimization. Computers & Industrial Engineering, 127, 520-535. (https://doi.org/10.1016/j.cie.2018.10.037)
İpek, A. B. (2023). Multi-objective simulation optimization integrated with analytic hierarchy process and technique for order preference by similarity to ideal solution for pollution routing problem. Transportation Research Record, 2677(1), 1658-1674. (https://doi.org/10.1177/03611981221105503)
Jamil, A., Abdallah, B. N., & Leksono, V. A. (2021). Firefly algorithm for multi-type vehicle routing problem. In Journal of Physics: Conference Series (1726(1), p. 012006). IOP Publishing. (https://doi.org/10.1088/1742-6596/1726/1/012006)
Jiang, X. Y., Chen, W. C., & Liu, Y. T. (2024). A study on the vehicle routing problem considering infeasible routing based on the improved genetic algorithm. International Journal of Engineering and Technology Innovation, 14(1), 67-84. (https://doi.org/10.46604/ijeti.2023.12612)
Khoo, T. S., & Mohammad, B. B. (2021). The parallelization of a two-phase distributed hybrid ruin-and-recreate genetic algorithm for solving multi-objective vehicle routing problem with time windows. Expert Systems with Applications, 168, 114408. (https://doi.org/10.1016/j.eswa.2020.114408)
Khoo, T. S., Mohammad, B. B., Wong, V. H., Tay, Y. H., & Nair, M. (2020). A two-phase distributed ruin-and-recreate genetic algorithm for solving the vehicle routing problem with time windows. IEEE Access, 8, 169851-169871. (https://doi.org/10.1109/ACCESS.2020.3023741)
Kyriakakis, N. A., Marinaki, M., & Marinakis, Y. (2021). A hybrid ant colony optimization-variable neighborhood descent approach for the cumulative capacitated vehicle routing problem. Computers & Operations Research, 134, 105397. (https://doi.org/10.1016/j.cor.2021.105397)
Lai, D., Costa, Y., Demir, E., Florio, A. M., & Van Woensel, T. (2024). The pollution-routing problem with speed optimization and uneven topography. Computers & Operations Research, 164, 106557. (https://doi.org/10.1016/j.cor.2024.106557)
Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408-416. (https://www.jstor.org/stable/25769465)
Lee, C. Y., Lee, Z. J., Lin, S. W., & Ying, K. C. (2010). An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem. Applied Intelligence, 32, 88-95. (https://doi.org/10.1007/s10489-008-0136-9)
Li, B., Wu, G., He, Y., Fan, M., & Pedrycz, W. (2022). An overview and experimental study of learning-based optimization algorithms for the vehicle routing problem. IEEE/CAA Journal of Automatica Sinica, 9(7), 1115-1138. (https://doi.org/10.1109/JAS.2022.105677)
Li, Y., Guo, Q., & Liu, J. (2019). Improved bat algorithm for vehicle routing problem. International Journal of Performability Engineering, 15(1), 317. (https://doi.org/10.23940/ijpe.19.01.p32.317325)
Liu, Z., Chen, Y., & Qin, J. (2023). The pollution-routing problem with one general period of congestion. Journal of Modelling in Management, 18(5), 1529-1560. (https://doi.org/10.1108/JM2-12-2021-0290)
Ma, X., & Liu, C. (2024). Improved ant colony algorithm for the split delivery vehicle routing problem. Applied Sciences, 14(12), 5090. (https://doi.org/10.3390/app14125090)
Machado, A. M., Mauri, G. R., Boeres, M. C. S., & de Alvarenga Rosa, R. (2021). A new hybrid matheuristic of GRASP and VNS based on constructive heuristics, set-covering and set-partitioning formulations applied to the capacitated vehicle routing problem. Expert Systems with Applications, 184, 115556. (https://doi.org/10.1016/j.eswa.2021.115556)
Mahmood, N. (2022). Solving capacitated vehicle routing problem using meerkat clan algorithm. The International Arab Journal of Information Technology, 19(4), 10-15. (https://doi.org/10.34028/iajit/19/4/14)
Manyiel, J. M. A., & Hooi, Y. K. (2021). Multi-population genetic algorithm for rich vehicle routing problems. In 2021 International Conference on Computer & Information Sciences(ICCOINS) (pp. 213-219). IEEE.
Masum, A. K. M., Shahjalal, M., Faruque, M. F., & Sarker, M. I. H. (2011). Solving the vehicle routing problem using genetic algorithm. International Journal of Advanced Computer Science and Applications, 2(7). (https://doi.org/10.14569/IJACSA.2011.020719)
Máximo, V. R., Cordeau, J. F., & Nascimento, M. C. (2024). AILS-II: An adaptive iterated local search heuristic for the large-scale capacitated vehicle routing problem. INFORMS Journal on Computing, 36(4), 974-986. (https://doi.org/10.1287/ijoc.2023.0106)
Min, J., Jin, C., & Lu, L. (2020). Improved sweep algorithm-based approach for vehicle routing problems with split delivery. In LISS2019: Proceedings of the 9th International Conference on Logistics, Informatics and Service Sciences (pp. 109-121). Springer Singapore.
Nguyen, M. A., Dang, G. T. H., Hà, M. H., & Pham, M. T. (2022). The min-cost parallel drone scheduling vehicle routing problem. European Journal of Operational Research, 299(3), 910-930. (https://doi.org/10.1016/j.ejor.2021.07.008)
Nie, Z., & Zhou, H. (2023). Euclidean capacitated vehicle routing in random setting: A 1.55-approximation algorithm. arXiv preprint arXiv:2304.11281.
Paisarnvirosrak, N., & Rungrueang, P. (2023). Firefly algorithm with Tabu search to solve the vehicle routing problem with minimized fuel emissions: Case study of canned rruits yransport. LOGI: Scientific Journal on Transport and Logistics, 14(1), 263-274. (https://doi.org/10.2478/logi-2023-0024)
Pangestu, A. D., Munib, A. A., Fitri, T. N., Oktyajati, N., & Sutopo, W. (2022). Determining the optimal route for newspaper distribution by using the sweep algorithm method (Case Study: PT Aksara Solopos). In Proceedings of the International Conference on Industrial Engineering and Operations Management (pp. 2909-2917). IEOM Society International.
Pham, Q. A., Hà, M. H., Vu, D. M., & Nguyen, H. H. (2022). A hybrid genetic algorithm for the vehicle routing problem with roaming delivery locations. In Proceedings of the International Conference on Automated Planning and Scheduling (Vol. 32, pp. 297-306).
Poonpanit, M., Punkong, N., Ratanavilisagul, C., & Kosolsombat, S. (2024). An improving genetic algorithm with local search for solving capacitated vehicle routing problem. In 2024 IEEE 9th International Conference on Computational Intelligence and Applications(ICCIA) (pp. 59-63). IEEE.
RamachandranPillai, R., & Arock, M. (2020). Spiking neural firefly optimization scheme for the capacitated dynamic vehicle routing problem with time windows. Neural Computing and Applications, 33(1), 409-432. (https://doi.org/10.1007/s00521-020-04983-8)
Ren, X., Feng, S., Wu, X., & Qi, J. (2021). Mixed-energy fleet pollution-routing problem with time windows. In 2021 IEEE International Conference on Industrial Engineering and Engineering Management(IEEM) (pp. 783-787). IEEE.
Rigakis, M., Trachanatzi, D., Marinaki, M., & Marinakis, Y. (2020). A hybrid firefly algorithm based on coordinates for the prize-collecting vehicle routing problem. In Operational Research in Agriculture and Tourism: 7th International Symposium and 29th National Conference on Operational Research, Chania, Greece, pp. 145-167. Springer International Publishing.
Sehta, N., & Thakar, U. (2021). Sweep nearest algorithm for capacitated vehicle routing problem. In 2021 IEEE 18th India Council International Conference (INDICON) (pp. 1-6). IEEE.
Shahmoradi-Moghadam, H., Samani, O., & Schönberger, J. (2020). A hybrid robust-stochastic optimization approach for the noise pollution routing problem with a heterogeneous vehicle fleet. In Dynamics in Logistics: Proceedings of the 7th International Conference LDIC 2020, Bremen, Germany (pp. 124-134). Springer International Publishing.
Shi, W., Wang, N., Zhang, M., & Jiang, B. (2023). A bi-objective pollution routing optimisation problem with decentralised cooperation and split delivery. IEEE Transactions on Intelligent Transportation Systems, 24(11), 12357-12371. (https://doi.org/10.1109/TITS.2023.3293507)
Souza, I. P., Boeres, M. C. S., & Moraes, R. E. N. (2023). A robust algorithm based on differential evolution with local search for the capacitated vehicle routing problem. Swarm and Evolutionary Computation, 77, 101245. (https://doi.org/10.1016/j.swevo.2023.101245)
Stodola, P. (2020). Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem. Natural Computing, 19(2), 463-475. (https://doi.org/10.1007/s11047-020-09783-6)
Thammano, A., & Rungwachira, P. (2021). Hybrid modified ant system with sweep algorithm and path relinking for the capacitated vehicle routing problem. Heliyon, 7(9), e08029. (https://doi.org/10.1016/j.heliyon.2021.e08029)
Utkina, I., Bukanova, O., & Batsyn, M. V. (2020). Fast heuristic for vehicle routing problem on trees. In Mathematical Optimization Theory and Operations Research: 19th International Conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020, pp. 379-386. Springer International Publishing.
Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research, 140, 105643. (https://doi.org/10.1016/j.cor.2021.105643)
Wu, Y., Du, H., & Song, H. (2024). An iterated local search heuristic for the multi-trip vehicle routing problem with multiple time windows. Mathematics, 12(11), 1712. (https://doi.org/10.3390/math12111712)
Xiao, Y., Zuo, X., Huang, J., Konak, A., & Xu, Y. (2020). The continuous pollution routing problem. Applied Mathematics and Computation, 387, 125072. (https://doi.org/10.1016/j.amc.2020.125072)
Yang, X. S. (2010). Nature-inspired Metaheuristic Algorithms. Second Edition, Luniver press, University of Cambridge, United Kingdom. (https://staff.fmi.uvt.ro/~daniela.zaharie/ma2016/projects/techniques/FireflyAlgorithm/Yang_nature_book_part.pdf)
Yelmewad, P., & Talawar, B. (2021). Parallel version of local search heuristic algorithm to solve capacitated vehicle routing problem. Cluster Computing, 24, 3671-3692. (https://doi.org/10.1007/s10586-021-03354-9)
Zhao, J., Mao, M., Zhao, X., & Zou, J. (2020). A hybrid of deep reinforcement learning and local search for the vehicle routing problems. IEEE Transactions on Intelligent Transportation Systems, 22(11), 7208-7218. (https://doi.org/10.1109/TITS.2020.3003163)
Zhou, Q., & Wu, Z. (2023). A green vehicle routing problem with pick-up and delivery based on an improved firefly algorithm. In Fourth International Conference on Computer Science and Communication Technology (ICCSCT 2023) (Vol. 12918, pp. 65-72). SPIE.