Резултати истраживања професора Рачунарског факултета у Београду Драгана Урошевића објављени у престижном међународном часопису Information Sciences

Професор Рачунарског факултета у Београду Драган Урошевић објавио је преко 60 радова у истакнутим међународним часописима, међународним и домаћим конференцијама. Био је председник  Организационог одбора друге међународне конференције посвећене Методи променљивих околина и члан  Програмског одбора већег броја конференција посвећених Методи променљивих околина. Члан је уређивачког одбора часописа ComSIS и YUJOR. Такође је и члан Програмског одбора симпозијума о операционим истраживањима SYM-OP-IS.
Главна област интересовања професора Драгана Урошевића су проблеми комбинаторне и глобалне оптимизације.
 
Код ових проблема циљ је одредити тзв. оптимално решење које представља глобални минимум или глобални максимум неке функције која се још зове и функција циља. Та функција обично има велики број аргумената (непознатих величина), при чему ти аргументи треба да задовољавају неке услове (ограничења). Најчешће су вредности неких или свих непознатих цели бројеви и тада кажемо да је то проблем мешовито целобројног (линеарног) програмирања.
Најпознатији проблем из ове области је добро познати проблем трговачког путника. Трговачки путник треба да посети одређени број градова и да се врати у град из кога је кренуо али тако да укупни пређени пут буде што краћи. Овај проблем је био предмет интересовања и знатно пре појаве рачунара. Са појавом рачунара порасло је интересовање за овај проблем јер се помоћу рачунара могао решавати проблем са врло великим бројем улазних података (градова које би требало да обиђе путник).
Данас постоји велика библиотека улазних података (такозваних инстанци) за проблем трговачког путника. Највеће инстанце имају на десетине хиљада градова (места) које треба да обиђе путник. Проблем трговачког путника је само један од представника проблема комбинаторне оптимизације. Сви они су, мање више, настали при проучавању неког проблема из реалног живота при чему су мање или више апстраховане неке ствари везане за те проблеме. Већина од проблема спада у групу тзв. НП-тешких проблема.
Главна одлика тих проблема је да бар за сада не постоје тачне методе које на класичним рачунарима одређује тачно решење у времену које се изражава у облику полинома који зависи од димензије проблема (величине проблема). Због тога се обично развијају приблизне методе за решавање тих проблема. Њихова је одлика да у неком разумном времену проналазе решење које не мора бити оптимално али је по вредности функције циља близу оптималног решења (нпр.дужина пронађене маршуте трговачког путника је врло близу дужине оптималне (најкраће)) руте.
 
Проблеми које је професор Драган Урошевић проучавао са својим колегама се могу сврстати у неколико група:
 
1. Варијанте проблема трговачког путника. Од основне варијанте проблема трговачког путника је настао велики број варијанти:
 
-проблем трговачког са временским прозорима - сваки корисник кога треба да посети трговачки путник има неки временски интервал (прозор) у коме може да прими робу од трговачког путника тако да, ако путник стигне пре почетка тог интервала, мора чекати до почетка тог интервала.
 
-проблем трговачког путника са преузимањем и испоруком - неки од корисника које треба да посети путник су произвођчи (нпр. издавачке куће, млекаре, кланице), а други су потрошачи (нпр. киосци , маркети, месаре). Сваки произвођач предаје путнику одређену количину производа, а сваки потрошач потражује одређену количину производа.Путник има возило ограничене носивости и треба да у неком редоследу обиђе кориснике, преузме робу од произвођача и испоручи потрошачима, али тако да пређена маршута буде што краћа.
 
-проблем испоручиоца (Traveling Deliveryman Problem) је врло сличан проблему трговачког путника. Од проблема трговачког путника се разликује
само по вредности (критеријуму) која се минимизује: код проблема трговачког путника је потребно минимизовати дужину туре, а код проблема испоручиоца треба минимизовати збир времена долазака (или времена опслуживања) корисника.
 
-варијанте hab локацијских проблема. Код ових проблема постоји одређен број места између којих се врши транспорт робе (за сваки пар места је позната количина робе која се транспортује између њих). Да би се транспорт појефтинио, успоставља се одређени број центара за прикупљање робе (хабови). Хабови се налазе на неким од места, док се места у којима не постоје хабови придружују једном или више хабова. Роба између места А и Б се транспортује тако што се транспортује од места А до хаба придруженог месту А, затим од хаба придруженог месту А до хаба прируженог месту Б и коначно од места придруженог месту Б до места Б (значи не може се директно транспортовати између два места која нису хабови). Транспорт између хабова је јефтинији (или бржи) јер се одвија коришћењем јефтинијих (бржих) превозних средстава. Потребно је одредити распоред (задатог броја) хабова тако да се минимизује укупна цена транспорта или цена транспорта између два места између којих је најскупљи транспорт. Зависно од тога који се од два критеријума минимизује, као и од тога да ли се једном месту (кориснику) може придружити један или више хабова, постоји већи број варијанти хаб локацијског проблема.
 
 
2.  Проблеми поделе елемената скупа тако да се минимизује / максимизује различитост или сличност (diversity/similarity). За сваки пар елемената скупа је  позната различитост. Поребно је елементе скупа поделити у групе, тако да се минимизира или максимизира различитост између елемената који се налазе у истој групи. При томе број елемената у групама не може бити мањи од задатог минималног броја, нити већи од задатог максималног броја. Један од последњих проблема који је недавно истраживан је проблем путујућег сервисера са профитом (Traveling Repairman with Profits Problem). Сервисер има одређен број својих клијената. Код сваког од њих треба обави неко сервисирање и за то сервисирање остварује одређену зараду (није иста за све клијенте). Али та зарада се смањује за време које је протекло од неког почетног тренутка (нпр. почетак дана када сервсер креће из своје радње) до тренутка када је стигао до тог клијента (тј. за време потребно да опслужи тог клијента). Време доласка до неког клијента је порпорционално дужини туре коју је прешао. За овај проблем су професор Драган Урошевић и колеге су предложили методу базирану на методи променљивих околина. Та метода по карактеристикама значајано превазилази све постојеће методе (на тест инстанцама где је број клијената 500, резултати су бољи за више од 1%). Добијени резултати су објављени у раду Solving the traveling repairman  problem with profits: A Novel variable neighborhood search approach који је публикован у истакнутом међународном часопису Information Sciences.