1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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), from this result it follows that TSP with distances measured in Manhattan norm is NP-complete, too (see for example this survey). 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"

$\endgroup$
  • $\begingroup$ @Mario : My initial question was about a weighted grid. I have made the edit . $\endgroup$ – Shalabh Vidyarthi Oct 5 '12 at 10:01
  • $\begingroup$ @Shalabh: I slightly changed the answer $\endgroup$ – Marzio De Biasi Oct 5 '12 at 12:46
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Oct 5 '12 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.