How to include both origin and destination in your features?
Since your goal is to predict the price, I think it would be more useful to include features such as:


distance between origin and destination
whether origin and destination are in the same state/country/continent/area...


However the actual origin and destination might still be useful, at least the frequent ones, so it's worth experimenting. Those which appear only once or twice in your training data are unlikely to help the model, on the contrary they might cause overfitting. So you could filter out the origin/destination cities which appear less then $N$ times and keep the other ones. It's very likely that this will reduce the number of possible values a lot.