Consistency between two outputs of a neural network I'm trying to fit a dense neural network based on tabular data input, where the outputs are two separate classification vectors, with one cross-entropy loss function for each.
Example: given a few input features, for a customer that visits a travel website with the intention of buying a train ticket, the model would predict both the destination of travel and the traveling class (1st class or 2nd class) that the customer is likely to buy.
Problem: it seems as if internally, the network was divided in two at some point in the hidden layers, and each sub-network got specialised in predicting one output vector, ignoring the other. This leads to an overall acceptable accuracy for each output, but the consistency between the two outputs leaves to be desired.

For example, for a given entry, the network would predict "London" and "1st Class", because independently, each output makes sense according to the input features, but there isn't a single training point where London and 1st class can be found together, simply because there isn't a 1st class option when travelling to London. The network seems to be completely devoid of any concern for the consistency between the two.
Example, if the passenger is an accountant, 35yo and departs from Brussels, the training set gives a clear winner for destination: London and, separately, also for class: 1st, and so this is what the network will tend to predict, despite this combination being totally absent.

Would there be any way to amend the network and/or the organisation of the loss functions so that the consistency between the two outputs would be taken into account, and the network would avoid combination of outputs that can't be found in the training set, and favor those that are?
More generally, what would be some good approaches to tackle this issue? Note that I would like to avoid resorting to manual rules down the line, if that is possible.

Cost function
In what way would your neural network be able to know that the 1st class with destination London is not feasible? How do you teach that to the network? In what way did you 'punish' the network during training for wrong predictions?
It is important that the training phase allows the network to train the desired features. In your question, you did not tell which cost function you used to train the model.
It is also not clear what type of output is created by your model and what you would desire from it. Do I guess correctly that the output is just a single class prediction? In that case, what class prediction would you favor in the example from the question.
Is 'London 2nd class' a better prediction than 'London 1st class'?
When this cost function only cares about a single error then it is gonna care less about combined errors. That might lead to your problem (I am assuming that this is how your cost function is created, but it is not clear).
Predicting London + 1st class will be wrong in the 89302 cases when the true value is Londen + 2nd class. But the choice to predict the 1st class instead of 2nd class might be rewarded in the 48516 + 41411 + 38186 + 35247 + 28512 cases when the true value is Paris/Rome/Berlin/Madrid/Rotterdam + 1st class (I am not sure, but I guess that your cost function is doing this).
You can punish the system for making predictions about 1st class when it is in London, but at the same time you reward 1st class predictions when the occur in other cities. So you are getting Londen 1st class as result.
Type of output
I mentioned earlier that I am guessing that your model is just giving a single class prediction. I am guessing this based on your situation as well as on the phrase

For example, for a given entry, the network would predict "London" and "1st Class"

If that is the case then you might consider to use a different type of output. Instead of predicting a single class you could have as output a vector of probabilities for all desired combinations of destinations and classes (as well as other aspects that you might have in your model). Then you could value the predictions and perform the training based on a likelihood function of a categorical distribution.
When you apply this model (some online shopping tool or some help for an airline company?) then it will not give a single class as output, but instead it could give a ranking of the top destinations.
Network structure
What kind of dense neural network do you have and how did your train it? It might be imaginable that there should be a node in some of those layers that gets trained to deal with the London + 2nd class case specifically. But, how many layers do you have, how many nodes per layer do you have, how did you do cross-valdiation?
It is imaginable that this error/false-prediction might occur. But it is difficult to say why and how exactly it occurs without details.
