VRP Variants

Hamiltonian Cycle Problem (HCP)

A Hamiltonian cycle (or Hamiltonian circuit) for a given graph G = (V, E) consists of finding an ordering of the vertices of G such that each vertex is visited exactly once and the last vertex returns to the first.

The problem is named after Sir William Rowan Hamilton, who in 1859 devised a puzzle — the icosian game — in which such a path along the edges of a dodecahedron was sought.

Deciding whether a graph contains a Hamiltonian cycle is NP-complete (Garey and Johnson, 1983), so no polynomial-time algorithm is known for the general case; in the worst case, only an exhaustive search can settle the question. The figures below show a graph and two of its Hamiltonian cycles.

An undirected graph given as input to the Hamiltonian cycle problem — Figure 1: Typical input for the HCP.

The same graph with one Hamiltonian cycle highlighted — Figure 2: A Hamiltonian cycle for the graph in Figure 1.

The same graph with a different Hamiltonian cycle highlighted — Figure 3: Another Hamiltonian cycle for the graph in Figure 1.

The HCP is the decision problem at the heart of routing: the Traveling Salesman Problem asks for a minimum-cost Hamiltonian cycle in a weighted complete graph, and every VRP route is itself a Hamiltonian cycle over the depot plus the customers assigned to it.