Journal
OPERATIONS RESEARCH LETTERS
Volume 48, Issue 2, Pages 163-166Publisher
ELSEVIER
DOI: 10.1016/j.orl.2020.01.009
Keywords
Generalized traveling salesman problem; Precedence constraints; Sequential ordering problem; Branch-and-bound; Assignment problem; Minimum spanning arborescence problem
Categories
Funding
- Swedish Foundation for Strategic Research
Ask authors/readers for more resources
The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) combines the Generalized Traveling Salesman Problem (GTSP) and the Sequential Ordering Problem (SOP). We present a novel branching technique for the GTSP which enables the extension of a powerful pruning technique. This is combined with some modifications of known bounding methods for related problems. The algorithm manages to solve problem instances with 12-26 groups within a minute, and instances with around 50 groups which are denser with precedence constraints within 24 h. (C) 2020 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available