An ACO hybrid metaheuristic for close–open vehicle routing problems with time windows and fuzzy constraints

• A new variant of VRPTW with close and open routes is introduced that responds to a real problem.
• The problem includes imprecision in capacity and time window constraints, which are modelled as fuzzy constraints.
• Fuzzy optimization approach is applied to address the problem modelled as a linear programming problem.
• A hybrid ACO metaheuristic procedure based on GRASP and VNS is provided to search for optimal solutions of the problem.
• The experiments show that the hybridization contributes to improve the performance.

The close–open vehicle routing problem is a realistic variant of the “classical” vehicle routing problem where the routes can be opened and closed, i.e. all the vehicles are not required to return to the depot after completing their service. This variant is a planning model that is a standard practice in business nowadays. Companies are contracting their deliveries to other companies that hire vehicles, and payment is made based on the distance covered by the vehicles. Available information on parameters in real world situations is also imprecise, and must be included in the optimization model and method. The aims of this paper are to formulate a model of this novel variant with time windows and imprecise constraints and to propose a fuzzy optimization approach and a hybrid metaheuristic for its solutions. The full proposal is applied to a real route planning problem with outsourcing, obtaining promising practical results. Customer demands and travel times are imprecise, thus capacity and time windows constraints are considered flexible and modelled as fuzzy constraints.

Figure optionsDownload as PowerPoint slide