New models and solution approaches in continuous and discrete facility location

点击翻译按钮获取中文摘要

A main objective of the proposed research is to construct and study generalized versions of some classical location problems in the literature that may extend their usefulness in practice. An example is the "distributed p-median problem", which generalizes the classical p-median and was recently proposed by myself and two co-authors in a recent paper (JORS 2019). This new model imposes a distribution rule that allows flows to be directed to new facilities that are not necessarily the closest to the demand points (as in the classical model). We have formulated various discrete and continuous versions of the problem and derived interesting structural properties. For example, it is well known that facility locations for the classical (closest facility) problem may be restricted to the nodes of a network. However we have shown that this is not true for the general problem. We are now working on a network formulation, and developing special cases where the finite dominating set of generalized median points has a manageable size, and hence is more amenable to solution. We also plan to extend the study to other problem classes such as the p-centre problem for locating emergency facilities. This work may also lead to useful applications in the design of supply chains. Another area of research will advance previous work supported by NSERC on approximate methods (heuristics) for solving global and combinatorial optimization problems with an emphasis on location models. A specific focus will be on improving our understanding of the topology (or landscape) of the solution space generated by different local search operators and different qualities of starting solutions. We intend to conduct empirical studies on some classical problems that will enable us to empirically evaluate the relative distances between local optima. This will provide insights on setting parameter values for various meta-heuristics, such as the 'shaking' parameter in variable neighborhood search (VNS). A related area I am working on with colleagues in Europe involves a "less is more" philosophy, which strives for simple designs instead of the current trend in the literature of increasing complexity of heuristics. Another interesting phenomenon relates to the convergence rate of local search methods. Preliminary results we have show that slowing the rate can lead to better quality solutions by altering the path traveled in the solution space.  Another area of research deals with the location of hubs on a network, which has many important applications. Here I am working with another team of colleagues from Europe on applying VNS to solve some classical versions of this problem, all of which assume that the triangle inequality holds. This strong assumption results in at most two intermediary hubs along any path connecting source to destination nodes. We recently proposed a new "flow" model that eliminates this restriction, and intend to work on more efficient formulations of this type.