Search the digital library catalog

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
Published: 03.06.2011; Views: 4124; Downloads: 190
Full text (925,86 KB)

Abstract: Let ▫$lambda(G)$▫ be the edge connectivity of ▫$G$▫. The direct product of graphs ▫$G$▫ and ▫$H$▫ is the graph with vertex set ▫$V(G times H) = V(G) times V(H)$▫, where two vertices ▫$(u_1,v_1)$▫ and ▫$(u_2,v_2)$▫ are adjacent in ▫$G times H$▫ if ▫$u_1u_2 in E(G)$▫ and ▫$v_1v_2 in E(H)$▫. We prove that ▫$lambda(G times K_n) = min{n(n-1)lambda(G), (n-1)delta(G)}$▫ for every nontrivial graph ▫$G$▫ and ▫$n geqslant 3$▫. We also prove that for almost every pair of graphs ▫$G$▫ and ▫$H$▫ with ▫$n$▫ vertices and edge probability ▫$p$▫, ▫$G times H$▫ is ▫$k$▫-connected, where ▫$k=O((n/log n)^2)$▫.
Keywords: mathematics, graph theory, combinatorial problems, connectivity, direct product, graph product, separating set
Published: 01.06.2012; Views: 1667; Downloads: 194
Link to full text

Abstract: Encyclopedia of Complexity and Systems Science provides an authoritative single source for understanding and applying the concepts of complexity theory together with the tools and measures for analyzing complex systems in all fields of science and engineering. The science and tools of complexity and systems science include theories of self-organization, complex systems, synergetics, dynamical systems, turbulence, catastrophes, instabilities, nonlinearity, stochastic processes, chaos, neural networks, cellular automata, adaptive systems, and genetic algorithms. Examples of near-term problems and major unknowns that can be approached through complexity and systems science include: The structure, history and future of the universe; the biological basis of consciousness; the integration of genomics, proteomics and bioinformatics as systems biology; human longevity limits; the limits of computing; sustainability of life on earth; predictability, dynamics and extent of earthquakes, hurricanes, tsunamis, and other natural disasters; the dynamics of turbulent flows; lasers or fluids in physics, microprocessor design; macromolecular assembly in chemistry and biophysics; brain functions in cognitive neuroscience; climate change; ecosystem management; traffic management; and business cycles. All these seemingly quite different kinds of structure formation have a number of important features and underlying structures in common. These deep structural similarities can be exploited to transfer analytical methods and understanding from one field to another. This unique work will extend the influence of complexity and system science to a much wider audience than has been possible to date.
Keywords: cellular automata, complex networks, computational nanoscience, ecological complexity, ergodic theory, fractals, game theory, granular computing, graph theory, intelligent systems, perturbation theory, quantum information science, system dynamics, traffic management, chaos, climate modelling, complex systems, dynamical sistems, fuzzy theory systems, nonlinear systems, soft computing, stochastic processes, synergetics, self-organization, systems biology, systems science
Published: 01.06.2012; Views: 1676; Downloads: 87
Link to full text

Keywords: graph theory, lexicographic product, Roman domination function, Roman dimination number
Published: 07.06.2012; Views: 1145; Downloads: 58
Link to full text

Abstract: Fault tolerance and transmission delay of networks are important concepts in network design. The notions are strongly related to connectivity and diameter of a graph, and have been studied by many authors. Wide diameter of a graph combines studying connectivity with the diameter of a graph. Diameter with width ▫$k$▫ of a graph ▫$G$▫, ▫$k$▫-diameter, is defined as the minimum integer ▫$d$▫ for which there exist at least ▫$k$▫ internally disjoint paths of length at most ▫$d$▫ between any two distinct vertices in ▫$G$▫. Denote by ▫${mathscr D}_c(G)$▫ the ▫$c$▫-diameter of ▫$G$▫ and ▫$kappa(G)$▫ the connectivity of ▫$G$▫. In the context of computer networks, wide diameters of Cartesian graph products have been recently studied by many authors. Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let ▫$G$▫ be a Cartesian graph bundle with fiber ▫$F$▫ over base ▫$B$▫, ▫$0 < a le kappa(F)$▫, and ▫$0 < b le kappa(B)$▫. We prove that ▫${mathscr D}_{a+b}(G) le {mathscr D}_a(F) + {mathscr D}_b(B) + 1$▫. Moreover, if ▫$G$▫ is a graph bundle with fiber ▫$F ne K_2$▫ over base ▫$B ne K_2$▫, then ▫${mathscr D}_{a+b}(G) le {mathscr D}_a(F) + {mathscr D}_b(B)$▫. The bounds are tight.
Keywords: mathematics, graph theory, Cartesian graph products, Cartesian graph bundles, wide diameter
Published: 07.06.2012; Views: 1255; Downloads: 69
Link to full text