考虑碳排放的船舶舾装托盘配送路径优化方法研究

doi:10.1007/s12204-024-2719-y

摘要/Abstract

摘要： 船舶舾装托盘配送产生的碳排放在造船物流中占很大比例。然而，由于问题规模大、约束复杂，且人工路径规划无法考虑碳排放目标，舾装托盘配送效率和绿色化程度较低。针对该问题背景，本文建立了异质车辆多拾取点绿色取送货问题的混合整数线性规划模型，同时考虑了经济成本与排放成本，以满足绿色物流的要求。提出了一种混合元启发式优化算法求解该问题，并根据问题特点设计了针对性的剪枝策略以提高求解效率。不同规模实例的数值实验结果证明了提出的混合优化算法具有求解性能优势。基于求解结果分析了经济成本目标模型和排放成本目标模型之间的成本构成和运输策略差异。本文还量化分析了异质车辆相比于同质车辆的优势，以及经济成本与排放成本之间的权衡关系。提出的方法可以在提高船舶舾装托盘配送效率的同时降低配送所产生的碳排放，有助于造船业的可持续发展。

关键词: 舾装托盘配送, 多拾取点取送货问题, 异质车辆, 碳排放, 自适应大规模邻域搜索

Abstract: Carbon emissions from ship outfitting pallet distribution account for a significant proportion of shipbuilding logistics. However, the complexity of the problem and the lack of carbon emission considerations make it difficult to achieve efficient and low-carbon distribution scheduling. To improve distribution efficiency while reducing carbon emissions, this paper formulates it as a heterogeneous fleet green multi-pickup and delivery problem with time windows. To effectively solve the problem, we develop a powerful hybrid meta-heuristic and propose a request insertion pruning strategy to accelerate the procedure. Computational results on multiple instances demonstrate the significant advantages of the proposed hybrid approach. The differences in cost components and transportation strategies between the economic and emission cost objective models are analyzed to provide meaningful managerial insights. This paper also quantifies the trade-offs between two costs and the benefits of a heterogeneous fleet over a homogeneous one. The method proposed can effectively reduce carbon emissions while improving distribution efficiency to help improve the sustainability of shipbuilding.

中图分类号:

TP391

. 考虑碳排放的船舶舾装托盘配送路径优化方法研究[J]. J Shanghai Jiaotong Univ Sci, 2026, 31(2): 440-457.

Liu Ziyan, Jiang Zuhua. Hybrid Meta-Heuristic Algorithm for a Pickup and Delivery Problem of Ship Outfitting Pallets Distribution Considering Carbon Emissions[J]. J Shanghai Jiaotong Univ Sci, 2026, 31(2): 440-457.

参考文献

[1] WADA Y, YAMAMURA T, HAMADA K, et al. Evaluation of GHG emission measures based on shipping and shipbuilding market forecasting [J]. Sustainability, 2021, 13(5): 2760.

[2] KLUSCHKE P, GNANN T, PLÖTZ P, et al. Market diffusion of alternative fuels and powertrains in heavy-duty vehicles: A literature review [J]. Energy Reports, 2019, 5: 1010-1024.

[3] LEE S, NOH D W, OH D H. Characterizing the difference between indirect and direct CO₂ emissions: Evidence from Korean manufacturing industries, 2004–2010 [J]. Sustainability, 2018, 10(8): 2711.

[4] LIU H W, YANG R L, WU D D, et al. Green productivity growth and competition analysis of road transportation at the provincial level employing Global Malmquist-Luenberger Index approach [J]. Journal of Cleaner Production, 2021, 279: 123677.

[5] YE C, HE W J, CHEN H Q. Electric vehicle routing models and solution algorithms in logistics distribution: A systematic review [J]. Environmental Science and Pollution Research, 2022, 29(38): 57067-57090.

[6] CHEN Y N, JIANG Z H. Multi-AGVs scheduling with vehicle conflict consideration in ship outfitting items warehouse [J]. Journal of Shanghai Jiao Tong University (Science), 2022. https://doi.org/10.1007/s12204-022-2561-z

[7] NACCACHE S, CÔTÉ J F, COELHO L C. The multi-pickup and delivery problem with time windows [J]. European Journal of Operational Research, 2018, 269(1): 353-362.

[8] ESKANDARPOUR M, OUELHADJ D, HATAMI S, et al. Enhanced multi-directional local search for the bi-objective heterogeneous vehicle routing problem with multiple driving ranges [J]. European Journal of Operational Research, 2019, 277(2): 479-491.

