Einige der Verallgemeinerungen betrachten mehrere Handlungsreisende, während sich andere Varianten durch grundlegend veränderte Optimierungskriterien oder durch zusätzliche Nebenbedingungen von der klassischen Version unterscheiden.