An iterated local search with guided perturbation for the heterogeneous fleet vehicle routing problem with time windows and three-dimensional loading constraints

Ayad Turky, I. Moser, Aldeida Aleti

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    1 Citation (Scopus)

    Abstract

    An Australian company is faced with the logistics problem of distributing small quantities of fibre boards to hundreds of customers every day. The resulting Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Three-Dimensional Loading Constraints has to be solved within a single hour, hence the use of a heuristic instead of an exact method. In previous work, the loading was performed after optimising the routes, which in some cases generated infeasible solutions in need of a repair mechanism. In this work, the feasibility of the loading constraints is maintained during the route optimisation. Iterated Local Search has proved very effective at solving vehicle routing problems. Its success is mainly due to its biased sampling of locl optima. However, its performance heavily depends on the perturbation procedure. We trialled different perturbation procedures where the first one perturbs the given solution by moving deliveries that incur the highest cost on the objective function, whilst the second one moves deliveries that have been shifted less frequently by the local search in previous iterations. Our industry partner provided six sets of daily orders which have varied characteristics in terms of the number of customers, customer distribution, number of fibre boards and fibre boards’ sizes. Our investigations show that an instance becomes more constrained when the customer order contains many different board sizes, which makes it harder to find feasible solutions. The results show that the proposed perturbation procedures significantly enhances the performance of iterated local search specifically on such constrained problems.

    Original languageEnglish
    Title of host publicationArtificial Life and Computational Intelligence (ACALCI 2017)
    Subtitle of host publicationThird Australasian Conference, Geelong, VIC, Australia, January 31 - February 2, 2017, Proceedings
    EditorsMarkus Wagner, Xiaodong Li, Tim Hendtlass
    Place of PublicationCham, Switzerland
    PublisherSpringer
    Pages279-290
    Number of pages12
    ISBN (Electronic)9783319516912
    ISBN (Print)9783319516905
    DOIs
    Publication statusPublished - 2017
    EventAustralasian Conference on Artificial Life and Computational Intelligence (ACALCI) 2017 - Deakin University, Waterfront Campus, Geelong, Australia
    Duration: 31 Jan 20172 Feb 2017
    Conference number: 3rd
    http://www.acalci.net/2017/
    https://link.springer.com/book/10.1007/978-3-319-51691-2 (Springer Proceedings)

    Publication series

    NameLecture Notes in Artificial Intelligence
    PublisherSpringer
    Volume10142
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    ConferenceAustralasian Conference on Artificial Life and Computational Intelligence (ACALCI) 2017
    Abbreviated titleACALCI 2017
    CountryAustralia
    CityGeelong
    Period31/01/172/02/17
    OtherACACLI 2017 is co-located with the Australasian Computer Science Week (ACSW 2017), which will be held at Deakin University's Waterfront Campus, Geelong, which is about 70 kilometers west of Mebourne.

    3rd Australasian Conference on Artificial Life and Computational Intelligence, ACALCI 2017
    Internet address

    Keywords

    • 3-dimensional loading constraints
    • Iterated local search
    • Perturbation operator
    • Time windows
    • Vehicle routing problem

    Cite this

    Turky, A., Moser, I., & Aleti, A. (2017). An iterated local search with guided perturbation for the heterogeneous fleet vehicle routing problem with time windows and three-dimensional loading constraints. In M. Wagner, X. Li, & T. Hendtlass (Eds.), Artificial Life and Computational Intelligence (ACALCI 2017): Third Australasian Conference, Geelong, VIC, Australia, January 31 - February 2, 2017, Proceedings (pp. 279-290). (Lecture Notes in Artificial Intelligence; Vol. 10142). Springer. https://doi.org/10.1007/978-3-319-51691-2_24