Method for Multi-class/category? I am having issues getting started with a multi class problem with multiple features and hoping someone could please point me in the right direction. 

I have data that is structured like this for training:

Item State Code1 Code2 Code3 Route
---  ---   ---   ---   ---   ---
item1 MI   A1    33    blue  Route1
item2 TX   A3    35    yellow Route2
item3 NM   A4    36    green  Route3
item4 NM   A4    37    green  Route3


Essentially I am trying to figure out where to even start. The goal is to know where to route the Items based on the features State, Code1,2, and 3. The route is dependent on a mix of the codes and state, and I want to build a model that says when I have code X, Y, Z and Color XX, then it is probably route 1 (some routes of course in the training data might have X, Y as codes and a different Z) 

I am assuming I will need to one-hot encode the features like the State and codes? But from there does anyone know of which type of model I should go for? I would assume a Neural Net of some kind, I've explored CNN's and Random Forrest.
My money would be on something much simpler like Naive Bayes.

In my experience for small data NB outperforms the more exotic methods.

Also, if you want to get more value out of your training data, try 10 fold cross validation