Modeling and Solving the Multi-Objective Vehicle Routing Problem with Soft and Fuzzy Time Windows

Abstract

In the distribution field, distribution costs and customer service satisfaction are extremely important issues for enterprises. However, both the Vehicle Routing Problem with Soft Time Windows (VRPSTW) and the Vehicle Routing Problem with Fuzzy Time Windows (VRPFTW) have certain deficiencies in describing real-world scenarios. Therefore, this paper considers both soft time windows and fuzzy time windows, improving upon the traditional VRPSTW and VRPFTW models to establish a more comprehensive and realistic model called the Vehicle Routing Problem with Soft Time Windows and Fuzzy Time Windows (VRPSFTW). Secondly, to solve the relevant problems, this paper proposes a Directed Mutation Genetic Algorithm integrated with Large Neighborhood Search (LDGA), which fully utilizes the advantages of the Genetic Algorithm (GA) in the early stages and appropriately adopts removal and re-insertion operators from the Large Neighborhood Search (LNS). This approach not only makes efficient use of computational resources but also compensates for the weaknesses of crossover and mutation operators in the later stages of the genetic algorithm. Thereby, it improves the overall efficiency and accuracy of the algorithm and achieves better solution results. In addition, in order to solve multi-objective problems, this paper employs a two-stage solution approach and designs two sets of algorithms based on the principles of “cost priority” and “service-level priority”. Simulation experiments demonstrated that the algorithms designed in this study achieved a more competitive solving performance.

Keywords

• soft time windows
• fuzzy time windows
• multi-objective optimization
• vehicle routing problem with soft time windows and fuzzy time windows
• directed mutation genetic algorithm integrated with large neighborhood search
• two-stage algorithm