Lagrangian duality applied to the vehicle routing problem with time windows

DOI10.1016/j.cor.2004.11.002zbMath1126.90038OpenAlexW2031722814MaRDI QIDQ2496037

Yanyan Li

Publication date: 30 June 2006

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

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

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

A new mixed integer programming model for curriculum balancing: application to a Turkish university ⋮ Lower bounding procedure for the asymmetric quadratic traveling salesman problem ⋮ A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows ⋮ Lifted and local reachability cuts for the vehicle routing problem with time windows ⋮ Accelerating column generation for variable sized bin-packing problems ⋮ Pricing routines for vehicle routing with time windows on road networks ⋮ Integrated job scheduling and network routing ⋮ A comparison of three metaheuristics for the workover rig routing problem ⋮ A generic exact solver for vehicle routing and related problems ⋮ New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows ⋮ The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches ⋮ New Refinements for the Solution of Vehicle Routing Problems with Branch and Price ⋮ A tutorial on column generation and branch-and-price for vehicle routing problems ⋮ A stabilized column generation scheme for the traveling salesman subtour problem ⋮ An Investigation on Compound Neighborhoods for VRPTW ⋮ Limited memory rank-1 cuts for vehicle routing problems ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ Minimizing value-at-risk in single-machine scheduling ⋮ The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach ⋮ An effective memetic algorithm for the cumulative capacitated vehicle routing problem ⋮ A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows ⋮ A vehicle routing problem with distribution uncertainty in deadlines ⋮ An inventory-routing problem with the objective of travel time minimization ⋮ A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows ⋮ A stochastic dynamic traveling salesman problem with hard time windows ⋮ A relax‐and‐price heuristic for the inventory‐location‐routing problem ⋮ A reactive MILP approach to the multidepot heterogeneous fleet vehicle routing problem with time windows ⋮ Heuristics for multi-attribute vehicle routing problems: a survey and synthesis

Uses Software

• ABACUS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A reoptimization algorithm for the shortest path problem with time windows
• Newton's method for convex programming and Tschebyscheff approximation
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• Stabilized column generation
• An outer approximate subdifferential method for piecewise affine optimization
• Vehicle routing problem with elementary shortest path based column generation
• A Nonlinear Programming Technique for the Optimization of Continuous Processing Systems
• 2-Path Cuts for the Vehicle Routing Problem with Time Windows
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• Decomposition Principle for Linear Programs
• The Cutting-Plane Method for Solving Convex Programs
• A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
• An Algorithm for Least-Squares Estimation of Nonlinear Parameters
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• An Algorithm for Minimax Solution of Overdetermined Systems of Non-linear Equations
• The B<scp>oxstep</scp> Method for Large-Scale Optimization
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
• A method for the solution of certain non-linear problems in least squares
• Solving the asymmetric travelling salesman problem with time windows by branch-and-cut