Vehicle routing with subtours

DOI10.1016/J.DISOPT.2019.03.003MaRDI QIDQ2010917zbMATH OpenOpenAlexWikidataFDO

Authors Stephan Held, Jochen Könemann, Jens Vygen

Publication date 28 November 2019

Published in Discrete Optimization (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(1)

• Minimum Vehicle Routing with a Common Deadline

Describes a project that uses

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)