Dağıtım-toplamalı araç rotalama probleminin iki boyutlu yükleme kısıtı altında modellenmesi ve çözümü

Abstract

Lojistik yönetiminde önemli bir yere sahip olan araç rotalama problemi bir çok farklı kısıt altında incelenmektedir. Son yıllarda önem kazanan yükleme kısıtı ve rota boyunca dağıtım ve toplama isteklerinin aynı zamanda karşılandığı problem tipi, araç rotalama problemi litareteratüründe sıklıkla karşımıza çıkmaktadır. Yapısı gereği NP-Zor olan rotalama problemin bu eklentiler sonrası zorluk derecesi daha da artmaktadır. Bu çalışmanın amacı iki boyutlu yükleme kısıtı altında dağıtım toplamalı araç rotalama problemini matematiksel olarak modellemek ve kesin çözüm yaklaşımı geliştirmektir. Ayrıca rota boyunca yüklerin araç içinde yeniden yerleştirmeye maruz kalmadan taşınmasına yönelik olarak da, son giren ilk çıkar kısıtı (LIFO-Last In First Out) dikkate alınmıştır. Problemin modellenmesi için karışık tamsayılı matematiksel bir model önerilmiştir. Ancak LIFO kısıtının uygulanması, elde edilen tamsayı çözümlerden LIFO koşuluna uygun olanları kontrol eden ardıl bir kontrol algoritması üzerinden gerçekleştirilmiştir. Önerilen matematiksel model ve ardıl algoritma Mosel dilinde kodlanmış ve kesme düzlemi kullanan doğrusal programlama tabanlı dal sınır algoritması desteği ile çözülmüştür. Çözüm süresinin kısa olduğu küçük boyutlu problemler ile önerilen yaklaşımın optimal çözüm becerisi kanıtlanmıştır.

In logistics research, the vehicle routing problem has been extensively studied for a variety of constraints. Among many others, container loading problem under sequential pickup and delivery requests along the route is a frequently encountered problem of logistics management. While the routing problem is NP-difficult by its structure, it becomes even more difficult to model these problems with these type of additional requirements. The purpose of this study is to develop a precise model and a solution approach for the vehicle routing problem with pickup-delivery under two dimensional loading constraints. It is also assumed that the loading must obey a last in-first-out rule (LIFO) which prohibits relocating loads within the vehicle. For the exact solution of the problem, a mixed integer mathematical model is proposed. However, for the complete implementation of the LIFO constraint, an efficient posterior control procedure is developed to check for the feasibility of candidate integer solutions. The proposed MILP model is solved by a solver package with an additional algorithmic programming capability in Mosel language. The solution approach with small size problems proved to be optimal.