METODE ALGORITMICE DE REZOLVARE A PROBLEMELOR DE OPTIMIZARE COMBINATORICA
DESCRIEREA PROIECTULUI

Importanta si relevanta continutului stiintific

Optimizarea combinatorica este un domeniu al matematicii aplicate in care se lucreaza intens in ultima sperioada, in special datorita numarului mare de aplicatii: in management (finante, problema portofoliului de investitii, marketing, productie, programare si planificare, reglarea stocurilor prin productie, probleme de locatie, etc), in disciplinele ingineresti (modul optim de proiectare a drumurilor, autostrazilor, podurilor; proiectarea circuitelor VLSI (very large scale integrated), modele de planificare a resurselor energetice, telecomunicatii), probleme de transport, probleme de optimizare a cailor ferate si transportului aerian, etc.

Optimizarea combinatorica combina tehnici din cercetari operationale, teoria grafurilor, combinatorica, programare matematica, teoria algoritmilor pentru a rezolva probleme de optimizare definite pe structuri discrete.

Echipa de cercetare se va axa pe urmatoarele probleme de optimizare combinatorica:

  1. Probleme generalizate de optimizare combinatorica. Problemele clasice de optimizare combinatorica pot fi generalizate in mod natural prin considerarea unei probleme inrudite relativ la o partitie data a virfurilor unui graf neorientat in multimi de virfuri. Aceste probleme generalizeaza problemele clasice de optimizare combinatorica si au un grad ridicat de complexitate. Se vor studia urmatoarele probleme:
  2. Probleme de optimizare a cailor ferate si transportului aerian:
    1. Probleme de optimizare a cailor ferate
    2. Probleme de optimizare a transportului aerian
Gradul de complexitate si noutate ale proiectului

Problemele de optimizare in care suntem interesati: problema generalizata a invelitorii minime de tip arbore, problema generalizata a comis voiajorului, probleme de optimizare a cailor ferate si a transportului aerian, sunt probleme cu un grad de complexitate foarte ridicat, facand parte din clasa problemelor NP-hard ceea ce inseamna ca problemele sunt foarte dificile din punct de vedere al teoriei complexitatii, in plus aceste probleme nu pot fi rezolvate cu ajutorul unor algoritmi cu timpi de executie polinomiali.

Diferite tehnici din Cercetari Operationale, Optimizare Combinatorica, Teoria Algoritmilor, Modelare matematica, Programare matematica, Teoria complexitatii, etc vor fi folosite. Transpunerea acestora in metode practice si implementarea lor este sarcina informaticienilor. De aceea echipa de cercetare este compusa din persoane cu diferite arii de specialitate: matematica, informatica si stiinte economice. Fiecare membru aducandu-si abilitatea si experienta sa echipei de cercetare.

Principalele elemente originale vizate de catre echipa de cercetare sunt :

  1. Elaborarea de noi modele matematice bazate pe programarea intreaga si programarea mixta (liniara si intreaga) pentru problemele de optimizare prezentate anterior, analiza acestor modele si compararea lor.
  2. Elaborarea de metode algoritmice bazate pe algoritmi meta-euristici ca de exemplu algoritmi de tip colonia furnicilor (Ant Colony algorithms), retele neuronale, calire simulata (Simulated Annealing) etc. pentru problemele de optimizare considerate.
  3. Implementarea metodelor algoritmice propuse si demonstrarea eficacitatii lor pe date reale obtinute de la Caile Ferate Romane si Tarom, iar pentru problemele generalizate de optimizare combinatorica metodele propuse de echipa de cercetare se vor compara cu cele existente in literatura de specialitate.
  4. Inovatia, va fi o alta trasatura importanta, pe parcursul perioadei de cercetare, echipa de cercetare va fi deschisa si receptiva la alte probleme specifice cailor ferate sau transportului aerian.
Gradul de competitivitate a rezultatelor obtinute in cadrul proiectului

Rezultatele stiintifice au un grad de competitivitate foarte ridicat in domeniul stiintific abordat astfel:

  1. unele articole au inceput deja sa fie citate in alte lucrari care vor aparea in jurnale cotate ISI;
  2. algoritmii propusi au fost implementati si testati pe date din literatura de specialitate dovedindu-si eficacitatea;
  3. s-au publicat 3 articole in reviste cotate ISI, 3 articole in volumele unor conferinte internationale cotate ISI si un numar de 7 articole aparute in jurnale si volumele unor conferinte internationale indexate in baze de date internationale;
  4. doua dintre conferintele internationale unde au fost comunicate rezultate obtinute sunt printre cele mai prestigioase in acest domeniu, avand o rata de acceptabilitate a lucrarilor de 28% respectiv 40%.
Gradul de vizibilitate a rezultatelor obtinute in cadrul proiectului

Rezultatele obtinute pana in aceasta faza au fost concretizate astfel: 3 articole in reviste cotate ISI; articole in volumele unor conferinte internationale cotate ISI (doua aparute, iar unul in curs de aparitie) si un numar de 7 articole aparute in jurnale si volumele unor conferinte internationale indexate in baze de date internationale. De asemenea un numar de 5 lucrari au fost trimise spre publicare, 2 la reviste cotate ISI, 2 la volumele unorconferinte internationale cotate ISI si unul la un jurnal indexat in baze de date internationale.

Gradul de viabilitate a proiectului

Pentru problemele de optimizare a cailor ferate si a transportului aerian am propus algoritmi eficienti de rezolvare folosind algoritmi de tip colonia furnicilor. Acesti algoritmi au fost implementati si testati pe date din literatura de specialitate (furnizate de compania olandeza de cai ferate Nederlandse Spoorwegen si date sintetice) dovedindu-si eficacitatea. In timpul ramas in cadrul proiectului dorim sa aplicam si testam acesti algoritmi pe date obtinute de la Caile Ferate Romane (CFR) si Tarom. In acest sens am contactat persoane de la institutiile amintite anterior, urmand a face prezentari ale rezultatelor obtinute si a gasi impreuna posibilitati de aplicare a acestora.

© nnn Scream Design nnn