It is of interest to federal and state agencies to develop an advanced uniform method for estimation of vehicle miles traveled (VMT) on local roads which can be used as a guideline for agencies nationwide. The purpose of this study is to propose advanced innovative approaches for estimating VMT on local roads and analyze the feasibility of applying these methods. The paper presents a methodology and procedure for estimating local road VMT using GPS vehicle trajectory data and an all-street road network and expands these methodologies and results to determine the minimum required GPS sample size. The Federal Highway Administration and other transportation agencies may consider using these methodologies as a future guide to update VMT estimates with minimal additional cost requirements. The key finding of the research is that it is feasible to use new GPS vehicle trajectory data to estimate VMT on non-Federal Aid System roadways. The sample size of this data allows the application of this new method across the nation. The accuracy of this method was tested for the State of Maryland. Once such statewide GPS data is obtained by a given state, the methodology can be easily applied to that state as well.