Distance Constrained Capacitated Vehicle Touting Problem For The Abuja Post Office Using Lexisearch Algorithm

Abstract

Transportation problems are generally modelled as vehicle routing problems (VRPs) since they consist of minimizing the overall cost while satisfying routing constraints and customers' orderings. In this paper, the mail delivery of the Nigerian Postal Services (NIPOST) is modeled as a distance- constrained capacitated variant (DCVRP) in order to address the problem of delay in mail delivery occurring frequently experienced in NIPOST. The Lexi-search algorithm was applied and implemented on the spreadsheet solver to solve the capacitated vehicle routing problem of Abuja Post Office. The algorithm was tested on Christofides Benchmark and found to perform well with computational analyses coded in c⁺⁺ and statistical analyses of goodness fit performed using R Software. The problem has been formulated as a mixed integer programming problem based on a modification of the Tompkin’s et al., model. Appropriate data was obtained from Abuja Post Office where the data is used to come up with the distance matrix. The annual cost savings for NIPOST using three vehicles is N1,950,054.66, N1,708,127.73 and N1,140,148.50 for N142, N163 and N213 per litre respectively. The annual cost savings for four vehicles, is N1,494,466.25, and therefore the purchse of a fourth vehicle will reduce delay in mail delivery though it might cost them more to aquire a new bus as already indicated. In the long run however, revenue will increase because of high patronage.