Solving vehicle routing problem with multiple centers and dynamic addition of target objects

Abstract

The paper considers the problem of vehicle routing with alternating objects of two types and several collection centers. A distinctive feature of this problem is the appearance of new target objects in the process of visiting the existing ones. The distance to the new target objects becomes known only after their actual appearance, which requires a flexible approach to the construction of vehicle routes. The mathematical model of the problem with all input data and constraints taken into account is compiled. Four heuristic algorithms are proposed to solve the problem: a “greedy” (i.e., making locally optimal decisions at each step) algorithm without changing the collection center, a “greedy” algorithm with changing the collection center, an algorithm taking into account losses, and an algorithm based on the calculation of the attractiveness of collection centers. For each of the proposed algorithms, their step-by-step description is presented, and their program implementations are developed, which allowed us to test them on a set of input data of different dimensions and perform a detailed comparison of the results of the algorithms. Several ways of generating input data for testing were also proposed: random and “cluster” algorithms for generating the locations of target objects, as well as sequential and “group” algorithms for generating the moments of appearance of target objects. In the final part, a comparative analysis of the developed algorithms is carried out and the efficiency of their application for solving vehicle routing problems with dynamic addition of target objects with input data of different size and nature is evaluated.