Mulţumiri

4.4.3.Minimizarea mişcărilor în avans rapid

Acest tip de optimizare este unul dintre cele mai importante, reducând lungimea mişcărilor în avans rapid cu peste 95% pentru unele frezări particulare şi deschizând premisele unor generări foarte eficiente de fişiere NC pentru MUCN de viteză mare.

Această problemă îşi găseşte o paralelă în optimizarea drumului dintre n localităţi (problema comis voiajorului), materializat aici prin trasee de sculă.

Rezolvarea completă a problemei comportă o dificultate polinomială de O(n!), cu n trasee. Dacă se ia în considerare şi posibilitatea că fiecare traseu poate fi reversibil, complexitatea problemei creşte la O(n!*2ⁿ), ceea ce, din punct de vedere al timpilor de rezolvare, duce la un dezastru, în cazul în care numărul de trasee depăşeşte 50. Spre exemplu, pentru rezovarea unei probleme de 100 trasee, un calculator cu procesor Pentium Pro 200Mz a lucrat mai mult de o zi.

În realitate, fişierele NC conţin uzual 200…5000 de curbe individuale, ceea ce constituie o complexitate imposibil de rezolvat la ora actuală. Din această cauză, soluţionarea problemei comis voiajorului TSP (Traveling Salesman Problem) prin alte metode este una dintre cele mai importante probleme de optimizare, pentru care, în literatura de specialitate încearcă timid să-şi facă apariţia algoritmi din familia celor bazaţi pe automate neuronale sau celulare, sau triangularizările Delaunay.

În cazul frezării, sistemele de fabricaţie folosesc metoda de frezare în zig-zig, optimizarea oprindu-se atunci când se depăşesc cazurile particulare cunoscute.

Având în vedere importanţa pe care o are pentru generarea optimizată a fişierului NC, s-a încercat să se creeze un algoritm care să rezolve această problemă cât mai rapid şi cât mai aproape de situaţia teoretică. Acest algoritm poartă numele “Metodă euristică rapidă de rezolvare a problemei comis voiajorului” - FHTSP (Fast Heuristically Traveling Salesman Problem).

Complexitatea a scăzut de la  n la  n, ceea ce face ca timpii de rezolvare a unor probleme de 500 trasee să fie de numai 0.5 secunde, iar pentru 2000 trasee, de 10 secunde.

Soluţia găsită este ideală în proporţie de peste 90%, iar timpii de calcul nu există practic. Acest algoritm generic este implementat de către autor în GNCPP şi EdgeCAM, iar comportarea lui în practică este ireproşabilă.

Algoritmul se poate rezuma în pseudocod astfel (o versiune unidirecţională):