Integrated vehicle routing and warehouse location problem

Abstract

ABSTRACT This thesis proposes an exact algorithm for the integrated vehicle routing and warehouse location problem, known as WLRP. WLRP helps the supply chain managers to make strategic level decisions, and may be used in a supply chain environment at different industrial sectors. Previous work on WLRP emphasized heuristic and metaheuristic solution approaches that do not guarantee optimality. In search of optimality, other related and well-studied problems are investigated and it is concluded that there is a close relationship between the vehicle routing problem with time windows (VRPTW) and WLRP. Therefore, first the VRPTW is studied extensively as a foundation to WLRP. Recent studies on VRPTW call attention to column generation methods together with the branch and bound algorithm. The column generation algorithm with dynamic programming is used and in this thesis a new dynamic programming formulation is presented. Furthermore, for heterogeneous fleet problems, a new variant of vehicle routing problem (VRP) is formulated which is named as the vehicle routing problem with time windows and discrete capacities (VRPTWDC); and the dynamic program is modified for this problem. The WLRP is formulated as a set partitioning problem and column generation technique is applied. The dynamic program is extensively modified to handle the problem more effectively, the bounds are tightened using 2-path cuts and the subtours are eliminated using a separation algorithm. Finally, branch and bound method is applied to solve WLRP optimally. All benchmark problems in WLRP literature are solved and it is illustrated that the proposed algorithm yields better solutions compared to algorithms reported in the literature. IV