This paper addresses a routing and scheduling problem from two different perspectives: economic and environmental. From economic perspective, we aim to optimize the vehicle routing plan to reduce the operating cost, but from environmental perspective, we aim to optimize the vehicle routing and speed decisions to reduce the carbon emissions. This research can provide two different decision plans under these two different perspectives, and the comparison of the results from the two different perspectives will be very meaningful and helpful to the logistics decision-makers. We formulate the problem using two mixed-integer programming (MIP) models with different objectives. However, this problem is very challenging, with medium-sized instances already difficult for the MIP solver. In order to solve it with larger scale instances, we propose an exact branch-and-price (BAP) algorithm. The BAP algorithm relies on efficiently solving the pricing sub-problem with different objectives. We design two different tailored labeling algorithms to solve it. Extensive computational experiments demonstrate the effectiveness of the proposed BAP algorithm, comparing with the MIP formulation solved by CPLEX with a time limit of 2 h.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2022147
Keywords: Routing and scheduling, carbon emissions, branch-and-price, mixed-integer programming
@article{RO_2022__56_5_3267_0,
author = {Luo, Hongyuan and Dridi, Mahjoub and Grunder, Olivier},
title = {A branch-and-price algorithm for a routing and scheduling problem from economic and environmental perspectives},
journal = {RAIRO. Operations Research},
pages = {3267--3292},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {5},
doi = {10.1051/ro/2022147},
mrnumber = {4481130},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022147/}
}
TY - JOUR AU - Luo, Hongyuan AU - Dridi, Mahjoub AU - Grunder, Olivier TI - A branch-and-price algorithm for a routing and scheduling problem from economic and environmental perspectives JO - RAIRO. Operations Research PY - 2022 SP - 3267 EP - 3292 VL - 56 IS - 5 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022147/ DO - 10.1051/ro/2022147 LA - en ID - RO_2022__56_5_3267_0 ER -
%0 Journal Article %A Luo, Hongyuan %A Dridi, Mahjoub %A Grunder, Olivier %T A branch-and-price algorithm for a routing and scheduling problem from economic and environmental perspectives %J RAIRO. Operations Research %D 2022 %P 3267-3292 %V 56 %N 5 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022147/ %R 10.1051/ro/2022147 %G en %F RO_2022__56_5_3267_0
Luo, Hongyuan; Dridi, Mahjoub; Grunder, Olivier. A branch-and-price algorithm for a routing and scheduling problem from economic and environmental perspectives. RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3267-3292. doi: 10.1051/ro/2022147
[1] and , The pollution-routing problem. Transp. Res. Part B: Methodol. 45 (2011) 1232–1250. | DOI
[2] , , and , Total carbon emissions minimization in connected and automated vehicle routing problem with speed variables. Expert Syst. App. 165 (2021) 113910. | DOI
[3] , and , A branch-and-price method for the vehicle allocation problem. Comput. Ind. Eng. 149 (2020) 106745. | DOI
[4] , , and , Branch and price for the time-dependent vehicle routing problem with time windows. Transp. Sci. 47 (2013) 380–396. | DOI
[5] , and , An exact approach for a variant of the pollution-routing problem. Transp. Sci. 51 (2017) 607–628. | DOI
[6] , and , An adaptive large neighborhood search heuristic for the pollution-routing problem. Eur. J. Oper. Res. 223 (2012) 346–359. | MR | Zbl | DOI
[7] , and , Column Generation. Vol. 5. Springer Science & Business Media (2006). | MR
[8] and , A green vehicle routing problem. Transp. Res. Part E: Logistics Transp. Rev. 48 (2012) 100–114. | DOI
[9] , and , A bi-objective green home health care routing problem. J. Cleaner Prod. 200 (2018) 423–443. | DOI
[10] , , and , A green home health care supply chain: new modified simulated annealing algorithms. J. Cleaner Prod. 240 (2019) 118200. | DOI
[11] , A tutorial on column generation and branch-and-price for vehicle routing problems. 4or 8 (2010) 407–424. | MR | Zbl | DOI
[12] , and , A branch-and-price algorithm for a compressor scheduling problem. Comput. Ind. Eng. 116 (2018) 72–81. | DOI
[13] , and , Time-dependent routing problems: a review. Comput. Oper. Res. 64 (2015) 189–197. | MR | Zbl | DOI
[14] and , A branch and price approach to the two-agent integrated production and distribution scheduling. Comput. Ind. Eng. 136 (2019) 504–515. | DOI
[15] , , , and , Methodology for calculating transport emissions and energy consumption (1999).
[16] , and , Analysis of travel times and CO2 emissions in time-dependent vehicle routing. Prod. Oper. Manage. 21 (2012) 1060–1074. | DOI
[17] , , and , Greenhouse impact due to the use of combustible fuels: life cycle viewpoint and relative radiative forcing commitment. Environ. Manage. 42 (2008) 458. | DOI
[18] , and , Heterogeneous fixed fleet vehicle routing considering carbon emission. Transp. Res. Part D: Transp. Environ. 23 (2013) 81–89. | DOI
[19] , , , and , Survey of green vehicle routing problem: past and future trends. Expert Syst. App. 41 (2014) 1118–1138. | DOI
[20] and , A constraint relaxation-based algorithm for the load-dependent vehicle routing problem with time windows. Flexible Serv. Manuf. J. 31 (2019) 331–353. | DOI
[21] , and , Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints. Eur. J. Oper. Res. 234 (2014) 49–60. | MR | Zbl | DOI
[22] , and , An ACO-based heuristic approach for a route and speed optimization problem in home health care with synchronized visits and carbon emissions. Soft Comput. 25 (2021) 14673–14696. | DOI
[23] , , and , Modeling the interrelationships among barriers to sustainable supply chain management in leather industry. J. Cleaner Prod. 181 (2018) 631–651. | DOI
[24] and , Finding least fuel emission paths in a network with time-varying speeds. Networks 63 (2014) 96–106. | MR | Zbl | DOI
[25] and , Fuel emissions optimization in vehicle routing problems with time-varying speeds. Eur. J. Oper. Res. 248 (2016) 840–848. | MR | Zbl | DOI
[26] and , A branch-and-price algorithm for a vehicle routing with demand allocation problem. Eur. J. Oper. Res. 272 (2) 2019 523–538. | MR | Zbl | DOI
[27] and , Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3 (2006) 255–273. | MR | Zbl | DOI
[28] , and , A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert Syst. App. 72 (2017) 160–176. | DOI
[29] , and , A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times. Transp. Res. Part E: Logistics Transp. Rev. 128 (2019) 52–95. | DOI
[30] , Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35 (1987) 254–265. | MR | Zbl | DOI
[31] , , and , A robust optimization approach for pollution routing problem with pickup and delivery under uncertainty. J. Manuf. Syst. 33 (2014) 277–286. | DOI
[32] , and , Data driven safe vehicle routing analytics: a differential evolution algorithm to reduce CO2 emissions and hazardous risks. Ann. Oper. Res. 270 (2018) 515–538. | MR | Zbl | DOI
[33] , and , A branch-and-price algorithm for a green location routing problem with multi-type charging infrastructure. Transp. Res. Part E: Logistics Transp. Rev. 156 (2021) 102529. | DOI
[34] , , and , A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows. Transp. Res. Part B: Methodol. 122 (2019) 511–527. | DOI
Cité par Sources :
