Metaheuristic algorithms for solving the multi-depot arc routing problem

Abstract

The main objective of the present work is to elaborate the most effective algorithm for solving the Multi-Depot Arc Routing Problem (MDARP), taking the Randomized Sharp as base algorithm and starting point, and particularly to study different alternatives for developing the edge-to-depot assignment. Concrete applications of this problem are garbage collection, electricity meter reading, mail distribution and door-to-door selling. To accomplish this several edge-to-depot allocation strategies in conjunction with variations on the Randomized Sharp algorithm were implemented in the Java language and tested against one another and using the existing benchmarks for this problem.

El objetivo principal del presente trabajo es elaborar un algoritmo más eficaz para resolver el Problema de Enrutamiento de Arco de Multi-Depot (MDARP), tomando el Sharp Randomized como algoritmo de base y punto de partida, y particularmente para estudiar diferentes alternativas para desarrollar el algoritmo asignación de puntos. Las aplicaciones concretas de este problema son la recolección de basura, la lectura del contador de electricidad, la distribución del correo y la venta puerta a puerta. Para lograr esto varias estrategias de asignación de borde a depot en conjunción con variaciones en el algoritmo Sharp aleatorizado se implementaron en el lenguaje Java y se probaron entre sí y utilizando los puntos de referencia existentes para este problema.

L'objectiu principal del present treball és elaborar un algorisme més eficaç per a resoldre el Problema de Enrutamiento d'Arc de Multi-Depot (MDARP), prenent el Sharp Randomized com a algorisme de base i punt de partida, i particularment per a estudiar diferents alternatives per a desenvolupar l'algorisme assignació de punts. Les aplicacions concretes d'aquest problema són la recol·lecció de brossa, la lectura del comptador d'electricitat, la distribució del correu i la venda porta a porta. Per a aconseguir açò diverses estratègies d'assignació de vora a depot en conjunció amb variacions en l'algorisme Sharp aleatorizado es van implementar en el llenguatge Java i es van provar entre si i utilitzant els punts de referència existents per a aquest problema.