The emergence of locally produced renewable energies induces the appearance of a new generation of local energy players, which are at the same time producers and consumers. In case of time dependent solar energy production, it raises the question of synchronizing production and consumption. We deal here with this issue, in the context of an experimental Solar Hydrogen (H2) production platform. More precisely, we try here to simultaneously schedule a H2 fueled vehicle which follows a pre-computed route while being compelled to periodically refuel, and the H2 production micro-plant which is required to produce related energy under time dependent production costs and productivity rates, both processes being subject to storage capacity constraints. In order to do it, we design a global dynamic programming (DP) algorithm for the resulting NP-Hard problem. This DP algorithm involves a 2D time space which links energy consumption by the vehicle and its production by the micro-plant. Since the number of states induced by this DP algorithm becomes an issue as soon as the size of the problem increases, we first propose a theoretical Polynomial Time Approximation Scheme (PTAS), next design several practical pruning devices and finally perform numerical tests in order to check their efficiency.
Keywords: Scheduling, dynamic programming, energy
@article{RO_2021__55_4_2141_0,
author = {Bendali, Fatiha and Mole Kamga, Eloise and Mailfert, Jean and Quilliot, Alain and Toussaint, H\'el\`ene},
title = {Synchronizing energy production and vehicle routing},
journal = {RAIRO. Operations Research},
pages = {2141--2163},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {4},
doi = {10.1051/ro/2021093},
mrnumber = {4282588},
zbl = {1468.90007},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021093/}
}
TY - JOUR AU - Bendali, Fatiha AU - Mole Kamga, Eloise AU - Mailfert, Jean AU - Quilliot, Alain AU - Toussaint, Hélène TI - Synchronizing energy production and vehicle routing JO - RAIRO. Operations Research PY - 2021 SP - 2141 EP - 2163 VL - 55 IS - 4 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021093/ DO - 10.1051/ro/2021093 LA - en ID - RO_2021__55_4_2141_0 ER -
%0 Journal Article %A Bendali, Fatiha %A Mole Kamga, Eloise %A Mailfert, Jean %A Quilliot, Alain %A Toussaint, Hélène %T Synchronizing energy production and vehicle routing %J RAIRO. Operations Research %D 2021 %P 2141-2163 %V 55 %N 4 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021093/ %R 10.1051/ro/2021093 %G en %F RO_2021__55_4_2141_0
Bendali, Fatiha; Mole Kamga, Eloise; Mailfert, Jean; Quilliot, Alain; Toussaint, Hélène. Synchronizing energy production and vehicle routing. RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2141-2163. doi: 10.1051/ro/2021093
[1] , Energy-efficient algorithms. Commun. ACM 53 (2010) 86–96. | DOI
[2] , and , Low complexity scheduling algorithms minimizing the energy for tasks with agreeable deadlines. Disc. Appl. Math. 175 (2014) 1–10. | MR | Zbl | DOI
[3] , Scheduing unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. In: Proceedings of the 17th Annual ACM-SIMA Symposium on Discrete Algorithms (2006) 364–367. | MR | Zbl
[4] , and , Modèles et Algorithmes en Ordonnancement; Ed Ellipses (2004) 198–203.
[5] , and , A survey of design techniques for system level dynamic power management. IEEE Trans. Very Large Scale Integr. Syst. 8 (2000) 299–316. | DOI
[6] , Batteries and ultracapacitors for electric, hybrid, and fuel cell vehicles. Proc. IEEE 95 (2007) 806–820. | DOI
[7] , The state of the art of electric, hybrid, and fuel cell vehicles. Proc. IEEE 95 (2007) 704–718. | DOI
[8] and , Homogeneous non idling schedules of unit-time jobs on identical parallel machines. Disc. Appl. Math. 161 (2013) 1586–1597. | MR | Zbl | DOI
[9] and , A polynomial algorithm for the homogeneous non idling scheduling problem of unit-time independent jobs on identical parallel machines. Disc. Appl. Math. 243 (2018) 132–139. | MR | Zbl | DOI
[10] , and , Anchored reactive and proactive solutions to the CPM-scheduling problem. Eur. J. Oper. Res. 261 (2017) 67–74. | MR | Zbl | DOI
[11] , and , Scheduling to minimize gaps and power consumption. SPAA (2007) 46–54.
[12] , Synchronization in vehicle routing – a survey of VRPs with multiple synchronization constraints. Transp. Sci. 46 (2012) 297–316. | DOI
[13] and , A green vehicle routing problem. Transp. Res. Part E: Logist. Transp. Rev. 109 (2012) 100–114. | DOI
[14] , , , , and , A metaheuristic for the time dependent pollution-routing problem. Eur. J. Oper. Res. 259 (2017) 972–991. | MR | Zbl | DOI
[15] , and , Light, Water, Hydrogen: The Solargeneration of Hydrogen by Water Photoelectrolysis. Springer-Verlag, US (2008). | DOI
[16] and , Algorithms for power management. SIGACT News 36 (2003) 63–76. | DOI
[17] , and , Energy minimizing vehicle routing problem, edited by , and . In: Combinatorial Optimization and Applications. Berlin, Heidelberg (2007) 62–71. | MR | Zbl | DOI
[18] , , and , The electric vehicle routing problem with shared charging stations. Int. Trans. Oper. Res. 26 (2019) 1211–1243. | MR | Zbl | DOI
[19] , Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Comput. Ind. Eng. 59 (2010) 157–165. | DOI
[20] , Energy consumption and cost-benefit analysis of hybrid and electric city buses. Transp. Res. Part C: Emerg. Technol. 38 (2014) 1–15. | DOI
[21] , Thermochemical and Thermal/Photo Hybrid Solar Water Splitting. Springer New York, New York, NY (2008).
[22] , , , and , Survey of green vehicle routing problem: past and future trends. Expert Syst. App. 41 (2014) 1118–1138. | DOI
[23] and , On an exact method for the constrained shortest path problem. Comput. Oper. Res. 40 (2013) 378–384. | Zbl | DOI
[24] and , Smart production scheduling with time-dependent and machine-dependent electricity cost by considering distributed energy resources and energy storage. Int. J. Prod. Res. 52 (2014) 3922–3939. | DOI
[25] , and , Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency. Int. J. Adv. Manuf. Technol. 68 (2013) 523–535. | DOI
[26] , , and , Production scheduling with a piecewise-linear energy cost function (2016) 1–8.
[27] and , Optimizing energy costs by intelligent production scheduling, edited by and . In: Glocalized Solutions for Sustainability in Manufacturing. Berlin, Heidelberg (2011) 293–298. | DOI
[28] , , and , Green vehicle routing and scheduling problem with split delivery. Electron. Notes Disc. Math. 69 (2018) 13–20. Joint, EURO/ALIO, International Conference 2018 on Applied Combinatorial Optimization (EURO/ALIO 2018). | DOI
[29] , , and , Efficient energy-optimal routing for electric vehicles. In: AAAI (2011).
[30] , and , The electric vehicle-routing problem with time windows and recharging stations. Transp. Sci. 48 (2014) 500–520. | DOI
[31] , , , , and , Plug-in hybrid electric vehicles and smart grid: investigations based on a micro simulation. Transp. Res. Part C: Emerg. Technol. 28 (2014) 74–86. | DOI
Cité par Sources :
