| Summary: | In this paper, we address the elementary shortest path problem with 2-dimensional loading constraints. The aim is to find the path with the smallest cost on a graph where the nodes represent clients whose items may have different heights and widths. Beyond its practical relevance, this problem appears as a subproblem in vehicle routing problems with loading constraints where feasible routes have to be generated dynamically. To the best of our knowledge, there are no results reported in the literature related to this problem. Here, we explore a variable neighborhood search approach for this problem. The method relies on constructive heuristics to generate feasible paths, while improved incumbents are sought in different neighborhoods of a given solution through a variable neighborhood search procedure. The resulting variants of the algorithm were tested extensively on benchmark instances from the literature. The results are reported and discussed at the end of the paper.
|
|---|