KUYRUKLU ARAÇ ROTALAMA PROBLEMİ: MATEMATİKSEL MODELLER VE SEZGİSEL ALGORİTMALAR

Abstract

This thesis focuses on the investigation of dedicated or parallel machine systems for the sequence-dependently integration of Machine Scheduling Problems with the Vehicle Routing Problem. Based on the Traveling Salesman Problem with Queued Tasks found in the literature, mathematical models of multi-vehicle or multi-machine variants are proposed within the framework of graph theory, the mathematical models are reduced to integer linear programming, and designed to eliminate symmetric solutions. For the elimination of subtours, the constraint generation method and the DFJ formulation are used to avoid the growth of the decision space with respect to the alternative and to reduce the use of redundant constraints. Despite their simplification, the proposed variants of the Vehicle Routing Problem with Queued Tasks have at least as much complexity as the subproblems defined within them, and become less tracktable within reasonable resources as the problem scale increases. In order to balance the trade-off between tracktability and optimality gap, a lookahead nearest neighbor heuristic algorithm with a distance-based dynamic criterion is designed specifically for the Vehicle Routing Problem with Queued Tasks. The performance of the proposed heuristic is within 13% of the obtained solutions. The generalized problems discussed in this thesis, the proposed mathematical models, and the heuristic can provide significant competitive advantages in terms of speed and cost by holistically treating inseparable routing and scheduling activities.