A Hybrid Column Generation approach for an Industrial Waste Collection Routing Problem

Kristian Hauge, Jesper Larsen, Richard Martin Lusby, Emil Krapper

    Research output: Contribution to journalJournal articleResearchpeer-review

    617 Downloads (Pure)

    Abstract

    This paper presents a practical roll-on/roll-o_ routing (ROROR) problem arising in the collection of industrial waste. Skip containers, which are used for the waste col-lection, need to be distributed between, and collected from, a set of customers. Full containers must be driven to dump sites, while empty containers must be returned to the depot to await further assignments. Unlike, the traditional ROROR problem, where vehicles may transport one skip container at a time regardless of whether it is full or not, we consider cases in which a vehicle can transport up to eight containers, at most two of which can be full. We propose a Generalized Set Partitioning formulation of the problem and describe a hybrid column generation procedure to solve it. A fast Tabu Search heuristic is used to generate new columns. The proposed methodology is tested on nine data sets, four of which are actual, real-world problem instances. Results indicate that the hybrid column generation outperforms a purely heuristic approach in terms of both running time and solution quality. High quality solutions to problems containing up to 100 orders can be solved in approximately 15 minutes.
    Original languageEnglish
    JournalComputers & Industrial Engineering
    Volume71
    Issue number1
    Pages (from-to)10-20
    ISSN0360-8352
    DOIs
    Publication statusPublished - 2014

    Keywords

    • Routing
    • Rollon-Rollo
    • Waste collection
    • Column Generation
    • Metaheuristic

    Cite this