Resource constrained shortest paths and extensions.

摘要

In this thesis, we use integer programming techniques to solve the resource constrained shortest path problem (RCSPP) which seeks a minimum cost path between two nodes in a directed graph subject to a finite set of resource constraints. Although NP-hard, the RCSPP is extremely useful in practice and often appears as a subproblem in many decomposition schemes for difficult optimization problems.;We begin with a study of the RCSPP polytope for the single resource case and obtain several new valid inequality classes. Separation routines are provided, along with a polynomial time algorithm for constructing an auxiliary conflict graph which can be used to separate well known valid inequalities for the node packing polytope. We establish some facet defining conditions when the underlying graph is acyclic and develop a polynomial time sequential lifting algorithm which can be used to strengthen one of the inequality classes.;Next, we outline a branch-and-cut algorithm for the RCSPP. We present preprocessing techniques and branching schemes which lead to strengthened linear programming relaxations and balanced search trees, and the majority of the new inequality classes are generalized to consider multiple resources. We describe a primal heuristic scheme that uses fractional solutions, along with the current incumbent, to search for new feasible solutions throughout the branch-and-bound tree. A computational study is conducted to evaluate several implementation choices, and the results demonstrate that our algorithm outperforms the default branch-and-cut algorithm of a leading integer programming software package.;Finally, we consider the dial-a-flight problem (DAFP), a new vehicle routing problem that arises in the context of on-demand air transportation and is concerned with the scheduling of a set of travel requests for a single day of operations. The DAFP can be formulated as an integer multicommodity network flow model consisting of several RCSPPs linked together by set partitioning constraints which guarantee that all travel requests are satisfied. Therefore, we extend our branch-and-cut algorithm for the RCSPP to solve the DAFP. Computational experiments with practical instances provided by the DayJet Corporation verify that the extended algorithm also outperforms the default branch-and-cut algorithm of a leading integer programming software package.