Transformations for Variants of the Travelling Salesman Problem and Applications
A Master of Science thesis in Engineering Systems Management by Mustafa Jamil Assaf entitled, "Transformations for Variants of the Travelling Salesman Problem and Applications," submitted in April 2017. Thesis advisor is Dr Malick Ndiaye. Soft and hard copy available.
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | doctoralThesis |
| منشور في: |
2017
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | http://hdl.handle.net/11073/8845 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513443745234944 |
|---|---|
| author | Assaf, Mustafa Jamil |
| author_facet | Assaf, Mustafa Jamil |
| author_role | author |
| dc.contributor.none.fl_str_mv | Ndiaye, Malick |
| dc.creator.none.fl_str_mv | Assaf, Mustafa Jamil |
| dc.date.none.fl_str_mv | 2017-05-24T08:16:20Z 2017-05-24T08:16:20Z 2017-04 |
| dc.format.none.fl_str_mv | application/pdf |
| dc.identifier.none.fl_str_mv | 35.232-2017.06 http://hdl.handle.net/11073/8845 |
| dc.language.none.fl_str_mv | en_US |
| dc.subject.none.fl_str_mv | Travelling Salesman Problem (TSP) Multi Depot Multiple Travelling Salesmen Problem (MmTSP) Depot-less Travelling Salesman Problem (DTSP) Duplicated and Dummy Depots Transformation |
| dc.title.none.fl_str_mv | Transformations for Variants of the Travelling Salesman Problem and Applications |
| dc.type.none.fl_str_mv | info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/doctoralThesis |
| description | A Master of Science thesis in Engineering Systems Management by Mustafa Jamil Assaf entitled, "Transformations for Variants of the Travelling Salesman Problem and Applications," submitted in April 2017. Thesis advisor is Dr Malick Ndiaye. Soft and hard copy available. |
| format | doctoralThesis |
| id | aus_716fa17970fb454e341f2ab01b6c5a5f |
| identifier_str_mv | 35.232-2017.06 |
| language_invalid_str_mv | en_US |
| network_acronym_str | aus |
| network_name_str | aus |
| oai_identifier_str | oai:repository.aus.edu:11073/8845 |
| publishDate | 2017 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Transformations for Variants of the Travelling Salesman Problem and ApplicationsAssaf, Mustafa JamilTravelling Salesman Problem (TSP)Multi Depot Multiple Travelling Salesmen Problem (MmTSP)Depot-less Travelling Salesman Problem (DTSP)Duplicated and Dummy DepotsTransformationA Master of Science thesis in Engineering Systems Management by Mustafa Jamil Assaf entitled, "Transformations for Variants of the Travelling Salesman Problem and Applications," submitted in April 2017. Thesis advisor is Dr Malick Ndiaye. Soft and hard copy available.The Travelling Salesman Problem (TSP) is a well-known problem in the operations research field. This research focuses on solving variants of the TSP through the use of proper transformations, which allows the use of existing solution approaches and algorithms. In this thesis, a comprehensive review with graphical illustrations is provided for the multiple Travelling Salesmen problem (mTSP) and the Multi Depot multiple Travelling Salesmen Problem (MmTSP) transformations that are available in the literature. Furthermore, several variants were solved for the MmTSP such as the Fixed Destination MmTSP, Non-Fixed Destination MmTSP and the Open Path MmTSP through formulated transformations based on duplicated and dummy depots. Solving mTSP and MmTSP variants through duplicating the depots is very traditional, while the use of dummy nodes is not common. We proved that the proposed transformations yield the same optimal solutions for the different variants. Then, numerical testing was used to validate the transformations. Also, a new variant of the TSP is introduced and the Mixed Integer Linear Programming (MILP) formulation is provided. In this variant, salesmen are allowed to start from any city, unlike the traditional TSP and its variants where salesmen are bind to start from a predetermined node. The proposed solution is done by adding dummy nodes that serve as depots to the regular TSP problem. We refer to this model as the Depot-less Travelling Salesmen Problem (DTSP). For the validation of the work, the model is used to solve an already existing problem from the online TSP library via an optimization software. Later, the proposed model is applied to solve supervisors' allocation problem and a clustering problem. Our results confirm that both the transformed and the original graphs yield the same answer, which is the main purpose of using transformation.College of EngineeringDepartment of Industrial EngineeringMaster of Science in Engineering Systems Management (MSESM)Ndiaye, Malick2017-05-24T08:16:20Z2017-05-24T08:16:20Z2017-04info:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/doctoralThesisapplication/pdf35.232-2017.06http://hdl.handle.net/11073/8845en_USoai:repository.aus.edu:11073/88452025-06-26T12:33:00Z |
| spellingShingle | Transformations for Variants of the Travelling Salesman Problem and Applications Assaf, Mustafa Jamil Travelling Salesman Problem (TSP) Multi Depot Multiple Travelling Salesmen Problem (MmTSP) Depot-less Travelling Salesman Problem (DTSP) Duplicated and Dummy Depots Transformation |
| status_str | publishedVersion |
| title | Transformations for Variants of the Travelling Salesman Problem and Applications |
| title_full | Transformations for Variants of the Travelling Salesman Problem and Applications |
| title_fullStr | Transformations for Variants of the Travelling Salesman Problem and Applications |
| title_full_unstemmed | Transformations for Variants of the Travelling Salesman Problem and Applications |
| title_short | Transformations for Variants of the Travelling Salesman Problem and Applications |
| title_sort | Transformations for Variants of the Travelling Salesman Problem and Applications |
| topic | Travelling Salesman Problem (TSP) Multi Depot Multiple Travelling Salesmen Problem (MmTSP) Depot-less Travelling Salesman Problem (DTSP) Duplicated and Dummy Depots Transformation |
| url | http://hdl.handle.net/11073/8845 |