The application of metaheuristics in network routing and inventory routing problem / Huda Zuhrah Ab Halim - Huda Zuhrah, Ab Halim (2012)
Metaheuristic methods are widely known as one of the most practical approaches in solving large (or very large) problems in many fields, specifically NP hard Combinatorial Problems. In this thesis, we study two powerful metaheuristics method that are Genetic Algorithm (GA) and Variable Neighborhood Search (VNS). In this thesis, we analyzed both metaheuristics methods, GA and VNS by applying to two NP-hard combinatorial problems, Point to Multipoint Routing Problem (PMRP) and Integrated Inventory Routing Problem (IRP). Message Scheduling Problems (MSP) is one of the important fields in the design of an efficient telecommunication network. Specifically PMRP is to find optimal routes for a set of requests; the message routing from one source nodes to multiple destinations. An enhanced GA and VNS were developed and both algorithms were tested on small, medium and large problems. VNS embeds different local search: swap, invert, or-opt and restricted or-opt. VNS with restricted or-opt performs better in terms of solution quality at the expense of a slightly higher computational time. The second part of the thesis is devoted to IRP. IRP is concerned with coordinating the inventory and delivery operations to meet suppliers demand with an objective to minimize the total cost which consist of the inventory holding cost and the fixed and variable transportation costs. The IRP addressed in this thesis is based on a finite horizon, multi-period, multi-supplier, and single assembly plant, where a fleet of capacitated vehicles housed at a depot transported products from the suppliers to meet the demand specified by the assembly plant. We proposed two different VNS; VNSIRP with Generalized Insertion Method (GENI) as a local search and enhanced VNS with GENI is used to construct the neighborhood structure. We evaluate both algorithms on a set data and enhanced VNS performs better with a slightly higher computational time.