| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font
First page > Show document

Show document Help

Title:Optimization methods for solving transportation problems on networks
Authors:ID Prnaver, Katja (Author)
ID Zmazek, Blaž (Mentor) More about this mentor... New window
ID Pisinger, David (Comentor)
Files:.pdf DR_Prnaver_Katja_2011.pdf (925,86 KB)
MD5: FEAD9476151B79CD1ADF4175490A4DAA
PID: 20.500.12556/dkum/64be54a2-bb49-437a-aac9-2b01d7d8fa09
 
Language:English
Work type:Dissertation
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract:In this thesis we study problems from real situations, which can be applied to network graphs and solved using mathematical graph theory. We start with the problem of oriented network design. The problem originates from networks, where the flow over the arcs is important and many times limited with the capacity of the networks. There are several techniques and results on the problem of assigning the flow through the network channels. In our problem, we try to find the optimal network structure, which could be used in the design phase of the network. With metaheuristics, we search for optimal network structures for a given number of nodes. We define triangle neighborhood and compare the results of the algorithm with the conjecture by Choplin et al. [8]. Further, we study the problem of order picking and order batching in block structured warehouses. For order picking problem, we present the extension of a dynamic programming algorithm by Ratliff and Rosenthal [42], which enables the development of an algorithm for an unlimited number of blocks. In order to achieve this, a new presentation of states and transitions of dynamic programming algorithm is given. We prove that the resulting path is optimal for the given structure. We compare the optimal path lengths to the results found in literature and also investigate the impact of warehouse layout parameters onto the routing. Closely related to the problem of order picking, we investigate the order batching problem. We discuss the variation of the order batching problem with time windows and present the algorithmic approach to solving the problem. The previously presented optimal path algorithm is applied in the algorithm to ensure even better quality of results. We introduce the evaluation function of a batch and compare the results of the algorithm with the test data from the literature as well as with data from the real warehouse. We conclude by summarizing the results and stating some possible extensions and further work.
Keywords:graph theory, networks, optimization, shortest path problem, traveling salesman problem, algorithms, metaheuristics, order batching
Place of publishing:[Maribor
Publisher:K. Prnaver]
Year of publishing:2011
PID:20.500.12556/DKUM-18663 New window
UDC:519.17:519.85(043.3)
COBISS.SI-ID:256276736 New window
NUK URN:URN:SI:UM:DK:VUSERYVH
Publication date in DKUM:03.06.2011
Views:5488
Downloads:259
Metadata:XML DC-XML DC-RDF
Categories:FNM
:
PRNAVER, Katja, 2011, Optimization methods for solving transportation problems on networks [online]. Doctoral dissertation. Maribor : K. Prnaver. [Accessed 7 April 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=18663
Copy citation
  
Average score:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:Slovenian
Title:Optimizacijske metode za reševanje transportnih problemov na omrežjih
Abstract:V doktorskem delu smo preučili problem iz vsakdanjih situacij, ki jih je mogoče prevesti na problem na omrežnih grafih in jih rešili z uporabo matematične teorije grafov. Začnemo s problemom usmerjenih omrežij. Problem izvira iz omrežja, kjer je pretok skozi loke pomemben in velikokrat omejen s kapaciteto omrežij. Obstaja več tehnik ter rezultatov za problem določanja pretoka skozi omrežja. Pri našem problemu poskušamo najti optimalno omrežno strukturo, ki bi se lahko uporabljala v fazi načrtovanja omrežja. Z metahevrističnim pristopom iščemo optimalne strukture omrežja za določeno število vozlišč. Definiramo trikotniško soseščino in primerjamo rezultate algoritma z domnevo, ki so jo postavili Choplin in drugi. Nadalje preučujemo problem iskanja optimalne poti v bločno strukturiranem skladišču. Za problem predstavimo nadgradnjo algoritma dinamičnega programiranja, ki sta ga uvedla Ratliff in Rosenthal, in ki omogoča razvoj algoritma za neomejeno število blokov. Predstavljen je nov način zapisa stanja in prehodov med fazami dinamičnega programiranja. Dokažemo, da je rezultantna pot optimalna. Primerjamo naše rezultate za dolžino optimalne poti z rezultati iz literature in preučimo vpliv parametrov na najkrajše poti pri različnih postavitvah skladišč. Preučimo še tesno povezan problem komisioniranja, in sicer različico z časovnimi okni. Predstavimo algoritmični pristop k reševanju problema. Uporabimo predhodno predstavljen algoritem za iskanje optimalne poti,in s tem zagotovimo še večjo kakovost rezultatov. Uvedemo ocenitveno funkcijo za množico naročil in primerjamo rezultate algoritma s podatki iz literature, kot tudi s podatki iz dejanskega skladišča. Delo zaključimo s povzetkom rezultatov in navedemo nekatere možne razširitve in nadgradnje.
Keywords:teorija grafov, omrežja, optimizacija, iskanje najkrajše poti, problem trgovskega potnika, algoritmi, metahevristike, komisioniranje


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica