A matheuristic for the inventory routing problem with divisible pickup and delivery
Master thesis
Permanent lenke
http://hdl.handle.net/11250/2577226Utgivelsesdato
2018Metadata
Vis full innførselSamlinger
Sammendrag
The management of reverse logistics has received growing attention in recent years due tonew regulations, environmental aspects and an eagerness to obtain further operationalbenefits. Reverse logistics can be modeled as a closed-loop supply chain, where significantimprovements can be made through inventory routing optimization.
This thesis considers an inventory routing problem with divisible pickup and delivery(IRP-DPD). A customer may have both delivery and pickup demand in this problem type andis allowed to have separate servings for pickup and delivery. The last part is contrary to what is common and is what constitutes a so-called divisible option. A single depot with a fleet of homogeneous vehicles is considered. The vehicles are restricted by capacity and a maximal duration for a route. An arc-flow formulation of the problem, formulated as a mixed integer linear program, is proposed as an exact solution approach. The formulation is strengthened with valid inequalities and an extended branch and cut algorithmis suggested. The branch and cut algorithm dynamically adds subtour cuts for each strong component of the solution that violates subtour elimination constraints. The exact approach with the extended branch and cut algorithm solves larger instances to optimality, produces lower dual gaps and finds feasible solutions for larger instances.
To solve larger instances, a matheuristic with a two-phase construction approach followed byan improvement search is proposed. To construct a solution the matheuristic decomposesthe problem into an inventory problem and a routing problem. The constructed solution isfurther improved with a set of operators. The matheuristic embeds the construction and theimprovement operators into an iterative scheme. When the iterative loop is terminated, afinal improvement search is suggested. The matheuristic gives solutions with lower dual gapsthan the exact method for all larger instances. It also finds good solutions faster and produces feasible solutions for instances where the exact method does not.