A hybrid adaptive large neighborhood search algorithm applied to a lot-sizing problem

Laurent Flindt Muller, Simon Spoorendonk

    Research output: Book/ReportReportResearch

    288 Downloads (Pure)

    Abstract

    This paper presents a hybrid of a general heuristic framework that has been successfully applied to vehicle routing problems and a general purpose MIP solver. The framework uses local search and an adaptive procedure which choses between a set of large neighborhoods to be searched. A mixed integer programming solver and its built-in feasibility heuristics is used to search a neighborhood for improving solutions. The general reoptimization approach used for repairing solutions is specifically suited for combinatorial problems where it may be hard to otherwise design operations to define a neighborhood of a solution and to investigate the feasibility of elements in such a neighborhood. The hybrid heuristic framework is applied to the multi-item capacitated lot sizing problem with dynamic lot sizes, where experiments have been conducted on a series of instances from the literature. On average the heuristic solutions are within 0.2% of the previously best known solutions and we found new improved upper bounds for 3 out of 12 instances.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages12
    ISBN (Print)978-87-90855-64-2
    Publication statusPublished - 2010
    SeriesDTU Management 2010
    Number1

    Keywords

    • capacitated lot sizing problem with setup times
    • adaptive large neighborhood search

    Cite this