Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/20769
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Bonakdarpour, Borzoo | - |
dc.contributor.author | Krishnan, Akhil | - |
dc.date.accessioned | 2016-11-03T14:51:38Z | - |
dc.date.available | 2016-11-03T14:51:38Z | - |
dc.date.issued | 2017 | - |
dc.identifier.uri | http://hdl.handle.net/11375/20769 | - |
dc.description | Distributed Approximation | en_US |
dc.description.abstract | The classic vehicle routing problem (VRP) is generally concerned with the optimal design of routes by a fleet of vehicles to service a set of customers by minimizing the overall cost, usually the travel distance for the whole set of routes. Although the problem has been extensively studied in the context of operations research and optimization, there is little research on solving the VRP, where distributed vehicles need to compute their respective routes in a decentralized fashion. Our first contribution is a synchronous distributed approximation algorithm that solves the VRP. Using the duality theorem of linear programming, we show that the approximation ratio of our algorithm is $O(n . (\rho)^{1/n} .log(n+m))$, where $\rho$ is the maximum cost of travel or service in the input VRP instance, $n$ is the size of the graph, and $m$ is the number of vehicles. We report results of simulations comparing our algorithm results with ILP solutions and a greedy algorithm. | en_US |
dc.language.iso | en_US | en_US |
dc.subject | VRP, NP-Complete, Distributed | en_US |
dc.title | Distributed Vehicle Routing Approximation | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | Computing and Software | en_US |
dc.description.degreetype | Thesis | en_US |
dc.description.degree | Master of Science (MSc) | en_US |
dc.description.layabstract | The Open Multi-Depot Vehicle Routing Problem(OMDVRP) problem is solved using an synchronous distributed algorithm and the approximation ratio is found and simulation results comparing the performance of ILP , greedy and the designed algorithm is done. | en_US |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
krishnan_akhil_finalsubmission201610_msc.pdf | 1.15 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.