Greedy Algorithm and Model for Analysis of a Bus Fleet's Operations

Abstract

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.