Large‐scale set partitioning problems: Some real‐world instances hide a beneficial structure

Abstract

In this paper we consider large‐scale set partitioning problems. Our main purpose is to show that real‐world set partitioning problems originating from the container‐trucking industry are easier to tackle in respect to general ones. We show such different behavior through computational experiments: in particular, we have applied both a heuristic algorithm and some exact solution approaches to real‐world instances as well as to benchmark instances from Beasley OR‐library. Moreover, in order to gain an insight into the structure of the real‐world instances, we have performed and evaluated various instance perturbations.

Didelės matematinės aibės dalijimo problemų sprendimas, nagrinėjant realius pavyzdžius

Santrauka. Nagrinėjamos didelių matematinių aibių dalijimo problemos. Autorių tikslas – atskleisti praktines matematinių aibių dalijimo problemas, kurių pasitaiko konteinerių vežimo versle. Aprašomi du eksperimentai, atlikti kompiuteriu. Atliekant pirmąjį eksperimentą, realiai aibės perdalijimo problemai spręsti buvo pritaikyti euristinis ir keli tikslūs sprendimo metodai. Atliekant antrąjį, tie patys metodai pritaikyti naudojant duomenis iš Beasley operacijų tyrimų bibliotekos. Gauti rezultatai palyginti, ir gauta naudingos informacijos apie realią matematinių aibių struktūrą.

Reikšminiai žodžiai: matematinės aibės dalijimas, konteinerių vežimo verslas, operacijų tyrimų biblioteka.

First Published Online: 21 Oct 2010

Keyword : set partitioning, Lagrangian relaxation, real-world instances, container-trucking industry, OR-library, instance perturbations