Patent ID: 8073797

Claim:
A computer-implemented method for solving a combinatorial optimization problem of transit point routing, said method comprising the steps of: marking a plurality of vertices representing transit points; intersecting the plurality of vertices with a plurality of boundaries with each of the boundaries offset from each other to create a plurality of open-ended zones bordered by the boundaries; enumerating a first set of vertices within a first zone of the open-ended zones; enumerating a second set of vertices within a second zone located across a first boundary of the plurality of boundaries from the first zone of the open-ended zones; plotting a first set of minimum length Hamiltonian paths for the first set of vertices; plotting a second set of minimum length Hamiltonian paths for the second zone by considering only vertices in the second zone and the minimum length Hamiltonian path of the first zone; connecting the first set of Hamiltonian paths with the second set of Hamiltonian paths; and defining a first transit point route by said connecting step to include the vertices of the first and second zones.