K-medoid Algorithm with Adaptive Large Neighborhood Search for the VRPTW

EasyChair Preprint no. 2596

Abstract

In this paper, we propose a new approach combining the k-medoid and the Adaptive Large Neighborhood Search (ALNS). The strategy fits into the class of algorithms cluster first - route second. Indeed, changing the way of clustering may change the efficiency of the solution of the Vehicle Routing Problem with Time Windows (VRP-TW). This fact, can be demonstrated by inserting a preprocessing step based on the K-medoid algorithm. In this stage, we subdivise the group of nodes of the general problem into small sets of customers which represent subproblems. Notice that the use of K-medoid is not restrictive and we can adopt of course other techniques such that K-means or density based spatial (DBS) clustering. Each subproblem is solved implicitly by applying the ALNS.

 

Keyphrases: ALNS, k-medoid, VRPTW

@Booklet{EasyChair:2596,
  author = {Mehdi Nasri and Imad Hafidi and Abdelmoutalib Metrane},
  title = {K-medoid Algorithm with Adaptive Large Neighborhood Search for the VRPTW},
  howpublished = {EasyChair Preprint no. 2596},

  year = {EasyChair, 2020}}