Naslov
A Branch and Bound Algorithm for the Sequential Ordering Problem

Autori
Karan, Mladen ; Skorin-Kapov, Nina

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proc. of 34rd International Convention on Information and Communication Technology, Electronics and Microelectronics MIPRO, CTI - Telecommunications and Information / - , 2011, 452-457

Skup
MIPRO 2011

Mjesto i datum
Opatija, Hrvatska, 23.05.2011. - 27.05.2011

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Sequential ordering problem ; Branch and bound ; Optimization

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Elektrotehnika

POVEZANOST RADA