Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Greedy Algorithm and Model for Analysis of a Bus Fleet's Operations
Mini Dissertation (B Eng. (Industrial and Systems Engineering))--University of Pretoria, 2017.
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English English |
| Published: |
University of Pretoria. Faculty of Engineering, Built Environment and Information Technology. Dept. of Industrial and Systems Engineering
2019
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613655292444672 |
|---|---|
| access_status_str | Open Access |
| author | McGladdery, Duncan |
| author_browse | McGladdery, Duncan |
| author_facet | McGladdery, Duncan |
| author_sort | McGladdery, Duncan |
| collection | Thesis |
| dc_rights_str_mv | © 2017 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. |
| description | Mini Dissertation (B Eng. (Industrial and Systems Engineering))--University of Pretoria, 2017. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/68393 |
| institution | University of Pretoria (South Africa) |
| language | English English |
| last_indexed | 2026-06-10T12:39:35.842Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2019 |
| publishDateRange | 2019 |
| publishDateSort | 2019 |
| publisher | University of Pretoria. Faculty of Engineering, Built Environment and Information Technology. Dept. of Industrial and Systems Engineering |
| publisherStr | University of Pretoria. Faculty of Engineering, Built Environment and Information Technology. Dept. of Industrial and Systems Engineering |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/68393 Greedy Algorithm and Model for Analysis of a Bus Fleet's Operations McGladdery, Duncan Mini-dissertations (Industrial and Systems Engineering) Mini Dissertation (B Eng. (Industrial and Systems Engineering))--University of Pretoria, 2017. Bus Company (BUSCO) approached Fourier-E, an industrial engineering company, to develop and optimise the Duty Master for their Sowetan operations. The Duty Master is a scheduling blue print that dictates the operations and management of a company's bus eet. Through the manipulation of positioning routes and depot allocations, a Duty Master should minimise distances travelled and eet size. In doing so, operating costs are reduced. Fourier-E had already developed their own algorithm for BUSCO's Sowetan Duty Master, which had resulted in substantial savings in the number of busses required to complete all revenue routes and total distances travelled. However, the run-time of their model of approximately 20 minutes to generate a solution is a serious limitation and prohibitive for client use. The primary aim of this project was to develop an online user-friendly model to en- able BUSCO to rapidly solve their eet scheduling requirements. Speci cally, the new algorithm had to be capable of generating a solution for the Duty Master in less than ten seconds. To accommodate the reduction in run-time, Fourier-E speci ed that the devel- oped algorithm must generate a solution which is at least 80% as good as their existing one in terms of busses saved and positioning kilometres driven. The problem of developing the Duty Master can be modelled as a Mulit-Depot Vehi- cle Routing Problem with Pickup and Delivery, Time Windows and Intermediate Facili- ties (MDVRPPDTWIF). To solve the problem, a greedy-heuristic was developed, called \Greedy-Bin". Computational tests showed that the algorithm exceeds all Fourier-E's speci cations and performs particularly well in run speed, whch at 1.23 seconds, is 976 times faster than the existing approach. The Greedy Bin algorithm performs at 88% of Fourier-E's with regards to busses saved and 96.7% for kilometres saved. The Greedy-Bin algorithm met all validation criteria. In order for clients to access the algorithm, an online user interface was developed which enables rapid evaluation of various operatonal scenarios. To achieve this, ve variables that can be manipulated by the client were added to the model, namely: bus speed, revenue routes, loading bu er, distance bu er and day and night depot capacities. Model outputs are: the number of busses needed to complete all revenue routes, positioning distance, depot allocations and eet utilisation throughout the day. Manipulation of the Duty Master model also demonstrates its capacity to save on oper- ating expenses by generating alternative solutions for depot allocations. Additionally, the nancial implications of changing bus speeds and manipiulating loading and positioning bu ers are demonstrated. Finally, in an industry where tenders for new revenue routes are highly competitive, the model can be used to assess the potential nancial implications of adding new routes and in doing so, inform the decision of whether or not to tender for those routes. 2019-02-04T13:11:30Z 2019-02-04T13:11:30Z 2017 2017 Mini Dissertation http://hdl.handle.net/2263/68393 en en © 2017 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. PDF application/pdf University of Pretoria. Faculty of Engineering, Built Environment and Information Technology. Dept. of Industrial and Systems Engineering |
| spellingShingle | Mini-dissertations (Industrial and Systems Engineering) McGladdery, Duncan Greedy Algorithm and Model for Analysis of a Bus Fleet's Operations |
| title | Greedy Algorithm and Model for Analysis of a Bus Fleet's Operations |
| title_full | Greedy Algorithm and Model for Analysis of a Bus Fleet's Operations |
| title_fullStr | Greedy Algorithm and Model for Analysis of a Bus Fleet's Operations |
| title_full_unstemmed | Greedy Algorithm and Model for Analysis of a Bus Fleet's Operations |
| title_short | Greedy Algorithm and Model for Analysis of a Bus Fleet's Operations |
| title_sort | greedy algorithm and model for analysis of a bus fleet s operations |
| topic | Mini-dissertations (Industrial and Systems Engineering) |
| url | http://hdl.handle.net/2263/68393 |
| work_keys_str_mv | AT mcgladderyduncan greedyalgorithmandmodelforanalysisofabusfleetsoperations |