**Tuesday, 16:15 - 16:40 h, Room: H 0106**

**Stefan Ropke**

Exact and heuristic solution methods for the generalized asymmetric vehicle routing problem and the capacitated arc routing problem

**Abstract:**

In the generalized asymmetric vehicle routing problem (GAVRP) one is given a set of nodes consisting of customer nodes and a depot. Customer nodes are partitioned into clusters and one must construct a number of routes, starting and ending at the depot, such that exactly one customer from each cluster is visited. Each cluster has a certain demand and routes must be constructed such that the total demand on a route is below a given threshold. We solve the GAVRP with an exact method, based on the branch-and-cut-and-price paradigm, as well as with a parallel adaptive large neighborhood search heuristic. Furthermore, in [Baldacci, Bartolini and Laporte (2010)] it was shown how an instance of the capacitated arc routing problem (CARP) easily could be transformed into a GAVRP instance. We use this transformation in order to solve CARP instances with the proposed GAVRP algorithms and report on extensive computational experiments for both problem types.

Talk 3 of the contributed session Tue.3.H 0106

**"Exact approaches to routing problems"** [...]

Cluster 13

**"Logistics, traffic, and transportation"** [...]