Distributed Approximation / 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. / Thesis / Master of Science (MSc) / 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.
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/20769 |
| Date | January 2017 |
| Creators | Krishnan, Akhil |
| Contributors | Bonakdarpour, Borzoo, Computing and Software |
| Source Sets | McMaster University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.002 seconds