A Branch and Bound Algorithm for the Sequential Ordering Problem (CROSBI ID 573329)
Prilog sa skupa u zborniku | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Karan, Mladen ; Skorin-Kapov, Nina
engleski
A Branch and Bound Algorithm for the Sequential Ordering Problem
The Sequential Ordering Problem (SOP) is the problem of finding the shortest hamiltonian path in a graph while satisfying given precedence constraints regarding the order in which the nodes are visited. This classical optimization problem has many real-world applications, particularly in production planning, scheduling and transportation. We propose a branch and bound- based approach which can be used to solve medium instances (up to 30 nodes) of the problem to optimality in reasonable time. It does not require any specialized software for solving Mixed Integer Linear programs (MILP) and performs well particularly for heavily-constrained instances. The performance of the algorithm is tested on benchmark problems found in the TSPLIB online library.
Sequential ordering problem ; Branch and bound ; Optimization
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
452-457.
2011.
objavljeno
Podaci o matičnoj publikaciji
Proc. of 34rd International Convention on Information and Communication Technology, Electronics and Microelectronics MIPRO, CTI - Telecommunications and Information
Podaci o skupu
MIPRO 2011
predavanje
23.05.2011-27.05.2011
Opatija, Hrvatska