Malaysian Journal of Mathematical Sciences, December 2020, Vol. 14(S)
Special Issue: 2nd International Conference on Applied & Industrial Mathematics and Statistics 2019 (ICoAIMS 2019)
Routing Mail Delivery from a Single Depot with Multiple Delivery Agents
Rahman, A., Tan, H. I., Liew, W. and Shahruddin, N. S.
Corresponding Email: [email protected]
Received date: 15 January 2020
Accepted date: 30 July 2020
Abstract:
Optimising the distance covered during mail delivery by utilising multiple Travelling Salesman Problem (mTSP) models and techniques can simultaneously minimise operations cost and Greenhouse Gasses (GHG) emissions caused by the transportation part of the mail delivery process. The aim of this study is to solve a mail delivery problem with multiple delivery agents in an established mail delivery network and compare our optimised delivery route with the original delivery route. This study also aims to optimise the delivery route for different numbers of delivery agents to prepare for cases of employee shortage and vehicle breakdown. This study decomposes the mTSP into multiple separate TSPs by clustering nodes together using the \((k)\)-Means Clustering method and assigning a delivery agent to each cluster, subsequently solving each cluster of TSP using Genetic Algorithm. The results show that our method is able to provide a better route for the mail delivery system compared to the original route, with a reduction of 11.25% in distance, which would no doubt reduce the transportation-related GHG emissions.
Keywords: Multiple Travelling Salesman Problem, Travelling Salesman Problem, Genetic Algorithm, \((k)\)-Means Clustering
