Strategic planning and transport optimization algorithms

Predmet istraživanja doktorske disertacije su algoritmi za planiranje i optimizaciju transporta. Ciljevi rada su konstrukcija, testiranje i analiza predloženih algoritama. Razmatrana su tri problema planiranja transporta, problemi taktičkog planiranja, strateškog planiranja i strateško-taktičkog planiranja i sinhronizacije sa proizvodnjom, kao i jedan problem generisanja matrica rastojanja. Za svaki problem implementiran je algoritam, definisani test primeri, metodologija testiranja, analizirani rezultati, izvedeni zaključci i navedeni pravci za poboljšanja i dalja istraživanja. Za potrebe rešavanja problema taktičkog planiranja definisana je posebna struktura bazirana na stablima, algoritam odabiranja satelita i ciljna funkcija. Algoritam za strateško planiranje koristi strukturu kružne liste za kodiranje lokacija i vozila i generičku transformaciju. Modelirana je dinamika hlađenja za algoritam Simuliranog kaljenja u skladu sa veličinom test primera. Za strateško-taktički problem planiranja i sinhronizaciju sa proizvodnjom odabran je problem distribucije novina u Danskoj. Data je definicija problema, predloženi su model, struktura bazirana na stablima i transformacije. Definisano je dekodiranje plana transporta kao i način raspoređivanja novina na vozila. Za potrebe generisanja matrica rastojanja konstruisan je Algoritam konusa koji putem internet servisa preuzima deo putne mreže dok se preostala rastojanja potrebna za matricu preračunavaju uz pomoć Dijkstra algoritma. Rezultati testiranja algoritma taktičkog planiranja pokazali su da je moguće efikasno automatski odabirati pozicije satelita i ostariti uštedu u ukupnim troškovima. Kružna struktura i generička transformacija u algoritmu za strateško planiranje dali su rezultate koji su uporedivi sa najboljim rezultatima dostupnim u literaturi. Algoritam za strateško-taktičko planiranje i sinhronizaciju sa proizvodnjom uspeo je da pronađe nekoliko najboljih rešenja na test primerima iz literature i ostvari uštedu od 15% do 25% na realnim problemima iz prakse. Matrice generisane Dijsktra algoritmom iz rastojanja dobijenih primenom Algoritma konusa sadrže oko 50% optimalnih vremenskih i oko 80% optimalnih prostornih rastojanja. Testovi su pokazali da primena ovih matrica u softveru za optimizaciju daju rešenja istog kvaliteta kao i matrice dobijene preuzimanjem svih rastojanja grubom silom. Svi algoritmi implementirani su i koriste se u softverskim paketima u praksi.The subject of the doctoral dissertation research is algorithms for transport planning and optimization. The objectives of the work are the construction, testing, and analysis of the proposed algorithms. Three problems of transport planning, problems of tactical planning, strategic planning, and strategic-tactical planning and synchronization with the production were considered, as well as one problem of generating distance matrices. For each problem, an algorithm was implemented, test examples and testing methodology were defined, results, conclusions, and directions for improvements and further research were stated. For the purpose of solving the problem of tactical planning, a special structure based on trees, a satellite selection algorithm, and a target function have been defined. The strategic planning algorithm uses a circular list structure for coding locations and vehicles, and generic transformation. The cooling schedule for the Simulated Annealing algorithm is modeled. The problem of newspaper distribution in Denmark was chosen for the strategic-tactical problem of planning and synchronization with production. The definition of the problem is given, the model is proposed, a structure based on trees, and transformations are presented. The decoding of the transport plan has been defined, as well as the manner of distributing newspapers on vehicles. For the purpose of generating distance matrices, a Cone Algorithm was constructed, which downloads a part of the road network via an Internet service, while the remaining distances required for the matrix are recalculated with the help of the Dijkstra algorithm. The results of testing the tactical planning algorithm have shown that it is possible to efficiently automatically select satellite positions and make savings in total costs. The circular structure and generic transformation in the strategic planning algorithm yielded results that are comparable to the best results available in the literature. The algorithm for strategic-tactical planning and synchronization with production managed to find some of the best solutions on test examples from the literature and achieved savings of 15% to 25% on real problems from practice. Matrices generated using the Dijkstra algorithm from distances obtained using the Cone Algorithm contain about 50% of the optimal time and about 80% of optimal spatial distances. Tests have shown that the application of these matrices in optimization software gives solutions of the same quality as matrices obtained by getting all distances by brute force. All algorithms are implemented and used in software packages in practice