Parameterized Complexity of Vehicle Routing
For researchers in parameterized complexity and combinatorial optimization, this paper establishes tight complexity boundaries for VRP and CVRP under treewidth, showing that CVRP is harder than VRP in the parameterized sense.
The paper studies the parameterized complexity of Vehicle Routing Problem (VRP) and Capacitated Vehicle Routing Problem (CVRP) with respect to treewidth and other parameters. It presents an FPT algorithm for VRP parameterized by treewidth, while proving paraNP- and W[·]-hardness for CVRP under various parameterizations, and provides an XP algorithm for CVRP parameterized by both treewidth and vehicle capacity.
The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph $G$, there are $k$ vehicles available to jointly cover the set of clients $C \subseteq V(G)$. Every vehicle must start at one of the depot vertices $D \subseteq V(G)$ and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of $G$. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and $W[\cdot]$-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.