3. Electronic Theses and Dissertations (ETDs) - All submissions
Permanent URI for this communityhttps://wiredspace.wits.ac.za/handle/10539/45
Browse
5 results
Search Results
Item A survey of the most recent state-of-the art shortest path algorithms and their applications to different types of networks.(1991) Comninos, GerryThe title of this research report is a "A Survey of the most recent State of-the-Art Shortest path algorithms" One may ask what is the need and aim of this survey. During the decades of the 1970's and 1980's there has been considerable research and publication in shortest path algorithm. Each new publication is either a new and faster algorithm or survey of recent methods. ( Abbreviation abstract )Item Trajectory-based methods for solving nonlinear and mixed integer nonlinear programming problems(2016) Oliphant, Terry-LeighI would like to acknowledge a number of people who contributed towards the completion of this thesis. Firstly, I thank my supervisor Professor Montaz Ali for his patience, enthusiasm, guidance and teachings. The skills I have acquired during this process have infiltrated every aspect of my life. I remain forever grateful. Secondly, I would like to say a special thank you to Professor Jan Snyman for his assistance, which contributed immensely towards this thesis. I would also like to thank Professor Dominque Orban for his willingness to assist me for countless hours with the installation of CUTEr, as well as Professor Jose Mario Martinez for his email correspondence. A heartfelt thanks goes out to my family and friends at large, for their prayers, support and faith in me when I had little faith in myself. Thank you also to my colleagues who kept me sane and motivated, as well as all the support staff who played a pivotal roll in this process. Above all, I would like to thank God, without whom none of this would have been possible.Item Computational approaches in compressed sensing(2014-09-01) Woolway, MatthewThis thesis aims to provide a summary on computational approaches to solving the Compressed Sensing problem. The theoretical problem of solving systems of linear equations has long been investigated in academic literature. A relatively new field, Compressed Sensing is an application of such a problem. Specifically, with the ability to change the way in which we obtain and process signals. Under the assumption of sparse signals, Compressed Sensing is able to recover signals sampled at a rate much lower than that of the current Shannon/Nyquist sampling rate. The primary goal of this thesis, is to describe major algorithms currently used in the Compressed Sensing problem. This is done as a means to provide the reader with sufficient up to date knowledge on current approaches as well as their means of implementation, on central processing units (CPUs) and graphical processing units (GPUs), when considering computational concerns such as computational time, storage requirements and parallelisability.Item Algorithmic approaches to solving multi-period sales force and delivery vehicle master routing problems(2014-03-04) Rademeyer, Angela LizaMany companies are confronted with the problem of creating xed master routes for a period of more than a day either for geographically dispersed sales representatives or for eets of delivery vehicles which operate from a single depot. This involves the assignment of the company's customers to the sales reps/vehicles as well as visit pro les. For the problems de ned herein, these allocations of customers to a service group must remain xed for the duration of the planning period. A pro le represents a valid combination of visit days for a customer as well as a proportion of distributable workload (time for sales reps or mass for delivery vehicles) for each visit. For the sales rep problem, there is the option to solve for the optimal number of salesmen and their home locations if they are not known. Also, routes for the salesmen may include a new feature, sleep-outs, which are governed by rules indicating possible combinations of nights spent away from home as well as sleep-out locations. These combinatorial optimization problems are solved using exact and heuristic branch-and-bound algorithms which also assists in de ning the problem complexity. A genetic algorithm hybridised with problem speci c heuristics (i.e. a memetic algorithm) is also applied to problems which cannot be solved exactly in a reasonable amount of time. This evolutionary programming metaheuristic technique uses natural multi- level data structures and problem-sensitive genetic operators.Item Dynamic bulk freight train scheduling in an uncongested rail network(2013-08-06) Bennetto, Robert AndrewMany academic works in the train scheduling environment concentrate on optimizing movements of resources through the physical network. To opti- mize bulk freight lines, algorithms must provide a feasible schedule given the available resources, basic operational constraints and varying demand while ensuring resource allocations that minimise total cost. To be usable the al- gorithm must run within reasonable time limits. This dissertation focuses on the bulk freight train scheduling problem of full loads without track conges- tion but extends to cover operational constraints as well as exible resource allocation and hubs. A problem outline is given wherein the constraints and decision variables are well de ned followed by a review of current literature. An exact formation of the problem is given with benchmarking on small data sets. A genetic algorithm is used to solve for schedules on larger problem data sets. The algorithm was successfully implemented on the 60Mt Coal Line in South Africa which provided notable improvements in e ciencies. Discussion and results are provided.