Resource extension functions: properties, inversion, and generalization to segments

DOI10.1007/s00291-007-0083-6zbMath1133.90309OpenAlexW2076023255MaRDI QIDQ2480803

Stefan Irnich

Publication date: 3 April 2008

Published in: OR Spectrum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00291-007-0083-6

zbMATH Keywords

Column generationVehicle routing and schedulingAccelerated local searchResource extension functionResource-constrained path

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (40)

The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem ⋮ Tramp ship routing and scheduling with voyage separation requirements ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs ⋮ Technical note: Split algorithm in \(O(n)\) for the capacitated vehicle routing problem ⋮ A new branch-and-price algorithm for the traveling tournament problem ⋮ Exact Branch-Price-and-Cut for a Hospital Therapist Scheduling Problem with Flexible Service Locations and Time-Dependent Location Capacity ⋮ Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling ⋮ Algorithms for non-linear and stochastic resource constrained shortest path ⋮ A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows ⋮ Selective arc‐ng pricing for vehicle routing ⋮ A generic exact solver for vehicle routing and related problems ⋮ Inter-depot moves and dynamic-radius search for multi-depot vehicle routing problems ⋮ Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network ⋮ Solving vehicle routing problems with intermediate stops using VRPSolver models ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ A directional heuristics pulse algorithm for a two resources constrained shortest path problem with reinitialization ⋮ Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints ⋮ Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies ⋮ Vehicle Routing Problems with Inter-Tour Resource Constraints ⋮ Integrating rolling stock scheduling with train unit shunting ⋮ Branch-and-price approaches for the multiperiod technician routing and scheduling problem ⋮ Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster ⋮ Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems ⋮ Perspectives on integer programming for time-dependent models ⋮ Solving shortest path problems with a weight constraint and replenishment arcs ⋮ Dynamic programming approaches to solve the shortest path problem with forbidden paths ⋮ Solving a vehicle routing problem with resource conflicts and makespan objective with an application in car body manufacturing ⋮ Optimal routing with failure-independent path protection ⋮ A rollout algorithm for the resource constrained elementary shortest path problem ⋮ Bidirectional labeling for solving vehicle routing and truck driver scheduling problems ⋮ On the shortest path problem with negative cost cycles ⋮ A unified solution framework for multi-attribute vehicle routing problems ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ On the one-to-one pickup-and-delivery problem with time windows and trailers ⋮ Cutting planes for branch-and-price algorithms ⋮ A matheuristic for a 2-echelon vehicle routing problem with capacitated satellites and reverse flows ⋮ Solving the selective multi-category parallel-servicing problem ⋮ Delay-constrained shortest paths: approximation algorithms and second-order cone models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Brunn-Minkowski inequality for the Monge-Ampère eigenvalue
• The pickup and delivery problem with time windows
• The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm
• Resource constrained shortest path problems in path planning for fleet management
• Sequential search and its application to vehicle-routing problems
• The Preferential Bidding System at Air Canada
• The Shortest Path Problem with Time Windows and Linear Waiting Costs
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• Technical Note—Optimizing the Schedule for a Fixed Vehicle Path with Convex Inconvenience Costs
• Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
• Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling
• Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: II. Routing
• Pickup and Delivery of Partial Loads with “Soft” Time Windows
• A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
• An algorithm for the resource constrained shortest path problem
• Modelling Intra-City Time-Dependent Travel Speeds for Vehicle Scheduling Problems
• Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms
• Airline Crew Scheduling: A New Formulation and Decomposition Algorithm
• A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
• A Column Generation Approach for Large-Scale Aircrew Rostering Problems
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Vehicle Routeing with Multiple Use of Vehicles
• Column Generation
• Dynamic Aggregation of Set-Partitioning Constraints in Column Generation
• Shortest Path Problems with Resource Constraints

This page was built for publication: Resource extension functions: properties, inversion, and generalization to segments