Solving shortest path problems with a weight constraint and replenishment arcs

DOI10.1016/j.cor.2011.07.017zbMath1251.90072OpenAlexW2010619023MaRDI QIDQ1762066

Natashia Boland, Olivia J. Smith, Hamish Waterer

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.07.017

zbMATH Keywords

shortest pathsresource constraintsreplenishmentpreprocessinglabeling algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

The electric vehicle shortest-walk problem with battery exchanges ⋮ On an exact method for the constrained shortest path problem ⋮ Dijkstra's algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment ⋮ On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage ⋮ The aircraft routing problem with refueling ⋮ A directional heuristics pulse algorithm for a two resources constrained shortest path problem with reinitialization ⋮ Acceleration strategies for the weight constrained shortest path problem with replenishment ⋮ A branch\&price\&cut algorithm for the vehicle routing problem with intermediate replenishment facilities ⋮ Traffic equilibrium and charging facility locations for electric vehicles ⋮ Range-constrained traffic assignment with multi-modal recharge for electric vehicles ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ Energy-optimal routes for battery electric vehicles ⋮ An exact reduction technique for the k-colour shortest path problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum cost path problems with relays
• An integrated aircraft routing, crew scheduling and flight retiming model
• The network design problem with relays
• Crew pairing at Air France
• Locomotive assignment with heterogeneous consists at CN North America
• The asymmetric traveling salesman problem with replenishment arcs
• A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem
• Crew assignment via constraint programming: Integrating column generation and heuristic tree search
• Heuristics for the black and white traveling salesman problem
• Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs
• Resource extension functions: properties, inversion, and generalization to segments
• Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• Flight String Models for Aircraft Fleeting and Routing
• Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem
• The Black and White Traveling Salesman Problem
• Wide area telecommunication network design: application to the Alberta SuperNet
• Lagrangian relaxation and enumeration for solving constrained shortest-path problems
• Approximation Algorithms for the Black and White Traveling Salesman Problem
• Improving Crew Scheduling by Incorporating Key Maintenance Routing Decisions
• A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
• Airline Crew Scheduling: A New Formulation and Decomposition Algorithm
• Flight Attendant Rostering for Short-Haul Airline Operations
• Airline Crew Scheduling with Time Windows and Plane-Count Constraints
• Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• Shortest Path Problems with Resource Constraints
• Optimal construction of airline individual crew pairings.
• Constraint programming based column generation for crew assignment

This page was built for publication: Solving shortest path problems with a weight constraint and replenishment arcs