We investigate the multi-trip elementary shortest path problem (MESPPRC) with resource constraints in which the objective is to find a shortest path between a source node and a sink node such that nodes other than the specified replenishment node are visited at most once and resource constraints are not violated. After each visit to the replenishment node, which we take to be the sink node in our study, resource consumption levels can be reset to a certain initial value. As this problem arises primarily as a subproblem in decomposition-based algorithms for a wide variety of practical applications, we illustrate it in the context of an integrated routing and scheduling problem with capacitated and time restricted vehicles. We propose exact and heuristic algorithms and evaluate the performance of these in a branch-and-price framework.
Citation
Technical Report, Laboratory for Computational Optimization Research, Lehigh University