A multi-level variable neighborhood search heuristic for a practical vehicle routing and driver scheduling problem

Min Wen, Emil Krapper, Jesper Larsen, Thomas K. Stidsen

    Research output: Book/ReportReportResearch

    4231 Downloads (Pure)

    Abstract

    This paper addresses an integrated vehicle routing and driver scheduling problem arising at the largest fresh meat producer in Denmark. The problem consists of a one-week planning horizon, heterogeneous vehicles, and drivers with predefi ned work regulations. These regulations include, among other things, predefined workdays, fixed starting time, maximum weekly working duration, break rule. The objective is to minimize the total delivery cost. The real-life case study is fi rst introduced and modelled as a mixed integer linear program. A multilevel variable neighborhood search heuristic is then proposed for the problem. At the first level, the problem size is reduced through an aggregation procedure. At the second level, the aggregated weekly planning problem is decomposed into daily planning problems, each of which is solved by a variable neighborhood search. At the last level, the solution of the aggregated problem is expanded to that of the original problem. The method is implemented and tested on real-life data consisting of up to 2000 orders per week. Computational results show that the aggregation procedure and the decomposition strategy are very effective in solving this large scale problem, and our solutions are superior to the industrial solutions given the constraints considered in this work.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages31
    ISBN (Print)978-87-90855-54-3
    Publication statusPublished - 2009
    SeriesDTU Management 2009
    Number9

    Keywords

    • driver scheduling
    • vehicle routing
    • node aggregation
    • variable neighborhood search

    Fingerprint Dive into the research topics of 'A multi-level variable neighborhood search heuristic for a practical vehicle routing and driver scheduling problem'. Together they form a unique fingerprint.

    Cite this