Retrieve user features in real time from UserId for prediction
I think most likely the return of your model wouldn’t be worth it given the amount of effort to generalize it enough. 


You may have millions of users, but each users need will probably too unique for generalization. I.e., everyone’s commute is so different that what you have learned from other users are probably not applicable to other users. (Unless during rush hours where most people are heading to the core business areas. You don’t need a model for that. )
The trained model will probably be marginally better than logging the users usage history. It probably isn’t worth the effort to train and process these data for what you can gain. 
Recent locations is probably good enough for most users and super easy to implement. Your model will probably have a hard time to predict the odd unusual trips anyway. 


You are probably better off storing the users current location and query the most likely destination. Or simply look at all the popular trip destinations from that location. A data base with proper index should be able to handle that