A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet
From MaRDI portal
Publication:1730643
DOI10.1007/S10479-017-2642-9zbMATH Open1434.90029arXiv1803.01930OpenAlexW2963986315MaRDI QIDQ1730643FDOQ1730643
Authors: Puca Huachi Vaz Penna, A. Subramanian, Luiz S. Ochi, T. Vidal, Christian Prins 
Publication date: 6 March 2019
Published in: Annals of Operations Research (Search for Journal in Brave)
Abstract: We consider a family of Rich Vehicle Routing Problems (RVRP) which have the particularity to combine a heterogeneous fleet with other attributes, such as backhauls, multiple depots, split deliveries, site dependency, open routes, duration limits, and time windows. To efficiently solve these problems, we propose a hybrid metaheuristic which combines an iterated local search with variable neighborhood descent, for solution improvement, and a set partitioning formulation, to exploit the memory of the past search. Moreover, we investigate a class of combined neighborhoods which jointly modify the sequences of visits and perform either heuristic or optimal reassignments of vehicles to routes. To the best of our knowledge, this is the first unified approach for a large class of heterogeneous fleet RVRPs, capable of solving more than 12 problem variants. The efficiency of the algorithm is evaluated on 643 well-known benchmark instances, and 71.70% of the best known solutions are either retrieved or improved. Moreover, the proposed metaheuristic, which can be considered as a matheuristic, produces high quality solutions with low standard deviation in comparison with previous methods. Finally, we observe that the use of combined neighborhoods does not lead to significant quality gains. Contrary to intuition, the computational effort seems better spent on more intensive route optimization rather than on more intelligent and frequent fleet re-assignments.
Full work available at URL: https://arxiv.org/abs/1803.01930
Recommendations
- A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows
- A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem
- A hybrid algorithm for a class of vehicle routing problems
- The multi-depot vehicle routing problem with heterogeneous vehicle fleet: formulation and a variable neighborhood search implementation
- A hybrid algorithm for the heterogeneous fleet vehicle routing problem
Approximation methods and heuristics in mathematical programming (90C59) Transportation, logistics and supply chain management (90B06)
Cites Work
- A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows
- Heuristics for multi-attribute vehicle routing problems: a survey and synthesis
- A unified solution framework for multi-attribute vehicle routing problems
- The truck dispatching problem
- Split delivery routing
- A unified tabu search heuristic for vehicle routing problems with time windows
- A general heuristic for vehicle routing problems
- Variable neighbourhood search: methods and applications
- Exact algorithms for routing problems under vehicle capacity constraints
- A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem.
- A new mixed integer linear model for a rich vehicle routing problem with docking constraints
- Rich vehicle routing problems: from a taxonomy to a definition
- A hybrid algorithm for a class of vehicle routing problems
- A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows
- A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem
- Efficient frameworks for greedy split and new depth first search split procedures for routing problems
- A unified heuristic for a large class of vehicle routing problems with backhauls
- A general vehicle routing problem
- Industrial aspects and literature survey: fleet composition and routing
- A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem
- Probabilistic diversification and intensification in local search for vehicle routing
- A hybrid algorithm for the heterogeneous fleet vehicle routing problem
- Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows
- A column generation approach to the heterogeneous fleet vehicle routing problem
- A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows
- An interactive GRAMPS algorithm for the heterogeneous fixed fleet vehicle routing problem with and without backhauls
- Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil
- The fleet size and mix vehicle routing problem
- A multi-level composite heuristic for the multi-depot vehicle fleet mix problem
- A tabu search heuristic for the heterogeneous fleet vehicle routing problem
- Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case
- A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem
- A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem
- Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs
- The fleet size and mix vehicle routing problem with time windows
- Thirty years of heterogeneous vehicle routing
- An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot
- The multi-depot vehicle routing problem with heterogeneous vehicle fleet: formulation and a variable neighborhood search implementation
- A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows
- A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing
- A heuristic column generation method for the heterogeneous fleet VRP
- A rich vehicle routing problem dealing with perishable food: a case study
- Tabu search variants for the mix fleet vehicle routing problem
- A heuristic for vehicle fleet mix problem using tabu search and set partitioning
- Title not available (Why is that?)
- Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet
- A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem
- A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows
- A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem
- An exact solution framework for a broad class of vehicle routing problems
- An iterated local search heuristic for the split delivery vehicle routing problem
- A Tabu Search Algorithm For The Site Dependent Vehicle Routing Problem With Time Windows
- Implementation and Testing of a Primal-Dual Algorithm for the Assignment Problem
Cited In (42)
- A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length
- Simultaneous product and service delivery vehicle routing problem with time windows and order release dates
- The consistent vehicle routing problem with heterogeneous fleet
- An adaptive iterated local search heuristic for the heterogeneous fleet vehicle routing problem
- A Hybrid Metaheuristic for a Real Life Vehicle Routing Problem
- Title not available (Why is that?)
- A POPMUSIC matheuristic for the capacitated vehicle routing problem
- Implicit depot assignments and rotations in vehicle routing heuristics
- How managerial perspectives affect the optimal fleet size and mix model: a multi-objective approach
- Title not available (Why is that?)
- A hybrid algorithm of local search for the heterogeneous fixed fleet vehicle routing problem
- Adaptive large neighborhood search for vehicle routing problems with transshipment facilities arising in city logistics
- A general heuristic for vehicle routing problems
- An improved transformer model with multi-head attention and attention to attention for low-carbon multi-depot vehicle routing problem
- Resolving a vehicle routing problem with heterogeneous fleet, mixed backhauls and time windows using cuckoo behaviour approach
- A hybrid algorithm for a class of vehicle routing problems
- A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers
- Asynchronous optimization of part logistics routing problem
- An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem
- A concise guide to existing and emerging vehicle routing problem variants
- Robust Optimization of a Broad Class of Heterogeneous Vehicle Routing Problems Under Demand Uncertainty
- A general VNS for the multi-depot open vehicle routing problem with time windows
- A general vehicle routing problem
- A heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem
- An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints
- A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows
- A heuristic for vehicle fleet mix problem using tabu search and set partitioning
- MineReduce: an approach based on data mining for problem size reduction
- A unified solution framework for multi-attribute vehicle routing problems
- A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem
- A variable neighborhood search approach to solve the order batching problem with heterogeneous pick devices
- A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem
- Vehicle routing problem with uniform private fleet and common carrier: a node subset heuristic
- A hybrid iterated local search heuristic for the traveling salesperson problem with hotel selection
- A tabu search heuristic for the heterogeneous fleet vehicle routing problem
- On the exact solution of vehicle routing problems with backhauls
- Bi-objective optimization model for the heterogeneous dynamic dial-a-ride problem with no rejects
- Iterated tabu search for the mix fleet vehicle routing problem with heterogenous electric vehicles
- Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case
- Hybrid data mining heuristics for the heterogeneous fleet vehicle routing problem
- Systematic review of the latest scientific publications on the vehicle routing problem
- A review of the role of heuristics in stochastic optimisation: from metaheuristics to learnheuristics
Uses Software
This page was built for publication: A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1730643)
