Policy learning and nested partitions optimization for resource allocation problems.

摘要

Many management problems in nowadays, such as the Local Pickup and Delivery Problem (LPDP), Discrete Facility Location Problem (DFLP), refer to the allocation of certain rare resources. Proper resource allocation can generate huge economic impacts. In this thesis, we use data mining and optimization methods to address resource allocation problems.;In many operational level resource allocation problems, proper policies for the resource-task assignment can be further developed into good allocation decisions. Data mining can be used to learn current resource-task assignment policies from historical data, which is promising in dealing with complex. A Data Mining-Based Decision System (DMBDS) framework is developed in Chapter 2. This DMBDS is successfully applied to LPDP, and lots of labor costs can be saved in dispatching.;Also, many resource allocation problems can be formulated into optimization problems which can be difficult to solve. Nested Partitions (NP) is previously developed to solve large-scale optimization problems. In this thesis, further methodological development of NP method is presented.;In Chapter 3, we invent the Hybrid Nested Partitions and Mathematical Programming (HNP-MP) approach for large-scale discrete optimization. This approach can provide approximate solutions efficiently, and in the meantime can easily handle different kinds of constraints. In this thesis, HNP-MP approach is further applied to LPDP and DFLP, and good performance is obtained.;In Chapter 4, we address the LPDP with stochastic loads. In this problem, there are many uncertain loads needed to be taken into account. We build the mathematical models for this stochastic LPDP with probabilistic objectives. We show that with maximizing profit expectation, the stochastic LPDP can be re-written as a deterministic LPDP. We further extend the FINP-MP approach to solve stochastic LPDP with more complicated objectives. Our experiment confirms the efficiency of the proposed algorithm and the benefits of considering these stochastic loads.;In Chapter 5, we propose the research direction of predicting NP solution value. The global optimum embedded prediction approach is developed. This approach is general and fast, and can provide useful prediction results, which is supported by the computational tests. Future research prospects are also discussed in this chapter.