Vehicle routing with subtours

DOI10.1016/J.DISOPT.2019.03.003zbMATH Open1474.90378arXiv1801.04991OpenAlexW2962997605WikidataQ128135279 ScholiaQ128135279MaRDI QIDQ2010917FDOQ2010917

Authors: Stephan Held, Jochen Könemann, Jens Vygen 

Publication date: 28 November 2019

Published in: Discrete Optimization (Search for Journal in Brave)

Abstract: When delivering items to a set of destinations, one can save time and cost by passing a subset to a sub-contractor at any point en route. We consider a model where a set of items are initially loaded in one vehicle and should be distributed before a given deadline {Delta}. In addition to travel time and time for deliveries, we assume that there is a fixed delay for handing over an item from one vehicle to another. We will show that it is easy to decide whether an instance is feasible, i.e., whether it is possible to deliver all items before the deadline {Delta}. We then consider computing a feasible tour of minimum cost, where we incur a cost per unit distance traveled by the vehicles, and a setup cost for every used vehicle. Our problem arises in practical applications and generalizes classical problems such as shallow-light trees and the bounded-latency problem. Our main result is a polynomial-time algorithm that, for any given {epsilon} > 0 and any feasible instance, computes a solution that delivers all items before time (1+ {epsilon}){Delta} and has cost O(1 + 1 / {epsilon}) OPT, where OPT is the minimum cost of any feasible solution. We show that our result is best possible in the sense that any improvement would lead to progress on 25-year-old questions on shallow-light trees.

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

Recommendations

• Vehicle Routeing with Multiple Use of Vehicles
• A subpath ejection method for the vehicle routing problem
• scientific article; zbMATH DE number 3912105
• scientific article; zbMATH DE number 956786
• scientific article; zbMATH DE number 3912104
• Vehicle routing problems with multiple trips
• Vehicle routing problems with multiple trips
• A new subtour elimination constraint for the vehicle routing problem
• Vehicle Routing
• Tour splitting algorithms for vehicle routing problems

zbMATH Keywords

approximation algorithmsvehicle routingshallow-light trees

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06)

Cites Work

• The Steiner tree problem on graphs: inapproximability results
• The Traveling Salesman Problem with Distances One and Two
• Min-max tree covers of graphs.
• Approximating the \(k\)-traveling repairman problem with repair times
• Approximation algorithms for distance constrained vehicle routing problems
• Vehicle Routing
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Minimum Makespan Multi-vehicle Dial-a-Ride
• Approximation results for min-max path cover problems in vehicle routing
• Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
• Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
• Approximations for minimum and min-max vehicle routing problems
• New inapproximability bounds for TSP
• Approximation hardness of min-max tree covers
• Shallow-Light Steiner Arborescences with Vertex Delays
• Balancing minimum spanning trees and shortest-path trees
• To fill or not to fill
• Capacitated vehicle routing with nonuniform speeds

Cited In (1)

• Minimum Vehicle Routing with a Common Deadline

Uses Software

• VRP

This page was built for publication: Vehicle routing with subtours

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