Locomotive Routing Problem Using a Hybrid Genetic Algorithm

This paper aims to solve a locomotive routing through a rail network that is important for railway companies, in view of the high cost of operating locomotives. The locomotive routing problem finds the least cost routes to assign a set of locomotives locating in a central depot to a set of trains in a pre-planned train schedule so as to provide them with sufficient power to haul the trains from the origins to their destinations. In this research the well known vehicle routing problem with time windows is considered to be the basis for modeling the locomotive routing problem. Vehicle routing problem with time windows (VRPTW) is an important variant of vehicle routing problem (VRP) with adding time windows constraints to the model. In this problem the vehicles that are located a depot must serve a number of customers within predefined soft/hard time windows at minimum cost, without violating the capacity and total trip time constraints for each vehicle. This paper first reviews the literature of VRPTW and locomotive routing problem and after defining the locomotive routing model, designs an efficient genetic algorithm with special operators to solve it. In the proposed genetic algorithm part of the initial population is initialized randomly and part is initialized using Push Forward Insertion Heuristic (PFIH) method. Having non-random part of the population greatly reduces the time for the solution to converge, and having a random part prevents sticking to a local optimum and not exploring the complete solution space. Candidate solutions for mating are selected using the tournament selection that in which two identical (through differently ordered) copies of the population is kept and in every generation, adjacent chromosomes are compared in one copy of the population pair by pair, and one chromosome with best fitness value is selected to insert to the mating pool. Then this procedure is proceeding with the second copy of the population to select the other half of the chromosomes. The proposed genetic algorithm employs two kinds of crossover operators namely heuristic and merge crossover that they tries to produced solutions with better time and distance travel cost. Also, the mutation schemes that are used in suggestive algorithm are swap node and swap sequence that they applied on chromosomes with special mutation probability scheme which changes the mutation probability as the standard deviation of the population fitness changes.The suggestive genetic algorithm uses a famous local heuristics namely λ-interchange mechanism to search the neighborhood and larger area of solution space and also make improvements on produced solutions. This mechanism incorporates two strategies namely one-interchange (FB) and two-interchange (GB) to search for better routing solutions. The former tries to find the first better solution in short time and the latter finds the best solutions during some changes. Also at the end of each generation, elitism and recovery strategy is used to keep a few numbers of good individuals. It is notable to mention that the algorithm reduces the exponential computational complexity of the problem to a polynomial one which is an advantage for the solution algorithm. Two different scenarios are presented and their results are compared. To check the validity of the method, results gained by the algorithm are compared with the ones from an optimizer solver. Moreover, a test problem with small size is solved step by step according to suggestive method to clarify the concept of the model. The results indicate good quality and time saving of the method.