J Shanghai Jiaotong Univ Sci

Journal of Shanghai Jiaotong University(Science) >

2026 , Vol. 31 >Issue 2: 440 - 457

DOI: https://doi.org/10.1007/s12204-024-2719-y

Automation & Computer Technologies

Hybrid Meta-Heuristic Algorithm for a Pickup and Delivery Problem of Ship Outfitting Pallets Distribution Considering Carbon Emissions

Expand
  • School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Received date: 2023-07-04

  Accepted date: 2023-08-15

  Online published: 2024-04-03

Fold

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.

Cite this article

Liu Ziyan, Jiang Zuhua . Hybrid Meta-Heuristic Algorithm for a Pickup and Delivery Problem of Ship Outfitting Pallets Distribution Considering Carbon Emissions[J]. Journal of Shanghai Jiaotong University(Science), 2026 , 31(2) : 440 -457 . DOI: 10.1007/s12204-024-2719-y

References

[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 CO2 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.


Options
Outlines

/

〈 〉