A branch and cut algorithm for the inventory routing problem

Abstract

Envanter rotalama problemi, ürünlerin aynı kapasitedeki araçlardan oluşan bir filo tarafından bir tedarikçiden bir dizi perakendeciye dağıtıldığı bir problemdir. Araçların güzergahları ve her perakendeciye her bir zaman periyodu için gönderilen ürün miktarları, envanter ve nakliye maliyetlerinin en aza inmesi amaçlanarak ve mevcut talepler her zaman karşılanarak hesaplanır. Perakendecilerdeki envanterler yönetilirken farklı envanter ikmal politikaları kullanılabilir. Biz problemi maksimum seviyede stok yenileme politikası ile birlikte değerlendiriyoruz. Maksimum stok yenileme politikası altında envanter rotalama problemi için karma bir tamsayılı doğrusal programlama modeli sunuyoruz ve problemin gevşetmelerinden yola çıkarak geçerli eşitsizlikler türetiyoruz. Geçerli eşitsizliklerimizi önceki çalışmalardakilerle ilişkilendirerek açıklıyoruz. Ayrıca yeni geçerli eşitsizlikler ve bir dal kesi algoritması öneriyoruz. Literatürdeki referans örnekler ve rastgele oluşturulmuş yeni örnekler üzerindeki hesaplama sonuçlarını sunuyoruz.

The inventory routing problem arises in vendor managed systems where products are distributed from a supplier to a set of retailers by a homogeneous fleet of capacitated vehicles. The routes of the vehicles and the quantities of products sent to each retailer in each time period are determined in such a way that no stockouts occur and total costs arising from inventory holding and transportation are minimized. Different inventory replenishment policies can be used while managing the inventories at retailers. We consider the problem with the maximum level inventory replenishment policy. We present a mixed integer linear programming model and derive valid inequalities using several structured relaxations. We relate our valid inequalities to those in the previous studies. We also propose new valid inequalities, implement a branch and cut algorithm and present computational results on benchmark instances from the literature as well as new randomly generated instances.