Premium
New dominance criteria for the generalized permanent labelling algorithm for the shortest path problem with time windows on dense graphs
Author(s) -
Cunha C.B.,
Swait J.
Publication year - 2000
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2000.tb00191.x
Subject(s) - successor cardinal , shortest path problem , computer science , dominance (genetics) , vehicle routing problem , algorithm , mathematical optimization , graph , mathematics , routing (electronic design automation) , theoretical computer science , mathematical analysis , biochemistry , chemistry , computer network , gene
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.