A recognised brand in the logistic sector, Royal Mail is the market leader in delivering parcels to British homes. However, in a context of increasing parcel traffic and growing expectations, Royal Mail is always working to adjust its operations to improve customer satisfaction. Route optimisation tools can therefore bring substantial value by easing cost management and enhancing service efficiency. In this talk, I will introduce the Vehicle Routing Problem (VRP) and show how this NP-hard combinatorial problem, despite being conceptually simple, is computationally difficult to solve.One leading approach implements heuristics from Operational Research and I will demonstrate how these can be used in an Agile Data Science working environment to develop an interactive software. While demonstrating this tool, I will show how the output of an iterative process of cost minimisation allows us to build parcel-sorting and delivery-ordering recommendations for an efficient management of this service.