Department of Logistics

Permanent URI for this community

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

Browse

Browsing Department of Logistics by browse.metadata.advisor "Burger, A. P."

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    An evaluation of the efficiency of self-organising versus fixed traffic signalling paradigms
    (Stellenbosch : Stellenbosch University, 2012-03) Einhorn, Mark David; Van Vuuren, J. H.; Burger, A. P.; Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics.
    ENGLISH ABSTRACT: see item for full text
  • Thumbnail Image
    Item
    Non-cooperative games on networks
    (Stellenbosch : Stellenbosch University, 2013-03) Van der Merwe, Martijn; Van Vuuren, J. H.; Burger, A. P.; Hui, Cang; Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics.
    ENGLISH ABSTRACT: There are many examples of cooperation in action in society and in nature. In some cases cooperation leads to the increase of the overall welfare of those involved, and in other cases cooperation may be to the detriment of the larger society. The presence of cooperation seems natural if there is a direct bene t to individuals who choose to cooperate. However, in examples of cooperation this bene t is not always immediately obvious. The so called prisoner's dilemma is often used as an analogy to study cooperation and tease out the factors that lead to cooperation. In classical game theory, each player is assumed to be rational and hence typically seeks to select his strategy in such a way as to maximise his own expected pay-o . In the case of the classical prisoner's dilemma, this causes both players to defect. In evolutionary game theory, on the other hand, it is assumed that players have limited knowledge of the game and only bounded rationality. Games in evolutionary game theory are repeated in rounds and players are a orded the opportunity to adapt and learn as this repetition occurs. Past studies have revealed that cooperation may be a viable strategy if the prisoner's dilemma is placed in an evolutionary context, where the evolutionary tness of a strategy is directly related to the pay-o achieved by the player adopting the strategy. One of the mechanisms that promote the persistence of cooperation in the evolutionary prisoner's dilemma is structured interaction between players. A mathematical framework for representing the evolutionary prisoner's dilemma (ESPD) is developed in this thesis. The mathematical framework is used to undertake an analytical approach (i.e. avoiding the use of simulation) towards investigating the dynamics of the ESPD with a path, cycle, plane grid or toroidal grid as underlying graph. The objective of this investigation is to determine the likelihood of the emergence of persistent cooperation between players. The ESPD on a path or a cycle admits two fundamentally di erent parameter regions; large values of the temptation-to-defect parameter are not capable of inducing persistent cooperation, while small values of this parameter allow for the possibility of persistent cooperation. It is found that the likelihood of cooperation increases towards certainty as the order of the underlying graph increases if the underlying graph is a path or cycle. The state space of the ESPD with a plane or toroidal grid graph as underlying graph grows very quickly as a function of the graph order. The automorphism classes of game states are enumerated to determine exactly how fast the size of the state space of the game grows as a function of the order of the underlying graph. Finally, the dynamics of the ESPD is investigated for a grid graph as underlying graph (in cases where the state space is small enough) by means of constructing the corresponding state graphs of the ESPD.
  • 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
    On two combinatorial optimisation problems involving lotteries
    (Stellenbosch : University of Stellenbosch, 2010-03) Du Plessis, Andre; Van Vuuren, J. H.; Burger, A. P.; University of Stellenbosch. Faculty of Economic and Management Sciences. Dept. of Logistics.
    ENGLISH ABSTRACT: Suppose a lottery draw consists of forming a winning ticket by randomly choosing t m distinct numbers from a universal set Um = f1; : : : ;mg. Each lottery participant forms a set of tickets prior to the draw, each ticket consisting of n m distinct numbers from Um, and is awarded a prize if k minfn; tg or more numbers in at least one of his/her tickets matches those of the winning ticket. A lottery of this form is denoted by the quadruple hm; n; t; ki, and the prize is known as a k-prize. The participant's set of tickets is also known as a playing set. The participant may wish to form a playing set in such a way that the probability of winning a k-prize is at least 0 < 1. Naturally, the participant will want to minimise the cost of forming such a playing set, which means that the cardinality of the playing set should be as small as possible. This combinatorial minimisation problem is known as the incomplete lottery problem and was introduced by Gr undlingh [16], who also formulated a related problem called the resource utilisation problem. In this problem one attempts to select a playing set of pre-speci ed cardinality ` in such a way that the probability of winning a k-prize is maximised. Gr undlingh [16] studied the incomplete lottery problem and the resource utilisation problem in the special case where n = t. In this thesis both problems are considered in the general case where n 6= t. Exact and approximate solution methods are presented and compared to each other in terms of solution quality achieved, execution time and practical feasibility. The rst solution method involves a mathematical programming formulation of both problems. Using this solution method, both problems are solved for small lottery instances. An exhaustive enumeration solution method, which uses the concept of overlapping playing set structures [5, 16], is reviewed and used to solve both combinatorial optimisation problems for the same small lottery instances. The concept of an overlapping playing set structure is further explored and incorporated in an attempt to solve both combinatorial optimisation problems approximately by means of various metaheuristic solution approaches, including a simulated annealing algorithm, a tabu search and a genetic algorithm. The focus of the thesis nally shifts to a di erent problem involving lotteries. An investigation is conducted into the probability, P(N; ), of participants sharing a k-prize if a total of N tickets are purchased by participants of the lottery hm; n; t; ki. Special attention is a orded in this problem to the jackpot prize of the South African national lottery, Lotto, represented by the quadruple h49; 6; 6; 6i and how the value of P(N; ) is a ected by the way that participants select their playing sets.
  • 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.