Processing may take a few seconds...



Deep Infeasibility Exploration Method for Vehicle Routing Problems


[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee

Scientific discipline (Law 2.0)

[2.3] Information and communication technology

Year of publication


Chapter type

chapter in monograph / paper

Publication language


  • Metaheuristics
  • Combinatorial optimization
  • Transportation
  • Vehicle routing problem

EN We describe a new method for the vehicle routing problems with constraints. Instead of trying to improve the typical metaheuristics used to efficiently solve vehicle routing problems, like large neighborhood search, iterated local search, or evolutionary algorithms, we allow them to explore the deeply infeasible regions of the search space in a controlled way. The key idea is to find solutions better in terms of the objective function even at the cost of violation of constraints, and then try to restore feasibility of the obtained solutions at a minimum cost. Furthermore, in order to preserve the best feasible solutions, we maintain two diversified pools of solutions, the main pool and the temporary working pool. The main pool stores the best diversified (almost) feasible solutions, while the working pool is used to generate new solutions and is periodically refilled with disturbed solutions from the main pool. We demonstrate our method on the vehicle routing problems, with variants respecting time, vehicle capacity and fleet limitation constraints. Our method provided a large number of new best-known solutions on well-known benchmark datasets. Although our method is designed for the family of vehicle routing problems, its concept is fairly general and it could potentially be applied to other NP-hard problems with constraints.

Date of online publication


Pages (from - to)

62 - 78





Evolutionary Computation in Combinatorial Optimization : 22nd European Conference, EvoCOP 2022, Held as Part of EvoStar 2022, Madrid, Spain, April 20–22, 2022 : Proceedings

Presented on

22nd European Conference EvoCOP 2022, 20-22.04.2022, Madrid, Spain

Ministry points / chapter


Ministry points / conference (CORE)


This website uses cookies to remember the authenticated session of the user. For more information, read about Cookies and Privacy Policy.