New dominance criteria for the generalized permanent labelling algorithm for the shortest path problem with time windows on dense graphs

This paper describes state-dominance criteria for the Generalized Permanent Labelling Algorithm (GPLA) for solving the Shortest Path Problem with Time Windows on dense graphs, which occurs as a subproblem of a vehicle routing problem. These criteria markedly improve its performance. One of the criteria we propose is based on a backward-looking test at the destination node. The other is a dominance test for the label being treated, which avoids the generation of successor states from dominated labels. Both are possible due to a new order of storing the labels for a given node within each bucket: the generated temporary labels are stored and later treated in decreasing service time order and increasing cost order. This order of label treatment, allied with the suggested dominance criteria, results in a significant time execution performance improvement with respect to the basic dense-graph GPLA.