New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem

DOI10.1287/OPRE.1110.0975zbMath1233.90059OpenAlexW1965032790MaRDI QIDQ2879522

Aristide Mingozzi, Roberto Baldacci, Roberto Roberti

Publication date: 26 March 2012

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.1110.0975

zbMATH Keywords

vehicle routingtime windowsdual ascent heuristiccolumn-and-cut generation

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (only showing first 100 items - show all)

Analytic centre stabilization of column generation algorithm for the capacitated vehicle routing problem ⋮ Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows ⋮ Exact Algorithms for the Chance-Constrained Vehicle Routing Problem ⋮ Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization ⋮ Stabilized Column Generation Via the Dynamic Separation of Aggregated Rows ⋮ Learning-Based Branch-and-Price Algorithms for the Vehicle Routing Problem with Time Windows and Two-Dimensional Loading Constraints ⋮ Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling ⋮ A Quasi-polynomial Time Approximation Scheme for Euclidean CVRPTW ⋮ Exact Approach for Integrated Delivery Optimization of E-Commerce and Online-to-Offline Parcels ⋮ Column elimination for capacitated vehicle routing problems ⋮ An exact solution method for home health care scheduling with synchronized services ⋮ The multi‐depot family traveling salesman problem and clustered variants: Mathematical formulations and branch‐&‐cut based methods ⋮ Estimating the marginal cost to deliver to individual customers ⋮ Selective arc‐ng pricing for vehicle routing ⋮ Linear edge costs and labeling algorithms: The case of the time‐dependent vehicle routing problem with time windows ⋮ Branch-and-Price Approaches for Real-Time Vehicle Routing with Picking, Loading, and Soft Time Windows ⋮ Decision Diagrams for Discrete Optimization: A Survey of Recent Advances ⋮ Preprocessing to reduce vehicle capacity for routing problems ⋮ Solving large-scale dynamic vehicle routing problems with stochastic requests ⋮ New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems ⋮ Patient appointment scheduling at hemodialysis centers: an exact branch and price approach ⋮ A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows ⋮ Planning robust drone-truck delivery routes under road traffic uncertainty ⋮ Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows ⋮ Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows ⋮ A survey of attended home delivery and service problems with a focus on applications ⋮ New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows ⋮ Numerically Safe Lower Bounds for the Capacitated Vehicle Routing Problem ⋮ The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands ⋮ Solving vehicle routing problems with intermediate stops using VRPSolver models ⋮ A branch‐and‐price‐based heuristic for the vehicle routing problem with two‐dimensional loading constraints and time windows ⋮ An Exact Solution Framework for Multitrip Vehicle-Routing Problems with Time Windows ⋮ Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation ⋮ A Joint Vehicle Routing and Speed Optimization Problem ⋮ Network-Based Approximate Linear Programming for Discrete Optimization ⋮ A rollout algorithm for the resource constrained elementary shortest path problem ⋮ Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure ⋮ Cut-First Branch-and-Price Second for the Capacitated Arc-Routing Problem ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ A branch-price-and-cut algorithm for the min-maxk-vehicle windy rural postman problem ⋮ New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows ⋮ Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem ⋮ Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times ⋮ Robust Data-Driven Vehicle Routing with Time Windows ⋮ Addressing Orientation Symmetry in the Time Window Assignment Vehicle Routing Problem ⋮ Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty ⋮ A branch-and-price algorithm for the ring-tree facility location problem ⋮ Total distance approximations for routing solutions ⋮ The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem ⋮ Efficient elementary and restricted non-elementary route pricing ⋮ Min-Max vs. Min-Sum vehicle routing: a worst-case analysis ⋮ Freight railway operator timetabling and engine scheduling ⋮ A column generation approach for a multi-attribute vehicle routing problem ⋮ The electric two-echelon vehicle routing problem ⋮ A matheuristic approach for the pollution-routing problem ⋮ The discrete time window assignment vehicle routing problem ⋮ Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations ⋮ A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times ⋮ On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows ⋮ Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows ⋮ Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks ⋮ Lifted and local reachability cuts for the vehicle routing problem with time windows ⋮ A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands ⋮ Pricing routines for vehicle routing with time windows on road networks ⋮ A vehicle routing problem with flexible time windows ⋮ A new formulation and approach for the black and white traveling salesman problem ⋮ Integrating dock-door assignment and vehicle routing with cross-docking ⋮ A branch-and-price approach for a multi-period vehicle routing problem ⋮ Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems ⋮ Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows ⋮ An open source spreadsheet solver for vehicle routing problems ⋮ A column generation approach for the location-routing problem with time windows ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ Robust vehicle routing problem with hard time windows under demand and travel time uncertainty ⋮ Vehicle routing problem with stochastic travel times including soft time windows and service costs ⋮ Algorithms and implementation of a set partitioning approach for modular machining line design ⋮ A branch-price-and-cut algorithm for the workover rig routing problem ⋮ Adapting the \textit{ng}-path relaxation for bike balancing problems ⋮ Hybrid dynamic programming with bounding algorithm for the multi-profit orienteering problem ⋮ A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem ⋮ Multi-neighborhood local search optimization for machine reassignment problem ⋮ Approximation schemes for Euclidean vehicle routing problems with time windows ⋮ Improved branch-cut-and-price for capacitated vehicle routing ⋮ The arc-item-load and related formulations for the cumulative vehicle routing problem ⋮ A branch-cut-and-price algorithm for the traveling salesperson problem with hotel selection ⋮ Combined maintenance and routing optimization for large-scale sewage cleaning ⋮ The joint network vehicle routing game with optional customers ⋮ An exact solution approach for the inventory routing problem with time windows ⋮ Selective routing problem with synchronization ⋮ A POPMUSIC matheuristic for the capacitated vehicle routing problem ⋮ An \(\varepsilon \)-constraint column generation-and-enumeration algorithm for bi-objective vehicle routing problems ⋮ The vehicle routing problem with service level constraints ⋮ Exact algorithms to minimize makespan on single and parallel batch processing machines ⋮ Design of diversified package tours for the digital travel industry: a branch-cut-and-price approach ⋮ Pricing strategies for capacitated ring-star problems based on dynamic programming algorithms ⋮ A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows ⋮ On the exact solution of vehicle routing problems with backhauls ⋮ Partial-route inequalities for the multi-vehicle routing problem with stochastic demands ⋮ Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier ⋮ Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem

Uses Software

• CVRPSP

This page was built for publication: New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem