An Adaptive Large Neighborhood Search-based Three-Stage Matheuristic for the Vehicle Routing Problem with Time Windows

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    311 Downloads (Pure)

    Abstract

    The Vehicle Routing Problem with Time Windows (VRPTW) consist of determining a set of feasible vehicle routes to deliver goods to a set of customers using a hierarchical objective; first minimising the number of vehicles used and, second, the total driving distance.
    A three-stage method is proposed for the VRPTW. The first stage aims at minimising the number of vehicle used, whereas the second and third phase aims at minimising the travel distance. The first stage maintains an ejection pool with temporarily unserved customers, and tries to insert these customer into the existing solution. If a new candidate solution for the minimum number of vehicles is found, a route is removed and the customers from the route is placed in the ejection pool. If the heuristic terminates without finding a new candidate solution where all customers are served, the first stage returns the last found candidate solution that serves all the customers. The second stage usesan Adaptive Large Neighborhood Search (ALNS) algorithm to minimise the travel distance, during the second phase all of the generated routes are considered by solving a set cover problem. The ALNS algorithm uses 4 destroy operators, 2 repair operators and a local search method. The third stage isa Branch-Cut-and-Price (BCP) matheuristic which considers a reduced problem instance, with onlya small subset of the total arcs. This work contributes to the existing literature by integrating a set cover model with ALNS and by using BCP as a post-optimization procedure.
    Original languageEnglish
    Publication date2015
    Number of pages4
    Publication statusPublished - 2015
    EventOdysseus 2015; Sixth International Workshop on Freight Transportation and Logistics - Ajaccio, Corsika, France
    Duration: 1 Jun 20165 Jun 2016

    Conference

    ConferenceOdysseus 2015; Sixth International Workshop on Freight Transportation and Logistics
    CountryFrance
    CityAjaccio, Corsika
    Period01/06/201605/06/2016

    Keywords

    • Vehicle Routing Problem
    • Large Neighbourhood Search
    • Matheuristic
    • Set Cover Problem
    • Operations Research

    Cite this

    Christensen, J. M., & Røpke, S. (2015). An Adaptive Large Neighborhood Search-based Three-Stage Matheuristic for the Vehicle Routing Problem with Time Windows. Abstract from Odysseus 2015; Sixth International Workshop on Freight Transportation and Logistics, Ajaccio, Corsika, France.