Optimization methods for solving transportation problems on networksKatja Prnaver
, 2011, dissertation
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
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 , 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
Keywords: graph theory, networks, optimization, shortest path problem, traveling salesman problem, algorithms, metaheuristics, order batching
Published: 03.06.2011; Views: 4074; Downloads: 184
Full text (925,86 KB)