Proiectul are ca obiectiv stimularea inovarii in cadrul întreprinderii prin dezvoltarea unui

produs nou inovativ – o solutie software pentru logistica si transporturi, in scopul productiei si

comercializarii, care să conducă pe termen mediu şi lung la creșterea competitivității companiei

PANTIRIS INNOVATION TECHNOLOGIES SRL pe piață.

Prin realizarea proiectului societatea isi propune valorificarea rezultatelor de cercetare obţinute

în urma activitatlor de cercetare finantate de catre societate in cadrul studiului:

“Studiu de cercetare si dezvoltare de noi solutii care sa remodeleze activitatea de livrari

si transport a companiilor”

Abstract

Optimizarea rutelor de transport reprezinta o prioritate in politicile economice ale Uniunii Europene.

In afara costurilor directe, transportul creeaza un plus de trafic, poluare sau zgomot. In domeniul

logisticii, optimizarea transportului reprezinta poate cea mai importante si mai studiata problema. Ea

apare un doar in coectarea si distributia bunurilor si si in servicii cum ar fi: taxi, livrari,rute ale

vehiculelor scolare, rute ale depanatorilor etc.

Ideea de baza pleaca de la binecunoscuta problema a comis-voiajorului care poate fi enuntata astfel:

“Fiind dat un numar fix de orase, precum si distantele dintre fiecare 2 orase, care este cea mai scurta

ruta posibila, prin care sa se viziteze fiecare oras o singura data, iar destinatia finala sa coincida cu

punctul de plecare”. Pe scurt, in varianta clásica, se cere identificarea unui circuit Hamiltonian de cost

minim intr.-un graf complet.

Problema este foarte veche, avand originile la inceputul secolului al XIX lea, dar prima abordare

matemática dateaza din anii 1930 cand a fost studata atat in Viena, cat si la Harvard. Denumirea a fost

data de Hassler Whitney (Univ. Princeton) tot in aceeasi perioada. Dupa anii 50, problema a devenit

din ce in ce mai populara in randul oamenilor de stiinta. Popularitatea problemei voiajorului deriva

din contrastul dintre simplitatatea enuntului si complexitatea calculelor necesare. Ceea ce o face insa

atat de importanta este reprezentat de multimea aplicatiilor posibile, incepand cu identificarea rutei

optime pentru miloacele de transport, pana la generarea traseelor urmate de dispozitivele de producere

a circuitelor integrate.

Rezolvarea problemei

Problema poate fi rezolvata exact, analizand toate circuitele posibile si identificand circuitul optim.

Pentru valori mici ale numarului de orase, se poate aplica aceasta metoda, insa in realitate, numarul

nodurilor este suficient de mare astfel incat, identificarea solutiei optime sa aiba nevoie de algoritmi

cu timpi de rulare foarte mari, iar in situatiile practice, astfel de algoritmi un ar fi fezabili. Numarul de

circuite posibile este egal cu (n-1)!/2. Problema voiajorului este inclusa in clasa problemelor “NP –

complete”, fiind una dintre problemele nerezolvate in domeniul “computer science”. Caracteristica

principala a acestor probleme este ca timpul de rezovare folosind un algoritm cunoscut, reste

exponential pe masura ce creste compexitatea problemei (numarul de noduri).

Pentru o rete acu 7 noduri, exista 360 variante. Pentru o rete acu 8 noduri, exista 2520 variante, pentru

una cu 10 noduri – 181440, la 11 noduri fiind aproape 2 milioane de variante. De exemplu, a fost

identificata in 2001 solutia optima exacta pntru 15112 orase din Germania, folosindu-se de metoda

propusa de Dantzig in 1954. Calculele au fost efectuate pe o retea de 110 procesoare de mare putere,

sitúate la Universitatea Rice si Universitatea Princeton. Daca acelasi calcul ar fi fost efectut cu un

singur computer cu un procesor de 500MHz, calculele ar fi durat 22.6 ani.

Identificarea rutei optime

Problema identificarii rutei optime este problema de optimizare combinatoriala si programare in

numere intregi. Se refera la deservirea unui numar de clienti cu o flota data de vehicule. Formulata de

Dantzig in 1959, reprezinta una dintre cele mai importante problema in transport, distributie si

logística. Cel mai intalnit cadru se refera la fírmele de curierat care preiau colete de la un depozit

central, livreaza la clienti si se reintorc la depozit. Scopul problemei il reprezinta minimizarea

costurilor. Identificarea solutiei optime este de asemenea din categoría “NP-complete”

In cadrul studiului de cercetare – dezvoltare s-a elaborat o euristia de optimizare hibrida ce combina

avantajele euristicilor populationale in faza de diversificare (cautarea dispersata) cu intensificarea

obtinuta in urma algoritmului de optimizare distribuita de tipcolonie de furnici. Desi cautarea tabu

este cunoscuta a avea o eficiente crescuta pentru obtinerea unor solutii bune pentru problemele de

optimizare combinatoriala in cazul problemei de transport ne intalnim cu instanta teoremelor de tip no

free lunch, demonstrate de William Macready (nicio metoda euristica simpla un este universal

eficienta pe intreaga clasa aproblemelor de optimizare combinatoriala). Succesul metodei hibride sta

in asa numitul “pranz gratis coevolutionar” in o populatie intreaga de optimizatori concreaza pentru

accesul la resurse (selectia in setul de referinta)