Constructing exact and heuristic solution approaches for dynamic vehicle routing problem

Vehicle routing problems (VRP) are at the center of many logistics applications. Cost effective determination of the route of a vehicle fleet plays an important role in various industries. With the developing industry standards, the importance of real-time dynamic VRP applications has increased. The key factor that makes routing problems dynamic is the changeable environmental conditions while routing. Dynamic VRP is one of the most important problems in production and logistics. The moment of occurrence, cancellation or change of customer demands, service times, travel times and availability of vehicles are expressed as sources of dynamism for dynamic VRP. The source of dynamism of the dynamic VRP addressed within the scope of this thesis is the dynamic emergence of some of the customers at an unknown or unpredictable moment or the change of the current client demand after the initial routes are created. It is necessary to take action with a fast and high accuracy rate against the problems encountered in real life. Thankfully, heuristic algorithms developed to solve NP-hard problems such as dynamic vehicle routing offer remarkable and undeniable advantages. Especially in case of dynamic demands while meeting the customer requests in the starting route of the vehicles, it is the key factor to arrange up-to-date routes quickly by rerouting. It is undeniable that the shorter this period the more it can be possible for vehicles to meet customer demands without delay. Hence, Random Iterative MDROL-HFS CW Saving Algorithm has been developed based on Clarke & Wright Savings Algorithm to perform large-scale dynamic VRP. There is no method that provides optimum solution for each problem dimension of dynamic VRP. For this reason, academic studies have focused on the development of exact solution methods for the largest possible problems in line with the current technological possibilities and algorithms that allow the closest result to the optimum result in the shortest time. The main purpose of this master thesis is to develop a mathematical model that offers exact solutions to dynamic VRP and a heuristic algorithm that guarantees a fast and high accuracy solution in large-scale problems.