Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty

DOI10.1287/IJOC.2019.0923MaRDI QIDQ3386790zbMATH OpenOpenAlexWikidataFDO

Authors Anirudh Subramanyam, Panagiotis P. Repoussis, Chrysanthos E. Gounaris

Publication date 7 January 2021

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.04348

zbMATH Keywords

branch-and-cutdemand uncertaintylocal searchmetaheuristicsrobust optimizationvehicle routing

Mathematics Subject Classification ID

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

Abstract: This paper studies robust variants of an extended model of the classical Heterogeneous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles with different capacities, availabilities, fixed costs and routing costs is used to serve customers with uncertain demand. This model includes, as special cases, all variants of the HVRP studied in the literature with fixed and unlimited fleet sizes, accessibility restrictions at customer locations, as well as multiple depots. Contrary to its deterministic counterpart, the goal of the robust HVRP is to determine a minimum-cost set of routes and fleet composition that remains feasible for all demand realizations from a pre-specified uncertainty set. To solve this problem, we develop robust versions of classical node- and edge-exchange neighborhoods that are commonly used in local search and establish that efficient evaluation of the local moves can be achieved for five popular classes of uncertainty sets. The proposed local search is then incorporated in a modular fashion within two metaheuristic algorithms to determine robust HVRP solutions. The quality of the metaheuristic solutions is quantified using an integer programming model that provides lower bounds on the optimal solution. An extensive computational study on literature benchmarks shows that the proposed methods allow us to obtain high quality robust solutions for different uncertainty sets and with minor additional effort compared to deterministic solutions.

Recommendations

• The robust capacitated vehicle routing problem under demand uncertainty
• The robust vehicle routing problem with time windows: solution by branch and price and cut
• Robust optimisation approach for vehicle routing problems with uncertainty
• Heuristic approaches for the robust vehicle routing problem
• Solving the bi-objective Robust Vehicle Routing Problem with uncertain costs and demands

Cites work

• A column generation approach to the heterogeneous fleet vehicle routing problem
• A Computational Study Of A New Heuristic For The Site-Dependent Vehicle Routing Problem
• A heuristic column generation method for the heterogeneous fleet VRP
• A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• A Tabu Search Algorithm For The Site Dependent Vehicle Routing Problem With Time Windows
• A tabu search heuristic for periodic and multi-depot vehicle routing problems
• A unified exact method for solving different classes of vehicle routing problems
• An exact algorithm for the asymmetrical capacitated vehicle routing problem
• Dynamic programming and optimal control. Vol. 1.
• Easy and difficult objective functions for max cut
• Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems
• Fast local search algorithms for the handicapped persons transportation problem
• Formulations and valid inequalities for the heterogeneous vehicle routing problem
• Heuristic approaches for the robust vehicle routing problem
• scientific article; zbMATH DE number 1016966 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Industrial aspects and literature survey: fleet composition and routing
• Robust optimization
• Robust optimization for the vehicle routing problem with multiple deliverymen
• Routing optimization with time windows under uncertainty
• Solving the bi-objective Robust Vehicle Routing Problem with uncertain costs and demands
• Solving the Orienteering Problem through Branch-and-Cut
• The fleet size and mix vehicle routing problem
• The Price of Robustness
• The robust capacitated vehicle routing problem under demand uncertainty
• The robust vehicle routing problem with time windows
• The vehicle routing problem. Latest advances and new challenges.
• Theory and applications of robust optimization
• Thirty years of heterogeneous vehicle routing
• Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs
• Vehicle Routing

Cited in

(27)

• Dantzig-Wolfe decomposition approach to the vehicle assignment problem with demand uncertainty in a hybrid hub-and-spoke network
• Robust optimisation approach for vehicle routing problems with uncertainty
• An inverse robust optimisation approach for a class of vehicle routing problems under uncertainty
• Robust vehicle routing under uncertainty via branch-price-and-cut
• A multi-objective vehicle routing and scheduling problem with uncertainty in customers' request and priority
• Robust optimization for relief logistics planning under uncertainties in demand and transportation time
• Robust optimization for the vehicle routing problem with multiple deliverymen
• Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen
• The consistent vehicle routing problem with heterogeneous fleet
• The robust capacitated vehicle routing problem under demand uncertainty
• Solving the bi-objective Robust Vehicle Routing Problem with uncertain costs and demands
• Heuristic approaches for the robust vehicle routing problem
• A two-stage robust optimization approach for the mobile facility fleet sizing and routing problem under uncertainty
• Comparing mathematical and a metaheuristic method for vehicle routing problem with uncertain demand
• A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty
• scientific article; zbMATH DE number 7366007 (Why is no real title available?)
• A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
• Distributionally robust equilibrious hybrid vehicle routing problem under twofold uncertainty
• Robust optimization for the electric vehicle pickup and delivery problem with time windows and uncertain demands
• The road train optimization problem with load assignment
• Solving real-world vehicle routing problems in uncertain environments
• A practical and robust approach for solving the multi-compartment vehicle routing problem under demand uncertainty using machine learning
• Integrated and sequential algorithms for the robust two-echelon location-routing problem under demand uncertainty
• New formulations for the robust vehicle routing problem with time windows under demand and travel time uncertainty
• Exact methods and a variable neighborhood search for the robust capacitated p-median problem
• Beyond fifty years of vehicle routing: insights into the history and the future
• The robust pickup and delivery problem with time windows

Describes a project that uses

Uses Software

• VRP
• CVRPSP

This page was built for publication: Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386790)