The effects of clustering on the medium and large-scale capacitated location-routing problem

Simple item page
dc.contributor.authorBuhrmann, Jacoba Hendrina
dc.date.accessioned2016-07-26T07:18:54Z
dc.date.available2016-07-26T07:18:54Z
dc.date.issued2016-07-26
dc.descriptionA thesis submitted to the Faculty of Engineering and the Built Environment, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the degree of Doctor of Philosophy. February 23, 2016en_ZA
dc.description.abstractThis work investigates the effectiveness of using clustering methods in solving various capacitated location-routing problems (CLRP) for medium- and large-scale datasets, with up to 20 000 datapoints. Different clustering methods as well as hybrid clustering methods are tested and compared. A new problem called the planar CLRP (plCLRP) is introduced. Based on the results from the clustering methods, cluster-based approaches are suggested to solve variants of the CLRP. These include the Hamiltonian p–median problem (HpMP), the planar CLRP (plCLRP), the concentrator discrete CLRP (cdCLRP) and the standard discrete CLRP (sdCLRP). A new method called the two-phased proportional regret ordering based unconstrained to constrained (PROBUC) method is also proposed to create capacitated clusters. The focus falls on finding effective non-exponential time algorithms that can be used to solve large-scale problems with good results. A full set of results for each problem are presented and comparisons are made with known results from the literature where possible. The PLRP (periodic location-routing problem) introduced by Prodhon and Prins (2008), is also investigated. A change in the current problem formulation, as provided by Prodhon (2011), is proposed to enforce single-source constraints across time horizon and limit the maximum number of vehicles. An approach to solve the PLRP, based on the cluster-based approaches to solve the discrete CLRPs, is suggested. The results of the cluster-based approach are compared to best-known solutions for existing PLRP instances given by Prodhon (2009a). A set of large scale PLRP instances are introduced, based on instances generated by Harks et al. (2013) for the sdCLRP.en_ZA
dc.identifier.urihttp://hdl.handle.net/10539/20701
dc.language.isoenen_ZA
dc.subject.lcshCluster analysis
dc.titleThe effects of clustering on the medium and large-scale capacitated location-routing problemen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
Abstract Thesis J.Buhrmann 23 Feb 2016.pdf
Size:
14.41 KB
Format:
Adobe Portable Document Format
Description:
Download
No Thumbnail Available
Name:
Thesis J.Buhrmann 23 Feb 2016.pdf
Size:
13.35 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
ETD Collection