Mathematical models and subgradient based solution approach for the vehicle routing problems

In this thesis, capacitated vehicle routing problem and heterogeneous fleet vehicle routing problem which are widely studied in the literature are examined and new solution approaches are proposed for the regarding problems. The vehicle routing problem is a nonconvex and nondifferentiable combinatorial optimization problem, which is a type of problem that is considered NP-hard due to integer variable constraints. The proposed solution approaches are based on the modified subgradiant method introduced by Kasımbeyli, which does not require the convexity and differentiability conditions of constrained optimization problems. The algorithm creates a subproblem for each iteration. In this study, genetic algorithm which is an effective metaheuristic algorithm in vehicle routing problems, is applied for the solution of the subproblem. Since the solution method is designed as a hybrid of the genetic algorithm and the Modified Subgradient Algorithm, it is called "Hybrid Subgradient Method". In this study, hybrid subgradient method is also applied to solve and examine the multi-objective mathematical model developed for the heterogeneous fleet vehicle routing problem. This method is applied to solve the heterogeneous fleet vehicle routing problem by combining the relaxation of constraints approach and the obtained solutions are presented with comparison. The performances of all proposed solution methods are investigated by using the test problems from the literature, the obtained computational results are analyzed and suggestions for future studies are presented. Keywords: Vehicle routing, Genetic algorithm, Heterogeneous fleet, Modified subgradient