20.500.12556/RUL-150461 Razporejanje prometa po cestnem omrežju The distribution of traffic on the road network V delu obravnavamo problem usmerjanja več vozil iz začetnih lokacij do ciljnih lokacij preko omrežja cest. Cestno omrežje ima na vsakem odseku omejeno kapaciteto. Cilj je vozilom dodeliti poti tako, da minimiziramo vsoto potovalnih časov. Problem imenujemo problem najcenejšega pretoka več dobrin, pri čemer smo želeli poiskati dovolj zmogljivo metodo, da bi delovala tudi na velikih realnih omrežjih. Implementirali smo več različnih reševalnih metod. Med njimi so požrešna metoda, sestopanje, Lagrangeova relaksacija in razveji in omeji. Te metode smo primerjali s standardnimi pristopi, kot so simpleksna metoda in razveji in obreži. Za nedopustne primere smo uporabili metodo dvokriterijski razveji in obreži, za velike primere pa metodo, ki poti optimizira lokalno. Raziskava je vključevala demonstracijo metod na majhnih sintetičnih primerih in realnih primerih ter testiranje na sintetičnih podatkih. S tem smo ugotovili, da so nekateri reševalniki absolutno boljša izbira od drugih. In this work, we deal with the problem of routing several vehicles from starting locations to destination locations via the road network. The road network has limited capacity on each section. The goal is to assign routes to vehicles in such a way as to minimize the sum of travel times. We call the problem minimum-cost multicommodity flow problem, and we wanted to find a method powerful enough to work even on large real networks. We have implemented several different solvers. These include the greedy method, descent, Lagrange relaxation, and branch and bound method. We compared these methods with standard approaches such as the simplex method and branch and cut method. For infeasible cases, we used the bi-objective branch and bound method, and for large cases, the method that optimizes paths locally. The research involved demonstration of the methods on small synthetic examples and real-world examples and also testing on synthetic data. With this, we found that some solvers are absolutely a better choice than others. problem pretoka več dobrin celoštevilsko programiranje Lagrangeova relaksacija razveji in omeji razveji in obreži CVXPY multicommodity flow problem integer programming Lagrange relaxation branch and bound branch and cut CVXPY true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2023-09-18 10:55:00 2023-09-18 10:55:05 2023-11-20 09:04:31 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 36537 169202179 Groselj_Ema_leila_-_Razporejanje_prometa_po_cestnem_omrezju.pdf Groselj_Ema_leila_-_Razporejanje_prometa_po_cestnem_omrezju.pdf 1 E2234C1991B08E91A43C37ABB386DB48 652247f30b6662332e8abd0649ef175de2b0016115369512f6654f6f6fb22582 0f9f975f-5601-11ee-9206-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=175042 Fakulteta za računalništvo in informatiko Fakulteta za matematiko in fiziko 0 0 0