Director de proiect: Conf. dr. ing. Guillaume DUCOFFE – CS

Obiectivul general al proiectului

Principalul obiectiv al proiectului îl reprezintă dezvoltarea (și testarea) unui prototip pentru problemele de amplasare a unor instalații strategice de tip școală sau spital.

Descriere proiect

Guvernul României și-a propus un program ambițios despre infrastructurile naționale, precum și o dezvoltare a autostrăzilor și construirea unor instalații strategice de tip școală sau spital. Totodată, reușita acestui program presupune rezolvarea unor probleme dificile de amplasare. Ne propunem să dezvoltăm (și să testăm) un prototip complet funcțional pentru problemele de amplasare a unor instalații. Acest prototip ar avea la bază câteva algoritmi recenți pe care i-am obținut în cadrul activităților noastre de cercetare fundamentală. Intenționăm să exploatăm unele proprietăți specifice ale rețelelor de infrastructuri din România pentru a crește eficacitatea produsului nostru. Totodată, abordarea noastră stă la un nivel suficient de general pentru a se potrivi în mai multe contexte, nu numai în cadrul amplasarii unor instalații publice.

Rezultate estimate

• realizarea unui software nou, cu denumirea FLIPS, pentru problemele de amplasare a unor instalații în București și în țară.

Rezultate obținute

Etapa 1/2022, denumită Crearea unei baze de date și a unor instrumente de analiză pentru studii despre amplasarea unor instalații din România, a fost compusă din patru activități principale:

• Activitatea 1.1, intitulată Crearea unei Baze de date pentru studii despre amplasarea unor instalații în România, a avut ca rezultat o bază de date, sub forma mai multor fișiere (în format MS Excel), cu informațiile despre mijloacele de transport, amplasarea unor instalații de tip școală sau spital, și densitatea populației, în București și (parțial) în alte orașe mari din România.
• Activitatea 1.2, intitulată Studiu aprofundat al literaturii de specialitate privind software-urile de pe piață pentru unele probleme privind amplasarea unei instalații, a avut ca rezultat un studiu comparativ dintre soluțiile existente pe piață pentru rezolvarea problemelor liniare. S-a realizat și un studiu comparativ al performanțelor obținute pentru metodele de rezolvare de tip SAT, respectiv programare liniară, aplicate la problemele de amplasare a unor instalații.
• Activitatea 1.3, intitulată Implementarea unor algoritmi pentru grafuri pentru unele probleme privind analiza avansată a rețelelor, a avut ca rezultate implementarea și testarea multor algoritmi pentru detectarea diverselor proprietăți ale grafurilor (ex., numărul Helly). Codul sursă al acestor implementări a fost scris în limbajul de programare Python. Totodată, s-a realizat și un studiu comparativ al performanțelor obținute pentru diverse metodele de rezolvare de tip: combinatorial, SAT și respectiv programare liniară.
• Activitatea 1.4, intitulată Gestionarea proiectului si Diseminare, a avut ca rezultate principale publicarea a trei articole științifice (două articole în reviste științifice naționale, și un articol acceptat la o conferință internațională), trimiterea a două alte articole pentru publicare în reviste ISI, și un studiu bibliografic privind problema amplasării unitӑților și tehnici recente în teoria clasificării.

Etapa 2/2023, denumită Studiu despre unele probleme privind amplasarea unor instalații in România: algoritmi și analiza aprofundată, a fost compusă din patru activități principale:

• Activitatea 2.1, intitulată Analiza rețelelor de tip "facility networks’’, a avut ca rezultat o analiză aprofundată a unor proprietăți geometrice specifice rețelei mijloacelor de transport din București (acestea fiind reprezentata sub forma unui graf). Graful studiat a fost obținut prin exploatarea bazei de date care a fost creată în prima etapă a proiectului (Activitatea A.1.1). De asemenea, au fost aplicați unii algoritmi implementați în prima etapă a proiectului (Activitatea A.1.3) pentru a analiza aceste rețele.
• Activitatea 2.2, intitulată Implementarea unor algoritmi eficienți pentru unele probleme privind amplasarea unor instalații, a avut ca rezultate implementarea și testarea mai multor algoritmi și structuri de date pentru problemele k-Center si k-Median. Pentru a realiza această activitate, s-au studiat peste 14 articole de specialitate, în care au fost publicate descrierile formale a acestor algoritmi. Totodată, s-a realizat un studiu comparativ al performanțelor obținute pentru unele rețele sintetice (grafuri aleatoare) ce dețin o parte din proprietățile specifice rețelelor complexe reale.
• Activitatea 2.3, intitulată Validarea ipotezelor noastre de lucru privind dezvoltarea software-ului, a avut ca rezultat principal un studiu preliminar despre amplasarea liceelor din București. Mai precis, folosind modelul stabilit în prima etapă a proiectului (Activitatea A.1.1), s-a realizat un studiu comparativ dintre amplasarea actuală acestor licee și o amplasare optimală.
• Activitatea 2.4, intitulată Gestionarea proiectului si Diseminare, a avut ca rezultate principale publicarea a trei articole științifice (un articol într-o revistă științifică internațională și două articole acceptate la conferințe internaționale), și trimiterea a două alte articole pentru publicare în reviste și conferințe ISI.

