Sökning: 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 (författare)
- Stiftelsen Fraunhofer-Chalmers Centrum för Industrimatematik (FCC),Fraunhofer-Chalmers Research Centre for Industrial Mathematics (FCC)
-
- Ekstedt, Fredrik (författare)
- Stiftelsen Fraunhofer-Chalmers Centrum för Industrimatematik (FCC),Fraunhofer-Chalmers Research Centre for Industrial Mathematics (FCC)
-
- Damaschke, Peter, 1963 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
(creator_code:org_t)
- Elsevier BV, 2020
- 2020
- Engelska.
-
Ingår i: Operations Research Letters. - : Elsevier BV. - 0167-6377. ; 48:2, s. 163-166
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://research.cha...
-
https://research.cha...
-
https://research.cha...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Systemvetenskap, informationssystem och informatik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Information Systems (hsv//eng)
Nyckelord
- Minimum spanning arborescence problem
- Generalized traveling salesman problem
- Assignment problem
- Branch-and-bound
- Sequential ordering problem
- Precedence constraints
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas