A large neighbourhood based heuristic for two-echelon routing problems

DOI10.1016/J.COR.2016.06.014MaRDI QIDQ342576zbMATH OpenOpenAlexDBLPWikidataFDO

Authors U. Breunig, V. Schmid, Richard F. Hartl, T. Vidal

Publication date 17 November 2016

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

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

zbMATH Keywords

heuristiclarge neighbourhood searchsplit delivery vehicle routing problemcity logisticsvariable neighbourhood searchadaptive large neighbourhood searchcapacitated vehicle routing problemtwo-echelon vehicle routing problemcovariance matrix adaptation evolution strategymulti-depot vehicle routing problemtwo-echelon location routing problem with single depotwo-echelon location routing problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Transportation, logistics and supply chain management (90B06)

Abstract: In this paper, we address two optimisation problems arising in the context of city logistics and two-level transportation systems. The two-echelon vehicle routing problem and the two-echelon location routing problem seek to produce vehicle itineraries to deliver goods to customers, with transits through intermediate facilities. To efficiently solve these problems, we propose a hybrid metaheuristic which combines enumerative local searches with destroy-and-repair principles, as well as some tailored operators to optimise the selections of intermediate facilities. We conduct extensive computational experiments to investigate the contribution of these operators to the search performance, and measure the performance of the method on both problem classes. The proposed algorithm finds the current best known solutions, or better ones, for 95% of the two-echelon vehicle routing problem benchmark instances. Overall, for both problems, it achieves high-quality solutions within short computing times. Finally, for future reference, we resolve inconsistencies between different versions of benchmark instances, document their differences, and provide them all online in a unified format.

Recommendations

• An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics
• A hybrid GRASP+VND heuristic for the two-echelon vehicle routing problem arising in city logistics
• A survey on two-echelon routing problems
• A variable neighborhood search approach for the two-echelon location-routing problem
• Lower and upper bounds for the two-echelon capacitated location-routing problem

Cites work

• scientific article; zbMATH DE number 4051316 (Why is no real title available?)
• A comparative study of heuristics for a two-level routing-location problem
• A guide to vehicle routing heuristics
• A hybrid GRASP+VND heuristic for the two-echelon vehicle routing problem arising in city logistics
• A method for solving traveling-salesman problems
• A survey on two-echelon routing problems
• An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics
• An exact algorithm for the two-echelon capacitated vehicle routing problem
• Branch-and-price algorithms for the two-echelon capacitated vehicle routing problem
• Heuristics for multi-attribute vehicle routing problems: a survey and synthesis
• Lower and upper bounds for the two-echelon capacitated location-routing problem
• New families of valid inequalities for the two-echelon vehicle routing problem
• Record breaking optimization results using the ruin and recreate principle
• Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking
• The granular tabu search and its application to the vehicle-routing problem

Cited in

(27)

• A progressive filtering heuristic for the location-routing problem and variants
• Combining very large scale and ILP based neighborhoods for a two-level location problem
• An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem
• A bi-objective two-echelon pollution routing problem with simultaneous pickup and delivery under multiple time windows constraint
• The electric two-echelon vehicle routing problem
• An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics
• A time-division distribution strategy for the two-echelon vehicle routing problem with demand blowout
• A two-echelon location routing problem with mobile satellites for last-mile delivery: mathematical formulation and clustering-based heuristic method
• The two-echelon vehicle routing problem with covering options: city logistics with cargo bikes and parcel lockers
• A multi-commodity two-echelon capacitated vehicle routing problem with time windows: model formulations and solution approach
• A parallelised large neighbourhood search heuristic for the asymmetric two-echelon vehicle routing problem with swap containers for cargo-bicycles
• Two-echelon vehicle routing problem with satellite bi-synchronization
• A branch-and-price algorithm for location-routing problems with pick-up stations in the last-mile distribution system
• Two-echelon vehicle routing problems: a literature review
• A benders decomposition algorithm for a bid generation problem in the procurement of three-echelon transportation services
• A neighborhood search and set cover hybrid heuristic for the two-echelon vehicle routing problem
• An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization
• A robust optimization framework for two-echelon vehicle and UAV routing for post-disaster humanitarian logistics operations
• A concise guide to existing and emerging vehicle routing problem variants
• The vehicle routing problem with arrival time diversification on a multigraph
• The two-echelon capacitated electric vehicle routing problem with battery swapping stations: formulation and efficient methodology
• An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization
• Hybrid adaptive large neighborhood search for vehicle routing problems with depot location decisions
• A matheuristic for a 2-echelon vehicle routing problem with capacitated satellites and reverse flows
• A hybrid GRASP+VND heuristic for the two-echelon vehicle routing problem arising in city logistics
• A survey on two-echelon routing problems
• A variable neighborhood search approach for the two-echelon location-routing problem

Describes a project that uses

Uses Software

• R
• OR-Library
• CMA-ES
• VRP

This page was built for publication: A large neighbourhood based heuristic for two-echelon routing problems

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