Subset selection routing : modelling and heuristics : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Operations Research at Massey University

Abstract

This theoretically practical thesis relates to the field of subset selection routing problems, in which there are a set of customers available to be serviced and decisions of which customers to service and how to carry out the service are required. We develop models for problems of this kind, particularly accounting for customer service in decision making. We consider possibilities that relate to not servicing customers, or servicing them poorly with respect to their desired service, and we model some possible implications of these decisions. We consider different constraints that may appear within these problems and exploit these within an overall model for a problem which we term the Maximum Collection Problem. We develop effective, generic solution methods for these problems and tailor specific routines to certain types of problem. We devise new methods for generating problems with specific characteristics and we use these to test the effectiveness of our methods. We extensively test our methods, identify shortcomings of existing methods and develop new methods for overcoming the identified weaknesses of the methods. We introduce a new version of subset selection routing problems, involving decision making in dynamic situations. We create models involving next day and same day service and develop fast, practical methods for obtaining effective solutions to these problems and test their effectiveness and robustness on a number of varied test problems.