Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

Algorithmic Handling of Time Expanded Networks

, ,

DOI: http://dx.doi.org/10.15439/2023F6717

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 667–676 ()

Full text

Abstract. 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.

References

  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