The effects of clustering on the medium and large-scale capacitated location-routing problem
Date
2016-07-26
Authors
Buhrmann, Jacoba Hendrina
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This 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.
Description
A 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, 2016