In this paper, a Modified Genetic Algorithm (MGA) is developed to solve Constrained Solid Travelling Salesman Problems (CSTSPs) in crisp, fuzzy, random, random-fuzzy, fuzzy-random and bi-random environments. In the proposed MGA, for the first time, a new 'probabilistic selection' technique and a 'comparison crossover' are used along with conventional random mutation. A Solid Travelling Salesman Problem (STSP) is a Travelling Salesman Problem (TSP) in which, at each station, there are a number of conveyances available to travel to another station. Thus STSP is a generalization of classical TSP and CSTSP is a STSP with constraints. In CSTSP, along each route, there may be some risk/discomfort in reaching the destination and the salesman desires to have the total risk/discomfort for the entire tour less than a desired value. Here we model the CSTSP with traveling costs and route risk/discomfort factors as crisp, fuzzy, random, random-fuzzy, fuzzy-random and bi-random in nature. A number of benchmark problems from standard data set, TSPLIB are tested against the existing Genetic Algorithm (with Roulette Wheel Selection (RWS), cyclic crossover and random mutation) and the proposed algorithm and hence the efficiency of the new algorithm is established. In this paper, CSTSPs are illustrated numerically by some empirical data using this algorithm. In each environment, some sensitivity studies due to different risk/discomfort factors and other system parameters are presented.