Scientific Program > Talks by Speaker > Vadseth Simen

This paper 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 algorithm is suggested. The branch and cut algorithm dynamically adds subtour cuts for each strong component of the solution that violates subtour elimination constraints.

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.