SOLVING THE PROBLEM OF VEHICLE ROUTING WITH MULTIPLE CENTERS, DYNAMIC ADDITION OF TARGET OBJECTS AND PRESCRIPTIVE DEADLINES FOR THEIR VISITS SOLVING THE DYNAMIC ROUTING PROBLEM

Abstract

The paper considers the problem of vehicle routing with alternating objects of two types and several collection centers. The problem is defined as dynamic, i.e. the target objects do not appear all at once, but after some predetermined time from the beginning of the movement of mobile objects. In addition, there are prescriptive deadlines - time points before which it is desirable to visit the target objects. Four target functions aimed at minimizing the following indicators are considered: the time to complete the visit of all target objects, the number of violations of the directive deadlines, the maximum in duration violation of the directive deadlines and the total time costs along all routes of vehicles. Four algorithms for solving the problem are proposed, namely, the algorithm based on grouping of target objects, the “greedy” algorithm with the change of collection center, the algorithm taking into account losses and the algorithm based on the calculation of the attractiveness of collection centers. The algorithm based on the grouping of target objects takes into account the directive timing of objects in solving the problem, the other three are based only on the information about the location of objects. In the framework of the study, a computational experiment for problems of different dimensions was conducted, a comparative analysis of the proposed algorithms depending on the chosen optimality criterion was performed, and the running time of each of the algorithms was evaluated. For the algorithm based on the calculation of the attractiveness of collection centers, the results of testing for two values of the hyperparameter are given.