Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Fast local searches for the vehicle routing problem with time windows

Fast local searches for the vehicle routing problem with time windows Olli Braysy INFOR Nov A B M N F O R M Global pg FAST LOCAL SEARCHES FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS OLLI BRÀYSY SINTEF Applied Mathematics Department of Optimization P O Box Blindent N- Oslo Norway E-mail Olli Braysy sintef no ABSTRACT The purpose of this paper is to present new deterministic local searches for solving the vehicle routing problem with time windows The proposed algorithms are based on a new three-phase approach In the ?rst phase an initial solution is created with one of the two proposed route construction heuristics In the second phase a special local search operator based on ejection chains is used to reduce the number of routes Finally in the third phase well-known Or-opt exchanges are used to minimize the total distance of the routes The ?ndings of computational experiments indicate that the proposed methods arc competitive with the best approaches proposed earlier in the literature in terms of solution quality while being much faster Moreover the proposed algorithms may easily be used to create initial solutions for a wide variety of vehicle routing algorithms RÉSUMÉ L'objectif de cet article est de présenter de nouvelles recherches locales déterministes pour résoutire le problème de tournées de véhicules avec fenêtres de temps Les algorithmes proposés sont basés sur une nouvelle approche en trois étapes Dans la première étape une solution de départ est obtenue avec l'une des deux heuristiques de construction de route proposées Dans la seconde étape une recherche spéciale basée sur des cha? nes d'éjection est utilisée de manière à réduire le nombre de routes Finalement dans une troisième étape un voisinage classique Or-Opt est utilisé pour minimiser la longueur totales des routes Les résultats des calculs expérimentaux indiquent que les méthodes proposées sont en terme de qualité concurrentielles avec les meilleures approches proposées auparavant dans la littérature tout en étant nettement plus rapides En outre les algorithmes proposés peuvent facilement être utilisés pour obtenir des solutions initiales pour un large éventail d'algorithmes de tournées de véhicules INTRODUCTION In this paper we focus on the Vehicle Routing Problem w i t h Time Windows V R P T W an important problem occurring in many distribution systems To describe the VRPTW let G C A be a directed graph where C c ct cn is a vertex set and c c i ' is an arc set Vertex c denotes a depot and the remaining vertices o f C represent customer locations Each arc c Cy has an associated nonnegative distance d- and a nonnegative travel time r y The V R P T W consists o f designing a set o f least cost vehicle routes such that a Every route starts and ends at the depot c b Every customer of C excluding the depot is visited exactly once by exactly one vehicle c The total demand o f any vehicle route does not exceed the vehicle capacity