This work describes the strategy of a Mexican package delivery firm to improve its on-time delivery level. This is based on the application of a transportation waste elimination approach on its routing operations on a detailed level. The company has an extended national network with an important private fleet. The current level of on-time delivery is estimated on 75% on average which is considered as poor by the management. The approach applied is built on the improvement of the Overall Vehicle Effectiveness (OVE) and/or Total Overall Vehicle Effectiveness (TOVE) indexes. These are extensions of the Overall Equipment Effectiveness (OEE) index used to improve manufacturing machine efficiency. Under these approaches wastes related to the availability, performance and quality efficiencies are identified and eliminated. A description of the application of the scheme and results from pilot projects is provided.