Route Optimisation for the South African Post Office SoC LTD

Abstract

Post Offices globally are suffering from a decrease in revenues as a result of a decreasing customer base and an increasing delivery network. This is because of their obligation to deliver mail at the same price irrespective of location, usually mandated by governments. Therefore Post Offices need to look at making each aspect of their core business more efficient and effective. This project focuses on the methods used to route mail from Post Office depots to delivery points (such as houses). An investigation was completed on the current methods used by the South African Post Office to plan postmen routes. The method, which updated routes once every 2 to 3 years, was deemed inefficient as it lacked any flexibility and couldn't account for everyday eventualities such as postman absenteeism and vehicle breakdown. A literature review presented herein identified are routing as the most relevant branch of operations research for this project. Specifically it was found that modelling the problem as a Capacitated Arc Routing problem that was solved using a path scanning heuristic would make the best use of the students skill set, the time available and would approximate a good solution for the Post Office. This report describes the chosen solution method, the tests conducted to ensure its effectiveness and the final solutions generated. Finally a brief chapter on possible future work is given.