Seçici ve periyodik envanter rotalama problemi için uyarlanmış geniş komşu arama sezgisel algoritması

In this thesis we develop the first metaheuristic method for a selective and periodic inventory routing problem (SPIRP) that arises in reverse logistics. The problem concerns a biodiesel production company collecting used vegetable oil from restaurants and hotels which are the source nodes using and wasting vegetable oil in considerable amounts. The production facility reuses the waste oil as raw material to produce biodiesel and meets the raw material requirement for each day from daily collection, inventory and by purchasing oil. The manager needs to decide which of the present source nodes to include in the collection program, and which periodic routing schedule to repeat in every planning horizon to visit these nodes accumulating vegetable oil. His objective is to minimize the total collection, inventory and purchasing costs while the production requirements and operational constraints are met. Recently, a flow-based mixed integer linear programming (MILP) formulation was proposed for this problem, and solved on a real-world case with up to 40 source nodes. However, it was observed that the average optimality gap attained by the commercial MILP solver in three hours exceeds 10% when there are more than 25 nodes present. In order to solve large sized instances of SPIRP more effectively in a reasonable time, we develop an Adaptive Large Neighborhood Search (ALNS) algorithm by using a rich neighborhood structure comprised of 11 distinct moves. Some of these moves modify the visiting schedule and vehicle routes, while others change also the subset of visited source nodes. We test our algorithm on small size instances and compare the results with the MILP model. While our algorithm solves the small instances in several seconds, the MILP model runs for hours to find similar results. When the number of source nodes is 30 and more, our algorithm outperforms the MILP model. We also test our algorithm on larger instances with up to 100 nodes and present the related computational results. For the instances with 50 to 100 nodes, the problem is solved with around 10.7% gap.