A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016)
In the Vehicle Routing Problem (VRP) we are given a set of demands that need to be delivered to a specified list of customers, and we are asked to assign vehicles to deliver the demands so that the corresponding cost of routes is minimized. The problem received great attention due to its many applic...
Saved in:
| Main Author: | |
|---|---|
| Format: | masterThesis |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10725/5342 https://doi.org/10.26756/th.2016.38 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513465809371136 |
|---|---|
| author | Kfoury, Muhib S. |
| author_facet | Kfoury, Muhib S. |
| author_role | author |
| dc.creator.none.fl_str_mv | Kfoury, Muhib S. |
| dc.date.none.fl_str_mv | 2016 2016-12-09 2017-03-09T09:42:01Z 2017-03-09T09:42:01Z 2017-03-09 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/5342 https://doi.org/10.26756/th.2016.38 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Lebanese American University |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Dissertations, Academic Lebanese American University -- Dissertations Vehicle routing problem |
| dc.title.none.fl_str_mv | A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016) |
| dc.type.none.fl_str_mv | Thesis info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/masterThesis |
| description | In the Vehicle Routing Problem (VRP) we are given a set of demands that need to be delivered to a specified list of customers, and we are asked to assign vehicles to deliver the demands so that the corresponding cost of routes is minimized. The problem received great attention due to its many applications in various fields such as logistics and transportation. Different types of the VRP have been proposed such as the Capacitated Vehicle Routing Problem (CVRP), where a designated single depot contains identical vehicles and the objective is to minimize the number of vehicles and the time taken for delivery, provided the total demand of supplies per vehicle does not exceed its capacity. CVRP is a well-known NP-complete problem. We consider heuristic methods that are based on two-phase algorithms. Each such algorithm starts by clustering the underlining network before proceeding into the route construction phase. We propose a three-stage hybrid heuristic approach consisting of a mixture of five algorithms that are run in parallel, differing only in the clustering stage. Experimental results on different benchmark datasets show that the proposed hybrid algorithm can outperform other existing heuristic methods, both in terms of number of vehicles and total distances traveled. In some cases, our algorithm found solutions that are better than the current best-known results, thereby breaking the records reported for some of the well-known benchmarks. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | LAURepo_ae3d3e3ee08c455f545b8ff1f6a9ab15 |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/5342 |
| publishDate | 2016 |
| publisher.none.fl_str_mv | Lebanese American University |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016)Kfoury, Muhib S.Dissertations, AcademicLebanese American University -- DissertationsVehicle routing problemIn the Vehicle Routing Problem (VRP) we are given a set of demands that need to be delivered to a specified list of customers, and we are asked to assign vehicles to deliver the demands so that the corresponding cost of routes is minimized. The problem received great attention due to its many applications in various fields such as logistics and transportation. Different types of the VRP have been proposed such as the Capacitated Vehicle Routing Problem (CVRP), where a designated single depot contains identical vehicles and the objective is to minimize the number of vehicles and the time taken for delivery, provided the total demand of supplies per vehicle does not exceed its capacity. CVRP is a well-known NP-complete problem. We consider heuristic methods that are based on two-phase algorithms. Each such algorithm starts by clustering the underlining network before proceeding into the route construction phase. We propose a three-stage hybrid heuristic approach consisting of a mixture of five algorithms that are run in parallel, differing only in the clustering stage. Experimental results on different benchmark datasets show that the proposed hybrid algorithm can outperform other existing heuristic methods, both in terms of number of vehicles and total distances traveled. In some cases, our algorithm found solutions that are better than the current best-known results, thereby breaking the records reported for some of the well-known benchmarks.N/A1 hard copy: xii, 66 leaves; 31 cm. available at RNL.Bibliography : leaves 63-66.Lebanese American University2017-03-09T09:42:01Z2017-03-09T09:42:01Z20162017-03-092016-12-09Thesisinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/masterThesishttp://hdl.handle.net/10725/5342https://doi.org/10.26756/th.2016.38http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.phpeninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/53422021-03-19T10:03:19Z |
| spellingShingle | A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016) Kfoury, Muhib S. Dissertations, Academic Lebanese American University -- Dissertations Vehicle routing problem |
| status_str | publishedVersion |
| title | A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016) |
| title_full | A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016) |
| title_fullStr | A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016) |
| title_full_unstemmed | A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016) |
| title_short | A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016) |
| title_sort | A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016) |
| topic | Dissertations, Academic Lebanese American University -- Dissertations Vehicle routing problem |
| url | http://hdl.handle.net/10725/5342 https://doi.org/10.26756/th.2016.38 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php |