Bounding procedures on bi-directional labeling algorithm of TDVRPTW in branch-and-cut-and-price framework

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2011

Öğrenci: SELEN KÖKTEN

Danışman: CEM İYİGÜN

Özet:

In this thesis we consider a Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW) which is solved by a Branch and Cut and Price (BCP) algorithm. The decomposition of an arc based formulation leads to a set-partitioning problem as the master problem, and a Time-Dependent Elementary Shortest Path Problem with Resource Constraints (TDESPPRC) as the pricing problem. The main contribution of this thesis is the modified fathoming and bounding procedures applied on bi-directional Time-Dependent Labeling algorithm (TDL) which is used solve the TDESPPRC. The aim of the fathoming proposed is to solve TDVRPTW more efficiently by not extending the unproductive labels in bi-directional TDL algorithm. Moreover, an arc bounding model is introduced to stop the extension of labels as an alternative to resource bounding used in bi-directional search. In addition, independent from the work on TDVRPTW, the thesis includes an effects analysis of a new customer on Kuehne+Nagel(K+N) Netherlands Fast Moving Consumer Goods (FMCG) and returns distribution network. This study focused on analyzing the current performance of the distribution network and evaluating the scenarios for K+N’s future distribution network by a simulation study.