<p>The Hamiltonian cycle problem on <em>grid graphs</em> (a node induced subgraph of the infinite grid) is NP-complete.</p>

<p>To prove NP-hardness of $VRP$ on grid graphs you can use a direct reduction: given a grid graph $G = (V, E)$ with $|V|= n$ nodes, it easy to see that it has an hamiltonian cycle if and only if the corresponding Vehicle Routing Problem on grid graphs (all edges have cost 1) has a solution with total cost $\leq n$. The weighted edges case is a generalization, so the reduction is immediate:</p>

<p>HAM CYCLE on grid graphs (NP-complete) $\leq$ VRP on grid graphs with cost 1 edges $\leq$ VRP on grid graphs with weighted edges.</p>

<p><strong>EDIT:</strong>
Other stuff: <em>Euclidian (planar)</em> TSP is NP-complete (see <a href="http://epubs.siam.org/doi/abs/10.1137/0211056?journalCode=smjcat" rel="nofollow">Hamilton paths in grid graphs</a>), from this result it follows that TSP with distances measured in Manhattan norm is NP-complete, too (<a href="http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/SIR000496.pdf" rel="nofollow">see for example this survey</a>). VRP on grid graphs with weighted edegs is a generalization of it.</p>

<p>But if we consider VRP on <em>solid</em> grid graphs (no holes allowed) I suspect that the problem is open because it is directly connected to this: "<a href="http://cs.smith.edu/~orourke/TOPP/P54.html" rel="nofollow">Problem 54: Traveling Salesman Problem in Solid Grid Graphs</a>"</p>

CC BY-SA 3.0
2012-10-05T10:01:54.753Z
@Mario : My initial question was about a weighted grid. I have made the edit .
Shalabh Vidyarthi
CC BY-SA 3.0
2012-10-05T12:46:40.833Z
@Shalabh: I slightly changed the answer
Marzio De Biasi
CC BY-SA 3.0
2012-10-05T16:02:31.657Z
@Shalabh: another note: the Hamiltonian circuit problem is NP-complete even for grid graphs with $deg \leq 3$ (some edges are missing) and the reduction to VRP with weighted edges is similar.
Marzio De Biasi
CC BY-SA 3.0
2012-10-04T12:50:22.867Z
2012-10-05T12:45:38.387Z
2012-10-05T12:45:38.387Z
Marzio De Biasi
<p>I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot.</p>

<p>Is the following problem NP-hard</p>

<p>Problem :The distance constrained version of the vehicle routing problems over Manhattan distance metric considering an complete $N\times N$  grid or a grid where some edges are missing  ?
The grid graph is a weighted one.</p>

<cc.complexity-theory><reference-request><graph-theory><np-hardness><optimization>
Vehicle routing problem over Manhattan distances
Shalabh Vidyarthi
# Vehicle routing problem over Manhattan distances

(Asked by: username_0 on 2012-10-04)

I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot.

Is the following problem NP-hard

Problem :The distance constrained version of the vehicle routing problems over Manhattan distance metric considering an complete $N\times N$ grid or a grid where some edges are missing ?
The grid graph is a weighted one.

**Tags:** cc.complexity-theory, reference-request, graph-theory, np-hardness, optimization


---

## 1 answers

### Answer by username_1 on 2012-10-04. Score: 3

The Hamiltonian cycle problem on *grid graphs* (a node induced subgraph of the infinite grid) is NP-complete.

To prove NP-hardness of $VRP$ on grid graphs you can use a direct reduction: given a grid graph $G = (V, E)$ with $|V|= n$ nodes, it easy to see that it has an hamiltonian cycle if and only if the corresponding Vehicle Routing Problem on grid graphs (all edges have cost 1) has a solution with total cost $\leq n$. The weighted edges case is a generalization, so the reduction is immediate:

HAM CYCLE on grid graphs (NP-complete) $\leq$ VRP on grid graphs with cost 1 edges $\leq$ VRP on grid graphs with weighted edges.

**EDIT:**
Other stuff: *Euclidian (planar)* TSP is NP-complete (see [Hamilton paths in grid graphs](http://epubs.siam.org/doi/abs/10.1137/0211056?journalCode=smjcat)), from this result it follows that TSP with distances measured in Manhattan norm is NP-complete, too ([see for example this survey](http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/SIR000496.pdf)). VRP on grid graphs with weighted edegs is a generalization of it.

But if we consider VRP on *solid* grid graphs (no holes allowed) I suspect that the problem is open because it is directly connected to this: "[Problem 54: Traveling Salesman Problem in Solid Grid Graphs](http://cs.smith.edu/~orourke/TOPP/P54.html)"

> **Comments:**
> **username_0**: @Mario : My initial question was about a weighted grid. I have made the edit .  
> **username_1**: @Shalabh: I slightly changed the answer  
> **username_1**: @Shalabh: another note: the Hamiltonian circuit problem is NP-complete even for grid graphs with $deg \leq 3$ (some edges are missing) and the reduction to VRP with weighted edges is similar.  

---

