{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/20769"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/20769","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"Distributed Vehicle Routing Approximation","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.","abstract_html":"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 <span class=\"etd-inline-math\">O(n . (\\rho)<sup>1/n</sup> .log(n+m))</span>, 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.","abstract_has_math":true,"creators":["Krishnan, Akhil"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computing and Software","school":null,"contributors":[],"advisors":["Bonakdarpour, Borzoo"],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017","date_published":"2017","updated_at":"2026-11-19T05:55:01Z","subjects":["VRP, NP-Complete, Distributed"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/22846"],"render_values":[{"text":"https://doi.org/10.71548/22846","href":"https://doi.org/10.71548/22846","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11375/20769","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/11375/20769","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F20769","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Bonakdarpour, Borzoo"]},{"key":"dc:contributor.department","label":"Department","values":["Computing and Software"]},{"key":"dc:creator","label":"Author","values":["Krishnan, Akhil"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2016-11-03T14:51:38Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2016-11-03T14:51:38Z"]},{"key":"dc:date.issued","label":"Date","values":["2017"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["VRP, NP-Complete, Distributed"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11375/20769","https://doi.org/10.71548/22846"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Distributed Approximation"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.abstractgeneral","label":"General Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science (MSc)"]},{"key":"dc:title","label":"Title","values":["Distributed Vehicle Routing Approximation"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Bonakdarpour, Borzoo"],"dc:contributor.department":["Computing and Software"],"dc:creator":["Krishnan, Akhil"],"dc:date.accessioned":["2016-11-03T14:51:38Z"],"dc:date.available":["2016-11-03T14:51:38Z"],"dc:date.issued":["2017"],"dc:description":["Distributed Approximation"],"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."],"dc:description.abstractgeneral":["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."],"dc:description.degree":["Master of Science (MSc)"],"dc:identifier.uri":["http://hdl.handle.net/11375/20769","https://doi.org/10.71548/22846"],"dc:language.iso":["en_US"],"dc:subject":["VRP, NP-Complete, Distributed"],"dc:title":["Distributed Vehicle Routing Approximation"],"dc:type":["Thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-19T05:55:01Z"}