ON THE DYNAMIC PROBLEM OF OPTIMAL SET PARTITIONING WITH FIXED CENTERS

Abstract

The article formulates and investigates a dynamic optimal set partitioning (OSP) problem with fixed centers, which belongs to the class of spatial distribution problems with dynamically changing parameters. A formal problem statement, solution algorithm, and results of a numerical experiment confirming the efficiency and accuracy of the proposed approach are presented. The relevance of the selected topic is driven by the wide applicability of optimal partitioning problems in dynamic formulations for solving applied tasks in logistics, resource management, service area planning, and other domains where cost depends on time. Unlike static model problems, in real-world conditions, the transportation cost between elements may vary over time, significantly affecting both the search for the optimal solution and the value of the objective functional. The study considers several transportation cost models, including linear, exponential, and random (stochastic), enabling improved adaptation of models to specific applied contexts.

To conduct the numerical experiment, specialized software was developed in Python, integrating modern numerical methods such as step-by-step optimization, modified gradient approaches, and graphical result analysis tools. The model is based on the classical formulation of the optimal partitioning problem with fixed centers but introduces temporal dependencies into cost coefficients, allowing the simulation of complex distribution scenarios with time as a factor. A comparative analysis of modeling results for both dynamic and static approaches was carried out, demonstrating the advantages of the dynamic formulation: higher accuracy, greater flexibility, and adaptability to changing problem conditions.

The computations were performed on a personal computer with the following configuration: Intel Core i7-12700K, 8 cores, 3.6 GHz; 32 GB DDR4 RAM; 2 TB SSD. The obtained results confirmed not only the effectiveness of the mathematical model but also the correctness of the implemented algorithms, additionally illustrated through graphical phase trajectories and visualizations of the resulting partitions.

Keywords: dynamic problem, optimal set partitioning, objective functional, phase trajectory, numerical methods, time dependence, Python.