Algorithmic Handling of Time Expanded Networks

• Autorzy: Quilliot Alain , Figueroa Jose-Luis , Toussaint Hélène , Wagler Annegret

Identyfikatory

DOI

10.15439/2023F6717

• Języki publikacji: EN

Abstrakty

EN

Time Expanded Networks, built by considering the nodes of a base network over some time space, are powerful tools for the formulation of problems involving synchronization mechanisms. Those mechanisms may for instance be related to the interaction between resource production and consumption or between routing and scheduling. Still, in most cases, deriving algorithms from those formulations is difficult, due to both the size of resulting network structure and the fact that reducing this size through rounding techniques tends to induce uncontrolled essor propagation. We address here this algorithmic issue, while proposing a generic decomposition scheme which works by first skipping the temporal dimension of the problem and next expanding resulitng projected solution into a full solution of the problem set on the time expanded network.

Słowa kluczowe

EN

coupling; computer science; uncertainty; production; routing; robustness; synchronization

PL

sprzężenie; informatyka; niepewność; produkcja; trasowanie; solidność; synchronizacja

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 667--676
• Opis fizyczny: Bibliogr. 21 poz., il.

Twórcy

autor

Quilliot Alain

• LIMOS Lab. UCA, CNRS and EMSE Clermont-Ferrand, France

autor

Figueroa Jose-Luis

• LIMOS Lab. UCA, CNRS and EMSE Clermont-Ferrand, France

autor

Toussaint Hélène

• LIMOS Lab. Clermont-Ferrand, France

autor

Wagler Annegret

• LIMOS Lab. Clermont-Ferrand, France

Bibliografia

• 1. R. K. Ahuja, T. L. Magnanti, J. B. Orlin, M. R.Reddy, Applications of network optimization, Chapter 1 of Network Models, Handbook of Operation Research and Management Science 7, pp. 1-83, 1995. doi.org/10.1016/S0927-0507(05)80118-5
• 2. J. Aronson, A survey of dynamic network flows, Ann. Oper. Res. 20, pp. 1-66, 1989. doi.org/10.1007/BF02216922
• 3. C. Artigues, E. Hébrard, A. Quilliot, H. Toussaint, Models and algorithms for natural disaster evacuation problems, Proc. 2019 FEDCSIS WCO Conf., p 143-146, 2019. doi.org/10.15439/2019F90
• 4. R. Bellman, On a routing problem, Quarterly of Applied Mathematics, 16, p 87-90, 1958.
• 5. F. Bendali, J. Mailfert, E. Mole-Kamga, A. Quilliot, H. Toussaint, Pipelining dynamic programming process in order to synchronize energy production and consumption, Proc. 2020 FEDCSIS WCO Conf., p 303-306, 2020. doi.org/10.15439/978-83-955416-7-4.
• 6. F. Bendali, J. Mailfert,and A. Quilliot, Flots entiers et multi-flots fractionnaires couplés par une contrainte de capacité, Investigacion Operativa, 9, 2001. DOI : 10.1051/ro:2006003
• 7. S. Bsaybes, A. Quilliot, A. Wagler, Fleet management for autonomous vehicles using flows in time-expanded networks, TOP, Springer Verlag 27 (2), pp. 288-311, 2019. http://dx.doi.org/10.1007/s11750-019-00506-4
• 8. D. Chemla, F. Meunier,Bike sharing systems: the static rebalanc- ing problem, Discrete Optimization 10 (2), p 120-146, 2013. doi.org/10.1016/j.disopt.2012.11.005
• 9. A. O.Fleischer, M. Skutella, Quickest flows over time, SIAM Journal of Computing 36 (6), p 1600-1630, 2007. doi.org/10.1137/S0097539703427215
• 10. S. Fidanova, O. Roeva, M. Ganzha, Ant colony optimization algorithm for fuzzy transport modelling, Proc. 2020 FEDCSIS WCO Conference, p 237-240, 2020. doi.org/10.15439/978-83-955416-7-4
• 11. R. Ford and D. Fulkerson, Flows in networks, Princeton University Press, 1962.
• 12. J. L.Gonzalez, M. Baiou,A. Quilliot, H. Toussaint, A. Wagler,Branch and cut for a two commodity flow relocation model with time constraints, Combinatorial Optimization. ISCO 2022. LNCS 13526. Springer, Cham. 2022. doi.org/10.1007/978-3-031-18530-4-2
• 13. M. S.Hall and S. Hippler, Multi-commodity flows over time, Theoretical Computer Sciences, p 58-84, 2007.
• 14. N. Kyngas, K. Nurmi, The extended shift minimization personnel task scheduling problem, Annals of Computer Sciences and Information Systems 26, p 65-74, 2021. doi.org/10.15439/978-83-959183-9-1
• 15. K. Kishkin, D. Arnaudov, V. Todorov, S. Fidanova, Multicriterial evaluation and optimization of an algorithm for charging energy storage elements, Annals of Computer Sciences and Information Systems 26, p 61-64, 2021. doi.org/10.15439/978-83-959183-9-1
• 16. W. B.Powell and P. Jaillet, Stochastic and dynamic networks and network routing, Handbook Operations Research, North Holland, 1995.
• 17. F. T.Raviv and M. Tzur, Static repositionning in a bike sharing system: models and solution approaches, EURO Journal of Transportation and Logistics 2, p 187-229, 2013. DOI 10.1007/s13676-012-0017-6
• 18. J. Schuijbroek, R. C. Hampshire, W. Van Hoeve, Inventory rebalancing and vehicle routing in bike sharing systems, EJOR 257 (3), (2017). doi.org/10.1016/j.ejor.2016.08.029
• 19. K. Stoilova, T. Stoilov, Bi-level optimization application for urban traffic management, Proc. 2020 FEDCSIS WCO Conf., p 327-336, 2020. doi.org/10.15439/978-83-949419-5-6
• 20. S. Varone, D. Schindl, C. Beffa, Flexible job shop scheduling problemm with sequance-dependent transportation constraints and setup times, Annals of Computer Sciences and Information Systems 26, p 97-102, 2021. doi.org/10.15439/978-83-959183-9-1
• 21. Q. P. Zheng, A. Arulselvan, Discrete time dynamic traffic assignment models and solution algorithms for managing lanes, Journal of Global Optimization 51, p 47-68, 2011. doi.org/10.1007/s10898-010-9618-5

Uwagi

1. Present work was funded by French ANR: National Agency for Research, Labex IMOBS3, and PGMO Program.

2. Thematic Tracks Regular Papers

3. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).