Software vendors travel management decisions using an elitist nonhomogeneous genetic algorithm

Vendors supplying software need to travel various places for product installation, troubleshooting, maintenance, upgrading, and promoting new products. These problems can be classified under asymmetric traveling salesman problems. Also, they are NP-hard in nature. In this paper, a new class of asymmetric traveling salesman problems is studied in which travel times are stochastic. We consider travel times as double truncated lognormal random variable and obtain the deterministic equivalent of the stochastic problem. An elitist nonhomogeneous genetic algorithm is proposed to solve this problem. The genetic algorithm control parameters, crossover and mutation probabilities vary in each successive generation. The best chromosome having the minimum travel time, together with the optimum crossover and mutation probabilities are selected using an elitist strategy. It is proved that the proposed algorithm follows a nonhomogeneous Markov chain process and almost certainly converges to the population that contains the optimal solution. Two case examples are presented to demonstrate the usefulness of the proposed approach.