Partitioning methods for NP-hard routing problems

Routing plays an essential role in modern life. As our civilization grows more reliant upon the efficient movement of goods and people, the mathematical problems underlying routing decisions also grow in complexity. Given their structure, partitioning provides one option for solving routing problems more quickly. This dissertation focuses on developing partitioning frameworks for NP-hard routing problems. Specifically, different partitioning methods are applied to the traveling salesman problem (TSP), resource-constrained shortest path problem (RCSPP), and other related problems. The TSP framework, referred to as convex hull partitioning (CHP), builds on several existing partitioning methods by using a new idea for forming subproblems. CHP relies on the connection between an optimal tour and the convex hull boundary of the input points. The hull points occur in the same order in both the convex hull boundary and the optimal tour. Using this order, CHP forms a set of point partitions based around consecutive pairs of hull points. This allows Hamiltonian paths through each partition to be connected at shared hull points, leading to a solution to the original TSP. A slightly modified framework uses a similar technique to solve sequential ordering problems (SOP). Adding a global resource constraint makes using a similar geometry-based partitioning method more difficult. Therefore, partitioning when solving an RCSPP uses the resource costs of paths to each node. When combined with an existing dynamic programming algorithm, resource cost partitioning allows all non-dominated paths from a single source to all other nodes to be found more quickly. Computational experiments show the partitioning frameworks allow both TSPs and RCSPPs to be solved more quickly with little to no decrease in solution quality. These results demonstrate the benefits of using partitioning to help solve TSPs and RCSPPs. Ideally, these partitioning techniques will be extended to provide similar benefits when solving other difficult routing problems.