Please use this identifier to cite or link to this item:

http://hdl.handle.net/10609/66566
Title: Metaheuristic Algorithms for solving the Multi-Depot Arc Routing Problem
Author: Page Carro, Patricio
Others: Universitat Oberta de Catalunya
Keywords: Arc Routing Problem
Randomized Algorithms
Heuristics
Issue Date: 18-Jun-2017
Publisher: Universitat Oberta de Catalunya
Abstract: The Multi-depot Arc Routing Problem (MDARP) is a combinatorial optimization problem belonging to a family of related problems that have in common the objective of finding the optimal route for a vehicle or a fleet of vehicles in order to satisfy demand located at the nodes or along the edges of a graph. When the demand is located at nodes it is called a Vehicle Routing Problem (VRP) and when it is located along the edges it is called Arc Routing Problem (ARP). For the present work, the ARP problem is studied, enriched by having multiple starting and finishing nodes, called depots. This problem is known in literature as Multi-depot Arc Routing Problem (MDARP). The aim of the present work is to study algorithms for the solution of the MDARP and some of its variants using as base the Randomized SHARP algorithm from González et al. (2012). This base algorithm is a randomized Clarke & Wright Savings heuristic (Clarke and Wright (1964)) for the construction of the solutions. Several strategies for the allocation of edges to each available depot were studied and compared in their results and efficiency. According to the results, the assignment of edges to depots using a biased-randomized strategy combined with the Randomized Sharp algorithm, a splitting search, simulated annealing and a cache strategy gives competitive results compared to current benchmarks.
Language: English
URI: http://hdl.handle.net/10609/66566
Appears in Collections:Bachelor thesis, research projects, etc.

Share:
Export:
Files in This Item:
File Description SizeFormat 
180617_TFM_IngCompMat_PPAGE.doc2.18 MBMicrosoft WordView/Open

Items in repository are protected by copyright, with all rights reserved, unless otherwise indicated.