20.500.12556/DKUM-14041 PROBLEM KITAJSKEGA POŠTARJA S PRIORITETNIMI VOZLIŠČI CHINESE POSTMAN PROBLEM WITH PRIORITY NODES V doktorski disertaciji z naslovom Problem kitajskega poštarja s prioritetnimi vozlišči je preučevana posplošitev problema kitajskega poštarja, v kateri je podmnožica vozlišč utežena in vrstni red obiska vozlišč vpliva na vrednost namenske funkcije. Preučevan problem je dokazano NP-težek. V disertaciji sta predstavljeni in preučevani dve konstrukcijski hevristiki. Za eno izmed njih je dokazano, da ob določenih pogojih vrne optimalne rešitve. Hevristiki sta implementirani in testirani na več razredih naključno tvorjenih instanc. A generalization of the Chinese Postman Problem in which the delays at a subset of priority nodes are penalized in the cost function is studied in present thesis. As it is shown that the problem is NP-hard, two tour constructing heuristics are proposed, and their properties are studied. It is proved that one of the heuristics gives optimal solutions on a subset of instances with bounded cost of delays. The implementations of the heuristics are compared on several types of randomly generated instances. problem kitajskega poštarja problemi usmerjanja Eulerjev graf prioritetna vozlišča modificiran algoritem Dijkstre modificiran Kruskalov algoritem Chinese Postman Problem Arc Routing Problem Eulerian Graph Priority Nodes Modified Dijkstra Algorithm Modified Kruskal Algorithm true true false [T. Kramberger] Slovenski jezik Angleški jezik Doktorska disertacija 2010-05-21 10:27:51 2010-05-27 07:49:33 2022-04-12 11:41:13 2023-12-17 03:12:22 2010 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.932(043.3) 14123542 URN:SI:UM:DK:EXOJMM2A DR_Kramberger_Tomaz_2010.pdf DR_Kramberger_Tomaz_2010.pdf 1 4730CECA27EA4A93F42B6B95F068DB8F fdc553624e98bae8607ecf2381babf22311bd4959c0f92c1a813f8eb5c85c701 0e9ddeed-7c04-11eb-bb7a-00155d0001ca 20.500.12556/dkum/a4f563f9-3cb9-42c6-98a7-90299c94ef0b https://dk.um.si/Dokument.php?lang=slv&id=14708 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0