A branch-and-price algorithm for the minimum latency problem

DOI10.1016/j.cor.2018.01.016zbMath1391.90048OpenAlexW2790488300MaRDI QIDQ1652580

Teobaldo Bulhões, Ruslan Sadykov, Eduardo Uchoa

Publication date: 11 July 2018

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

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

zbMATH Keywords

branch-and-price\(ng\)-pathsminimum latency

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27)

Related Items (20)

The arc-item-load and related formulations for the cumulative vehicle routing problem ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling ⋮ An online optimization approach for post-disaster relief distribution with online blocked edges ⋮ Routing multiple work teams to minimize latency in post-disaster road network restoration ⋮ Multirobot search for a stationary object placed in a known environment with a combination of GRASP and VND ⋮ Improving a state‐of‐the‐art heuristic for the minimum latency problem with data mining ⋮ Minimizing total weighted latency in home healthcare routing and scheduling with patient prioritization ⋮ Selective arc‐ng pricing for vehicle routing ⋮ Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier ⋮ Branch-and-price algorithms for large-scale mission-oriented maintenance planning problems ⋮ A generic exact solver for vehicle routing and related problems ⋮ Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network ⋮ A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ Weighted online minimum latency problem with edge uncertainty ⋮ Minimizing the average searching time for an object within a graph ⋮ Tree optimization based heuristics and metaheuristics in network construction problems ⋮ Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty ⋮ Solving the traveling delivery person problem with limited computational time ⋮ Projection heuristics for binary branchings between sum and product

Uses Software

• VRP
• BaPCod

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient elementary and restricted non-elementary route pricing
• Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem
• Natural and extended formulations for the time-dependent traveling salesman problem
• Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem
• The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times
• An effective memetic algorithm for the cumulative capacitated vehicle routing problem
• A new formulation for the traveling deliveryman problem
• A simple and effective metaheuristic for the minimum latency problem
• Variable neighborhood search for the travelling deliveryman problem
• The time dependent traveling salesman problem: polyhedra and algorithm
• Improved branch-cut-and-price for capacitated vehicle routing
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• Resource extension functions: properties, inversion, and generalization to segments
• A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem
• The minimum latency problem
• New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem
• The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k ≥ 3
• Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• The complexity of the travelling repairman problem
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Special cases of traveling salesman and repairman problems with time windows
• P-Complete Approximation Problems
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• The Delivery Man Problem and Cumulative Matroids
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows
• Time‐dependent traveling salesman problem–the deliveryman case
• Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
• A note on the traveling repairman problem
• The traveling salesman problem with cumulative costs
• Shortest Path Problems with Resource Constraints

This page was built for publication: A branch-and-price algorithm for the minimum latency problem