## Invited Session Fri.1.H 3005

#### Friday, 10:30 - 12:00 h, Room: H 3005

**Cluster 2: Combinatorial optimization** [...]

### Combinatorial optimization in logistics

**Chair: Erwin Pesch**

**Friday, 10:30 - 10:55 h, Room: H 3005, Talk 1**

**Jens Schulz**

Explanation algorithms in cumulative scheduling

**Coauthor: Stefan Heinz**

**Abstract:**

In cumulative scheduling, conflict analysis is one of the key ingredients to solve these problems efficiently. Thereby, the computational complexity of explanation algorithms that explain infeasibilities or bound changes plays an important role. Their role is even more substantial when we are faced with a backtracking system where explanations need to be constructed on the fly. In this talk we present complexity results for computing minimum-size explanations for the propagation algorithms time-tabling, edge-finding, and energetic reasoning. We show that it is possible to compute in polynomial time minimum-size explanations for bound changes which result from energetic reasoning and edge-finding. In case of time-tabling, we prove that an important special case is already weakly NP-hard. In the context of bound-widening, the problems all become NP-hard. To this end, we establish a relation to unsplittable flow problems on the path. We evaluate different heuristic approaches and exact approaches to explain bound changes derived by these algorithms. Using these minimum-size explanations pays off in total compared to using faster but weaker explanation algorithms.

**Friday, 11:00 - 11:25 h, Room: H 3005, Talk 2**

**Jenny Nossack**

Benders decomposition for a 1-full-truckload pickup-and-delivery vehicle routing problem

**Coauthor: Erwin Pesch**

**Abstract:**

We address a pickup and delivery vehicle rounting problem with multiple depots, where routes have to be constructed to satisfy customer requests, which either involve the pickup or delivery of a single commodity. A fleet of homogeneous vehicles is available to fulfill the demand and supply of the customers under the objective to minimize the total distance traveled. Each vehicle has unit capacity and the commodities which are collected from the pickup customers can be used to accommodate the demand of the delivery customers. We model this problem as an integrated integer nonlinear programming problem that simultaneously solves an assignment and a routing problem, linked via coupling constraints. Exact solution approaches based on the classical and the generalized Benders

decomposition are presented to optimally solve the problem.

**Friday, 11:30 - 11:55 h, Room: H 3005, Talk 3**

**Erwin Pesch**

A branch-and-bound algorithm for the acyclic partitioning problem

**Coauthor: Jenny Nossack**

**Abstract:**

We focus on the problem of partitioning the vertex set of a

directed, arc- and vertex-weighted graph into clusters, i.e. disjoint sets. Clusters are to be determined such that the sum of the vertex weights within the clusters satisfies an upper bound and the sum of the arc weights within the clusters is maximized. Additionally, the graph is enforced to partition into a directed, acyclic graph where the clusters define the vertices. This problem is known as the acyclic partitioning problem and has been proven to be NP-hard. Real-life applications arise at rail-rail transshipment yards. We propose new integer programming formulations for the acyclic partitioning problem and suggest an exact solution approach based on an integration constraint propagation into a branch-and-bound framework. Computational results are reported to confirm the strength of our approach.