Deep infeasibility exploration method for vehicle routing problems

Piotr Beling, Piotr Cybula, Andrzej Jaszkiewicz, Przemysław Pełka, Marek Rogalski, Piotr Sielski

22nd European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoStar/EvoCOP), April 2022, Madrid, Spain

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.

Abstract

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.

Bibtex

@InProceedings{10.1007/978-3-031-04148-8_5,
author="Beling, Piotr
and Cybula, Piotr
and Jaszkiewicz, Andrzej
and Pe{\l}ka, Przemys{\l}aw
and Rogalski, Marek
and Sielski, Piotr",
editor="P{\'e}rez C{\'a}ceres, Leslie
and Verel, S{\'e}bastien",
title="Deep Infeasibility Exploration Method for Vehicle Routing Problems",
booktitle="Evolutionary Computation in Combinatorial Optimization",
year="2022",
publisher="Springer International Publishing",
address="Cham",
pages="62--78",
abstract="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.",
isbn="978-3-031-04148-8",
doi="10.1007/978-3-031-04148-8_5",
note="Part of the Lecture Notes in Computer Science book series (LNCS, volume 13222)"
}