Applying the Genetic Algorithm to Solving the Heterogeneous Vehicle Routing Problem Considering Service Costs and Stability

103

This study uses the genetic algorithm to explore the heterogeneous vehicle routing problem (HVRP). The main purpose is to construct a problem solving software for the reference of related industries. In addition to service costs, this study also contains the concept of service stability. Furthermore, this study blends rule of thumb into the calculation to avoid dramatic change in the path. This study develops a fuzzy multi-objective linear programming model, combining genetic algorithms and membership functions. To avoid gene repeat during chromosome mating, the structure of our genetic algorithm is based on the parthenogenesis genetic algorithm proposed by Chang and Yeh (2007). In view of the fact that using a random approach to generating an initial solution leads to poor results, due to the objective of service stability, this study adds a function of initial stable rate and uses the rule of thumb to generate new initial population. In addition, fuzzy multi-objective is added to the fitness function to calculate the objective functions of two different units. The solutions are then converted into the membership functions to determine the quality of chromosomes. This study further tests eight instances of HVRP benchmark instances constructed by Golden et al. (1984) to verify the model’s range of applications. The results show that the model has good performance with regard to service costs and stability. In addition, adjusting the initial stable rate can affect the results tending to the objective of service costs or service stability. The findings provide practical reference to the related industries.