Etapa 3/2023, denumită Crearea si validarea unui nou instrument de rezolvare a unor probleme privind amplasarea unei instalatii, a fost compusă din trei activități principale:

• Activitatea 3.1, intitulată Simularea unor probleme privind amplasarea unor instalatii, a avut ca rezultat elaborarea mai multor „business cases” pentru instrumentul nostru de rezolvare: unul este bazat pe locatia universitatilor din Bucuresti (foloseste rezultatele obtinute in cadrul Activitatii 2.1) si celelalte trei au avut la baza unor probleme privind amplasarea unor senzori in mai multe mijloace inconjuratoare (statii de metrou, activitati viticole, retele). Pentru crearea ultimelor trei ``business cases’’ am folosit unor set-uri de date obtinute de catre Beia International in cadrul unor alte proiecte.
• Activitatea 3.2, intitulată Studiu privind performantele noului software si timpul de rulare al acestuia, a avut ca rezultat un studiu comparativ al performanțelor obținute pentru instrumentul nostru de rezolvare si metodele de rezolvare de pe piata de tip SAT, respectiv programare liniară, aplicate la problemele de amplasare a unor instalații (un studiu preliminar privind performantele metodelor de rezolvare de pe piata a fost realizata in cadrul Activitatii 1.2). S-a realizat un studiu comparativ al performanțelor obținute pentru unele rețele sintetice (grafuri aleatoare).
• Activitatea 3.3, intitulată Gestionarea proiectului si Diseminare, a avut ca rezultate principale publicarea a trei articole științifice in unele reviste științifice internaționale.

Diseminare

1. Ducoffe, G. Obstructions to Faster Diameter Computation: Asteroidal Sets. 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). In LIPIcs, Volume 249, IPEC 2022 (December 2022). doi:10.4230/LIPIcs.IPEC.2022.10
2. Ducoffe, G. Obstructions to Faster Diameter Computation: Asteroidal Sets. Journal version. Submitted. Available at https://arxiv.org/pdf/2209.12438
3. Ducoffe, G. A variation of Boolean distance. Bulletin Mathematique de la Societe des Sciences Mathematiques de Roumanie, 2022, 65(113), No. 4, pp. 405-419. WOS:000965780200005
4. Ducoffe, G. The power of interval models for computing graph centralities. Romanian Journal of Information Technology and Automatic Control. 2022, 32 (4), pp.33-44. doi:10.33436/v32i4y202203. WOS:000924067500003
5. Ducoffe, G. Distance problems within Helly graphs and k-Helly graphs. Theoretical Computer Science, 2023, 946, no.113690. doi:10.1016/j.tcs.2023.113690. WOS:000923734600001
6. Dragan, F.F. and Ducoffe, G. $\alpha_i$-Metric Graphs: Radius, Diameter and all Eccentricities. 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023). In Lecture Notes in Computer Science, Volume 14093, pp. 276-290, Springer.
7. Radulescu, C.-Z., Radulescu, M. and Boncea, R. A revised group DEMATEL method with application on facility location problem in context of Internet of Things. 10th International Conference on Information Technology and Quantitative Management (ITQM 2023). In Procedia Computer Science, Volume 221, pp. 9-16, Elsevier.
8. Dissaux, T., Ducoffe, G. and Nisse, N. Treelength of series-parallel graphs. Discrete Applied Mathematics, 2023, 341, pp. 16-30. doi:10.1016/j.dam.2023.07.022. WOS:001059041300001
9. Ducoffe, G. Balancing graph Voronoi diagrams with one more vertex. Accepted. To appear in Networks, Wiley.
10. Ducoffe, G., Habib, M., Pitois, F. and Feuilloley, L. Pattern detection in ordered graphs. Submitted. Technical report available at https://arxiv.org/pdf/2302.11619.
11. Berge, P., Ducoffe, G. and Habib, M.  Subquadratic-time algorithm for the diameter and all eccentricities on median graphs. Accepted. To appear in Theory of Computing Systems, Springer.

Raport științific final (2022 - 2023)

Pentru mai multe detalii descarcă Raport științific final