| dc.description.abstract | The management of reverse logistics has received growing attention in recent years due to
new regulations, environmental aspects and an eagerness to obtain further operational
benefits. Reverse logistics can be modeled as a closed-loop supply chain, where significant
improvements 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 and
is 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 by
an improvement search is proposed. To construct a solution the matheuristic decomposes
the problem into an inventory problem and a routing problem. The constructed solution is
further improved with a set of operators. The matheuristic embeds the construction and the
improvement operators into an iterative scheme. When the iterative loop is terminated, a
final improvement search is suggested. The matheuristic gives solutions with lower dual gaps
than 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. | |
