Search: onr:"swepub:oai:research.chalmers.se:c4d28a0f-cf01-437a-9aec-089a61478962" >
Branch-and-bound fo...
Branch-and-bound for the precedence constrained generalized traveling salesman problem
-
- Salman, Raad, 1989 (author)
- Stiftelsen Fraunhofer-Chalmers Centrum för Industrimatematik (FCC),Fraunhofer-Chalmers Research Centre for Industrial Mathematics (FCC)
-
- Ekstedt, Fredrik (author)
- Stiftelsen Fraunhofer-Chalmers Centrum för Industrimatematik (FCC),Fraunhofer-Chalmers Research Centre for Industrial Mathematics (FCC)
-
- Damaschke, Peter, 1963 (author)
- Chalmers tekniska högskola,Chalmers University of Technology
-
(creator_code:org_t)
- Elsevier BV, 2020
- 2020
- English.
-
In: Operations Research Letters. - : Elsevier BV. - 0167-6377. ; 48:2, s. 163-166
- Related links:
-
https://doi.org/10.1...
-
show more...
-
https://research.cha...
-
https://research.cha...
-
https://research.cha...
-
show less...
Abstract
Subject headings
Close
- 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 hours.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Systemvetenskap, informationssystem och informatik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Information Systems (hsv//eng)
Keyword
- Minimum spanning arborescence problem
- Generalized traveling salesman problem
- Assignment problem
- Branch-and-bound
- Sequential ordering problem
- Precedence constraints
Publication and Content Type
- art (subject category)
- ref (subject category)
Find in a library
To the university's database