نوع مقاله : پژوهشی
نویسندگان
1 دانشکده مهندسی صنایع، پردیس دانشکده های فنی، دانشگاه تهران
2 دانشکده مهندسی صنایع-دانشگاه تهران
چکیده
کلیدواژهها
موضوعات
عنوان مقاله [English]
نویسندگان [English]
Vehicle routing problems are a category of complex mathematical problems in the field of transportation and supply chain management, and a wide variety of these problems have been introduced. One category within this field involves the collaboration of two different types of fleets in a network, where in many cases, one of the fleets must patrol the graph as a support fleet and is not subject to the same constraints as the other fleet, such as only visiting a vertex or an edge once. Examples include refueling fleets or trucks providing services to drones, where these fleets patrol the network so that the other fleet can use their services as needed.
In this paper, the problem of the free movement of such fleets on a graph is examined as a free patrol problem, which can be used as a sub-problem in the modeling and solving of many routing problems. To this end, the problem is modeled as a mixed-integer linear programming (MILP) problem in both discrete and continuous time spaces. Generally, it is expected that the model in continuous time space will exhibit lower computational complexity, but since modeling in continuous time requires changes to the graph, leading to an increase in the number of vertices and edges, its behavior needs to be more thoroughly investigated. On the other hand, another challenge in analyzing this problem is that the objective of the free patrol sub-problem depends on the main problem, as without the main problem, the free patrol problem may lose its objective, with a fleet patrolling the graph within a designated time. Therefore, to decouple and make the free patrol independent of the main problem, five different objective functions have been introduced for each model, covering a wider range of comparisons, leading to ten models in total. Subsequently, all ten models were solved exactly using randomly generated data for ten different graphs. Finally, the behavior of the models was evaluated and compared from various perspectives. The numerical results demonstrate the superior performance of continuous time model over the discrete time model.
کلیدواژهها [English]
)