[9] ASGHARI M, MIRZAPOUR AL-E-HASHEM S M J. A green delivery-pickup problem for home hemodialysis machines; sharing economy in distributing scarce resources [J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 134: 101815.

[10] KARAKOSTAS P, SIFALERAS A, GEORGIADIS M C. Adaptive variable neighborhood search solution methods for the fleet size and mix pollution location-inventory-routing problem [J]. Expert Systems with Applications, 2020, 153: 113444.

[11] TAN Y Y, DENG L, LI L X, et al. The capacitated pollution routing problem with pickup and delivery in the last mile [J]. Asia Pacific Journal of Marketing and Logistics, 2019, 31(4): 1193-1215.

[12] KOÇ Ç, BEKTAŞ T, JABALI O, et al. The fleet size and mix pollution-routing problem [J]. Transportation Research Part B: Methodological, 2014, 70: 239-254.

[13] WANG J G, FAN X M, ZHU Y, et al. Cross-platform AR annotation for assembly-design communication in pipe outfitting [J]. The International Journal of Advanced Manufacturing Technology, 2022, 121(7): 4981-4998.

[14] WU D, YANG R, MA D, et al. Integrated Virtual Assembly Environment and its application in ship piping layout [J]. International Journal of Production Research, 2008, 46(17): 4729-4749.

[15] CHEN J. The study of modern outfitting process based on lean shipbuilding[D]. Shanghai: Shanghai Jiao Tong University, 2011 (in Chinese).

[16] WANG Q. The optimal management research about centralized configuration of outfitting trays[D]. Zhenjiang: Jiangsu University of Science and Technology, 2012 (in Chinese).

[17] CAO W. Research on ship pre-outfitting material batching and delivery in shipyards[D]. Harbin: Harbin Engineering University, 2020 (in Chinese).

[18] DUMAS Y, DESROSIERS J, SOUMIS F. The pickup and delivery problem with time windows [J]. European Journal of Operational Research, 1991, 54(1): 7-22.

[19] BERBEGLIA G, CORDEAU J F, GRIBKOVSKAIA I, et al. Static pickup and delivery problems: A classification scheme and survey [J]. TOP, 2007, 15(1): 1-31.

[20] HO S C, SZETO W Y. GRASP with path relinking for the selective pickup and delivery problem [J]. Expert Systems with Applications, 2016, 51: 14-25.

[21] ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows [J]. Transportation Science, 2006, 40(4): 455-472.

[22] GOKSAL F P, KARAOGLAN I, ALTIPARMAK F. A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery [J]. Computers and Industrial Engineering, 2013, 65(1): 39-53.

[23] CURTOIS T, LANDA-SILVA D, QU Y, et al. Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows [J]. EURO Journal on Transportation and Logistics, 2018, 7(2): 151-192.

[24] FU Z X, CHOW J Y J. The pickup and delivery problem with synchronized en-route transfers for microtransit planning [J]. Transportation Research Part E: Logistics and Transportation Review, 2022, 157: 102562.

[25] WANG Y, PENG S G, GUAN X Y, et al. Collaborative logistics pickup and delivery problem with eco-packages based on time–space network [J]. Expert Systems with Applications, 2021, 170: 114561.

[26] AZIEZ I, CÔTÉ J F, COELHO L C. Exact algorithms for the multi-pickup and delivery problem with time windows [J]. European Journal of Operational Research, 2020, 284(3): 906-919.

[27] KOHAR A, JAKHAR S K. A capacitated multi pickup online food delivery problem with time windows: A branch-and-cut algorithm [J]. Annals of Operations Research, 2021. https://doi.org/10.1007/s10479-021-04145-6

[28] ASGHARI M, MIRZAPOUR AL-E-HASHEM S M J. Green vehicle routing problem: A state-of-the-art review [J]. International Journal of Production Economics, 2021, 231: 107899.

[29] BEKTAŞ T, LAPORTE G. The pollution-routing problem [J]. Transportation Research Part B: Methodological, 2011, 45(8): 1232-1250.

[30] JABIR E, PANICKER V V, SRIDHARAN R. Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem [J]. Transportation Research Part D: Transport and Environment, 2017, 57: 422-457.

[31] JIANG Z H, CHEN Y N, LI X Y, et al. A heuristic optimization approach for multi-vehicle and one-cargo green transportation scheduling in shipbuilding [J]. Advanced Engineering Informatics, 2021, 49: 101306.

[32] WANG Y, ASSOGBA K, FAN J X, et al. Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost [J]. Journal of Cleaner Production, 2019, 232: 12-29.

[33] LU X L, PU X J, WANG H F, et al. Dual-objective modeling and optimization of a low-carbon waste-classified collection problem [J]. Environmental Science and Pollution Research, 2023, 30(12): 35076-35095.

[34] SOYSAL M, ÇIMEN M, BELBAĞ S. Pickup and delivery with electric vehicles under stochastic battery depletion [J]. Computers & Industrial Engineering, 2020, 146: 106512.

[35] GOEKE D. Granular tabu search for the pickup and delivery problem with time windows and electric vehicles [J]. European Journal of Operational Research, 2019, 278(3): 821-836.

[36] SOYSAL M, ÇIMEN M, DEMIR E. On the mathematical modeling of green one-to-one pickup and delivery problem with road segmentation [J]. Journal of Cleaner Production, 2018, 174: 1664-1678.

[37] YU Y, WU Y T, WANG J W. Bi-objective green ride-sharing problem: Model and exact method [J]. International Journal of Production Economics, 2019, 208: 472-482.

[38] ABDI A, ABDI A, AKBARPOUR N, et al. Innovative approaches to design and address green supply chain network with simultaneous pick-up and split delivery [J]. Journal of Cleaner Production, 2020, 250: 119437.

[39] ZARRAT DAKHELY PARAST Z, HALEH H, AVAKH DARESTANI S, et al. Green reverse supply chain network design considering location-routing-inventory decisions with simultaneous pickup and delivery [J]. Environmental Science and Pollution Research International, 2021. https://doi.org/10.1007/s11356-021-13770-4

[40] YU S H, PUCHINGER J, SUN S D. Van-based robot hybrid pickup and delivery routing problem [J]. European Journal of Operational Research, 2022, 298(3): 894-914.

[41] TEKIL-ERGÜN S, PESCH E, KUZMICZ K A. Solving a hybrid mixed fleet heterogeneous dial-a-ride problem in delay-sensitive container transportation [J]. International Journal of Production Research, 2022, 60(1): 297-323.

[42] SUN W, YU Y, WANG J W. Heterogeneous vehicle pickup and delivery problems: Formulation and exact solution [J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 125: 181-202.

[43] GOLDEN B, ASSAD A, LEVY L, et al. The fleet size and mix vehicle routing problem [J]. Computers & Operations Research, 1984, 11(1): 49-66.

[44] DRAGOMIR A G, VAN WOENSEL T, DOERNER K F. The pickup and delivery problem with alternative locations and overlapping time windows [J]. Computers & Operations Research, 2022, 143: 105758.

[45] DEMIR E, BEKTAŞ T, LAPORTE G. A review of recent research on green road freight transportation [J]. European Journal of Operational Research, 2014, 237(3): 775-793.

[46] DEMIR E, BEKTAŞ T, LAPORTE G. A comparative analysis of several vehicle emission models for road freight transportation [J]. Transportation Research Part D: Transport and Environment, 2011, 16(5): 347-357.

[47] BARTH M, BORIBOONSOMSIN K. Energy and emissions impacts of a freeway-based dynamic eco-driving system [J]. Transportation Research Part D: Transport and Environment, 2009, 14(6): 400-410.

[48] ASHTINEH H, PISHVAEE M S. Alternative fuel vehicle-routing problem: A life cycle analysis of transportation fuels [J]. Journal of Cleaner Production, 2019, 219: 166-182.

[49] SALEHI M, JALALIAN M, VALI SIAR M M. Green transportation scheduling with speed control: Trade-off between total transportation cost and carbon emission [J]. Computers & Industrial Engineering, 2017, 113: 392-404.

[50] KOÇ Ç, BEKTAŞ T, JABALI O, et al. A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows [J]. Computers and Operations Research, 2015, 64: 11-27.

[51] BALINSKI M L, QUANDT R E. On an integer program for a delivery problem [J]. Operations Research, 1964, 12(2): 300-304.

[52] MARSTEN R E. An algorithm for large set partitioning problems [J]. Management Science, 1974, 20(5): 774-787.

[53] DEMIR E, BEKTAŞ T, LAPORTE G. An adaptive large neighborhood search heuristic for the Pollution-Routing Problem [J]. European Journal of Operational Research, 2012, 223(2): 346-359.

[54] DETTI P, PAPALINI F, DE LARA G Z M. A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare [J]. Omega, 2017, 70: 1-14.

[55] BRAEKERS K, CARIS A, JANSSENS G K. Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots [J]. Transportation Research Part B: Methodological, 2014, 67: 166-186.

[56] PARRAGH S N, DOERNER K F, HARTL R F. Variable neighborhood search for the dial-a-ride problem [J]. Computers and Operations Research, 2010, 37(6): 1129-1138.