Optimization Online


Solution Methods for the Multi-trip Elementary Shortest Path Problem with Resource Constraints

Z Akca (zelihaakca***at***gmail.com)
TK Ralphs (ted***at***lehigh.edu)
RT Berger (rosemary.t.berger***at***gmail.com)

Abstract: 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.

Keywords: Branch-and-price, Elementary shortest path, Routing

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization (Other )

Category 3: Integer Programming (0-1 Programming )

Citation: Technical Report, Laboratory for Computational Optimization Research, Lehigh University

Download: [PDF]

Entry Submitted: 03/11/2011
Entry Accepted: 03/11/2011
Entry Last Modified: 03/15/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society