An adaptive large neighborhood search for the multi-compartment inventory routing problem

Abstract

In this thesis study, we concentrate on an inventory routing problem with a fleet of multi-compartment vehicles which enables the distribution of different products to customers on a delivery route. Using separate compartments on a vehicle increases profitability and customer satisfaction when customer demands vary over product and period basis. We assume that the compartment that each product can be loaded is known and the capacities of the compartments are fixed. Customers have preset storage capacities and distribution plans should be made in a way that no customers would face stock-outs for any product on any day. We observe the practices of this variant in the distribution of foods with different temperature needs to groceries, feed distribution to livestock farms, and collection of different types of recyclable wastes. We examine this problem separately for three assumptions considering different cases of allowing/disallowing split delivery to customers. We propose a matheuristic ap proach to solve the addressed problem where we systematically integrate an Adaptive Large Neighborhood Search algorithm with mathematical programming models. We generate a set of instances and test the performance of our algorithm by comparing it with the results obtained by a flow formulation adapted from the literature. We observe that the best results we find for each instance are only %11.7 worse than the solutions found by the flow formulation on average.Bu tez ¸calı¸smasında, farklı ¨ur¨unlerin m¨u¸sterilere aynı rotada da˘gıtımına olanak sa˘glayan ¸cok b¨olmeli ara¸clardan faydalandı˘gımız bir envanter rotalama problemini ele almak tayız. M¨u¸steri taleplerinin g¨un ve ¨ur¨un bazında farklılık g¨osterdi˘gi bir durumda ara¸c i¸cerisinde ayrı b¨olmeler kullanmak hem karlılı˘gı hem de m¨u¸steri memnuniyetini arttırmaktadır. Ara¸clarda her b¨olmede hangi ¨ur¨un¨un ta¸sınaca˘gının belirli oldu˘gu ve b¨olme kapasitelerinin sabit oldu˘gu bir yapıyı benimsiyoruz. M¨u¸sterilerin belirli stoklama kapasiteleri oldu˘gunu ve da˘gıtım planlarının hi¸cbir m¨u¸sterinin hi¸cbir g¨unde hi¸cbir ¨ur¨unden stok-dı¸sı kalmayaca˘gı ¸sekilde yapılması gerekti˘gini varsayıyoruz. Bu b¨olme yapısının kullanıldı˘gı ¸cok b¨olmeli rotalama problemlerinin uygulamalarına mar ketlere farklı sıcaklıkta ta¸sınması gereken gıdaların da˘gıtımı, hayvan ¸ciftliklerine yem da˘gıtımı, ve ¸ce¸sitli geri d¨on¨u¸st¨ur¨ulebilir atıkların toplanması alanlarında rastlanmak tadır. Bu problemi m¨u¸sterilere b¨ol¨unm¨u¸s da˘gıtımın izin verildi˘gi/verilmedi˘gi farklı durumları g¨oz ¨on¨unde bulundurarak ¨u¸c farklı varsayım i¸cin ayrı ayrı inceliyoruz. Problemin ¸c¨oz¨um¨u i¸cin Uygulanabilir Geni¸s Kom¸suluk Araması algoritmasını matem atiksel modeller ile sistematik bir ¸sekilde kullandı˘gımız mat-sezgisel bir y¨ontem sunuy oruz. Algoritmamızın performansını literat¨urden uyarladı˘gımız bir akı¸s form¨ulasyon undan elde etci˘gimiz sonu¸clar ile olu¸sturdu˘gumuz bir dizi veri k¨umesi ¨uzerinde kar¸sıla¸s tırarak de˘gerlendiriyoruz. Her bir veri k¨umesinde algoritmamızın buldu˘gu en iyi sonucun akı¸s form¨ulasyonu ile bulunan sonu¸ctan ortalamada sadece %11.7 daha k¨ot¨u oldu˘gu g¨ozlemlenmektedir.