Heuristics for unequal weight delivery problems with a fixed error guarantee

DOI10.1016/0167-6377(87)90012-5zbMath0632.90083OpenAlexW2017372614MaRDI QIDQ1095815

Bezalel Gavish, Kemal Altinkemer

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0167-6377(87)90012-5

zbMATH Keywords

polynomial time algorithmheuristicfully polynomial procedureoptimal partitioning of a travelling salesman tourunequal weight delivery problemworst case error performance

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05)

Related Items (32)

Vehicle routing with split deliveries ⋮ A Fast $$(2 + 2/7)$$-Approximation Algorithm for Capacitated Cycle Covering ⋮ Survivable network design: the capacitated minimum spanning network problem ⋮ Routing problems: A bibliography ⋮ Improved bounds for vehicle routing solutions ⋮ Improved approximations for capacitated vehicle routing with unsplittable client demands ⋮ Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem ⋮ Improved approximation algorithms for cumulative VRP with stochastic demands ⋮ Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension ⋮ Matheuristics with performance guarantee for the unsplit and split delivery capacitated vehicle routing problem ⋮ Routing vehicles to minimize fuel consumption ⋮ Topological design of telecommunication networks --- local access design methods ⋮ Capacitated Vehicle Routing with Non-uniform Speeds ⋮ Routing a Heterogeneous Fleet of Vehicles ⋮ Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution ⋮ Analysis of heuristics for the design of tree networks ⋮ Split delivery routing ⋮ A new heuristic for the fleet size and mix vehicle routing problem ⋮ Minimizing latency of capacitated \(k\)-tours ⋮ Approximation Algorithms for Cumulative VRP with Stochastic Demands ⋮ Capacitated Vehicle Routing with Nonuniform Speeds ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Approximation algorithms for the load-balanced capacitated vehicle routing problem ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Locating Depots for Capacitated Vehicle Routing ⋮ A genetic algorithm for service level based vehicle scheduling ⋮ Selecting Good a Priori Sequences for Vehicle Routing Problem with Stochastic Demand ⋮ A constant approximation algorithm for the uniform a priori capacitated vehicle routing problem with unit demands ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem ⋮ A tight approximation algorithm for multi-vehicle CVRP with unsplittable demands on a line ⋮ Topological design of ring networks ⋮ A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering

Uses Software

• VRP

Cites Work

• An approach for solving a class of transportation scheduling problems
• A vehicle routing improvement algorithm comparison of a greedy and a matching implementation for inventory routing
• Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees
• Bounds and Heuristics for Capacitated Routing Problems
• Heuristics with Constant Error Guarantees for the Design of Tree Networks
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Topological design of centralized computer networks—formulations and algorithms
• Tight bounds for christofides' traveling salesman heuristic
• Unnamed Item
• Unnamed Item

This page was built for publication: Heuristics for unequal weight delivery problems with a fixed error guarantee