Doctoral Degrees (Logistics)

Permanent URI for this collection

https://scholar.sun.ac.za/handle/10019.1/726

Browse

Browsing Doctoral Degrees (Logistics) by browse.metadata.advisor "Burger, A. P."

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    On the existence and enumeration of sets of two or three mutually orthogonal Latin squares with application to sports tournament scheduling
    (Stellenbosch : Stellenbosch University, 2012-03) Kidd, Martin Philip; Van Vuuren, J. H.; Burger, A. P.; Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics.
    ENGLISH ABSTRACT: A Latin square of order n is an n×n array containing an arrangement of n distinct symbols with the property that every row and every column of the array contains each symbol exactly once. It is well known that Latin squares may be used for the purpose of constructing designs which require a balanced arrangement of a set of elements subject to a number of strict constraints. An important application of Latin squares arises in the scheduling of various types of balanced sports tournaments, the simplest example of which is a so-called round-robin tournament — a tournament in which each team opposes each other team exactly once. Among the various applications of Latin squares to sports tournament scheduling, the problem of scheduling special types of mixed doubles tennis and table tennis tournaments using special sets of three mutually orthogonal Latin squares is of particular interest in this dissertation. A so-called mixed doubles table tennis (MDTT) tournament comprises two teams, both consisting of men and women, competing in a mixed doubles round-robin fashion, and it is known that any set of three mutually orthogonal Latin squares may be used to obtain a schedule for such a tournament. A more interesting sports tournament design, however, and one that has been sought by sports clubs in at least two reported cases, is known as a spouse-avoiding mixed doubles round-robin (SAMDRR) tournament, and it is known that such a tournament may be scheduled using a self-orthogonal Latin square with a symmetric orthogonal mate (SOLSSOM). These applications have given rise to a number of important unsolved problems in the theory of Latin squares, the most celebrated of which is the question of whether or not a set of three mutually orthogonal Latin squares of order 10 exists. Another open question is whether or not SOLSSOMs of orders 10 and 14 exist. A further problem in the theory of Latin squares that has received considerable attention in the literature is the problem of counting the number of (essentially) different ways in which a set of elements may be arranged to form a Latin square, i.e. the problem of enumerating Latin squares and equivalence classes of Latin squares of a given order. This problem quickly becomes extremely difficult as the order of the Latin square grows, and considerable computational power is often required for this purpose. In the literature on Latin squares only a small number of equivalence classes of self-orthogonal Latin squares (SOLS) have been enumerated, namely the number of distinct SOLS, the number of idempotent SOLS and the number of isomorphism classes generated by idempotent SOLS of orders 4 n 9. Furthermore, only a small number of equivalence classes of ordered sets of k mutually orthogonal Latin squares (k-MOLS) of order n have been enumerated in the literature, namely main classes of 2-MOLS of order n for 3 n 8 and isotopy classes of 8-MOLS of order 9. No enumeration work on SOLSSOMs appears in the literature. In this dissertation a methodology is presented for enumerating equivalence classes of Latin squares using a recursive, backtracking tree-search approach which attempts to eliminate redundancy in the search by only considering structures which have the potential to be completed to well-defined class representatives. This approach ensures that the enumeration algorithm only generates one Latin square from each of the classes to be enumerated, thus also generating a repository of class representatives of these classes. These class representatives may be used in conjunction with various well-known enumeration results from the theory of groups and group actions in order to determine the number of Latin squares in each class as well as the numbers of various kinds of subclasses of each class. This methodology is applied in order to enumerate various equivalence classes of SOLS and SOLSSOMs of orders up to and including order 10 and various equivalence classes of k-MOLS of orders up to and including order 8. The known numbers of distinct SOLS, idempotent SOLS and isomorphism classes generated by idempotent SOLS are verified for orders 4 n 9, and in addition the number of isomorphism classes, transpose-isomorphism classes and RC-paratopism classes of SOLS of these orders are enumerated. The search is further extended to determine the numbers of these classes for SOLS of order 10 via a large parallelisation of the backtracking treesearch algorithm on a number of processors. The RC-paratopism class representatives of SOLS thus generated are then utilised for the purpose of enumerating SOLSSOMs, while existing repositories of symmetric Latin squares are also used for this purpose as a means of validating the enumeration results. In this way distinct SOLSSOMs, standard SOLSSOMs, transposeisomorphism classes of SOLSSOMs and RC-paratopism classes of SOLSSOMs are enumerated, and a repository of RC-paratopism class representatives of SOLSSOMs is also produced. The known number of main classes of 2-MOLS of orders 3 n 8 are verified in this dissertation, and in addition the number of main classes of k-MOLS of orders 3 n 8 are also determined for 3 k n−1. Other equivalence classes of k-MOLS of order n that are enumerated include distinct k-MOLS and reduced k-MOLS of orders 3 n 8 for 2 k n − 1. Finally, a filtering method is employed to verify whether any SOLS of order 10 satisfies two basic necessary conditions for admitting a common orthogonal mate with its transpose, and it is found via a computer search that only four of the 121 642 class representatives of RC-paratopism classes of SOLS satisfy these conditions. It is further verified that none of these four SOLS admits a common orthogonal mate with its transpose. By this method the spectrum of resolved orders in terms of the existence of SOLSSOMs is improved in that the non-existence of such designs of order 10 is established, thereby resolving a longstanding open existence question in the theory of Latin squares. Furthermore, this result establishes a new necessary condition for the existence of a set of three mutually orthogonal Latin squares of order 10, namely that such a set cannot contain a SOLS and its transpose
  • Thumbnail Image
    Item
    Self-organising traffic control algorithms at signalised intersections
    (Stellenbosch : Stellenbosch University, 2015-04) Einhorn, Mark David; Van Vuuren, J. H.; Burger, A. P.; Stellenbosch University. Faculty of Economic and Management Sciences. Dept of Logistics
    ENGLISH ABSTRACT: The debilitating social, economic and environmental ramifications of traffic congestion are experienced in large cities the world over. The optimisation of traffic signal timings at signalised road intersections attempts to mitigate the extent of these adverse effects of traffic congestion by reducing the delay time experienced by vehicles in a transport network. Today, traffic signal control schemes may be classiffied into one of two main classes, namely fixed-time traffic signal control strategies, which are typically cyclic in nature, and vehicle-actuated traffic signal control strategies, which are typically acyclic in nature. Generally, cyclic control strategies tend to lack exibility, and are unable to adapt to short-term uctuations in traffic ow rates, resulting in green times that are either too long or too short. On the other hand, acyclic control strategies tend to lack coordination between intersections, resulting in vehicles being required to stop at the majority of signalised intersections they encounter. Self-organising traffic signal control has been proposed as an attractive alternative form of control which both exhibits exibility and facilitates a global coordination between intersections as a result of localised signal switching policies. Two examples of existing self-organising traffic signal control algorithms from the literature include an algorithm proposed by Lammer and Helbing in 2008 and an algorithm proposed by Gershenson and Rosenblueth in 2012. These algorithms have been shown to outperform both optimised fixed-time traffc signal control techniques as well as state-of-the-art vehicle actuated trffic signal control techniques, in terms of reducing vehicle delay time in a transport network. A draw-back of both of these self-organising approaches, however, is that their effective operation relies on carefully selected parameter values; poorly selected parameter values may render these algorithms very ineffectual. In this dissertation, three novel self-organising traffic signal traffic control algorithms are proposed. These three algorithms assume the use of existing radar detection sensors mounted at the intersection to provide the necessary input data. The radar detection sensors are capable of detecting and tracking individual vehicles approaching an intersection, providing real-time information pertaining to their physical dimensions, velocities, and ranges from the intersection in terms of both time and distance. The three traffic signal control algorithms are free of any user-specialised parameters, and instead rely solely on the data provided by the radar detection sensors to inform their signal switching policies. The first of these traffic signal control algorithms is inspired by inventory control theory, and draws parallels between the monetary costs typically considered in inventory control models and the delay time costs associated with traffic control at signalised intersections, which the algorithm attempts to minimise. The second novel traffic control algorithm is inspired by the chemical process of osmosis in which solvent molecules move unaided from a region where they are highly concentrated, across a semi-permeable membrane, into a region of high solute molecule concentration. The algorithm models vehicles approaching an intersection as solvent molecules and the physical space available for the vehicles to occupy once they have passed through the intersection as solute molecules. Following this analogy, the intersection is considered to be the semi-permeable membrane. The third traffic control algorithm is a hybrid of the inventory and osmosis-inspired algorithms together with an intersection utilisation maximisation technique, which prevents unnecessary or prolonged underutilisation of an intersection. The three novel trafficc control algorithms, together with the algorithms of Lammer and Helbing, and of Gershenson and Rosenblueth, as well as a fixed-time control algorithm, are implemented in a purpose-built microscopic traffic simulation modelling framework. Several measures are employed to evaluate the relative performances of the algorithms. These measures include the usual mean and maximum resulting delay times incurred by vehicles and the saturation level of the roadways in the transport network, as well as three novel performance measure indicators which include the mean number of stops made by vehicles, their mean normalised delay time and the mean normalised number of stops made. The algorithms are compared in the context of a linear corridor road network topology as well as a grid road network topology under various traffic ow conditions. The overall performance of the novel hybrid traffic signal control algorithm is found to be superior for the corridor road network topology, while the performance of the osmosis-inspired algorithm is found to be superior for the grid road network topology.