A note on the quickest minimum cost transshipment problem

DOI10.1016/J.ORL.2023.03.005MaRDI QIDQ6106530zbMATH OpenOpenAlexFDO

Authors Martin Skutella

Publication date 3 July 2023

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

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

zbMATH Keywords

complexityflow over timetransportation problemtransshipment

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Abstract: Klinz and Woeginger (1995) prove that the minimum cost quickest flow problem is NP-hard. On the other hand, the quickest minimum cost flow problem can be solved efficiently via a straightforward reduction to the quickest flow problem without costs. More generally, we show how the quickest minimum cost transshipment problem can be reduced to the efficiently solvable quickest transshipment problem, thus adding another mosaic tile to the rich complexity landscape of flows over time.

Recommendations

• Faster algorithms for the quickest transshipment problem
• scientific article; zbMATH DE number 1303551
• The quickest flow problem
• The quickest transshipment problem
• The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths

Cites work

• A survey of dynamic network flows
• An introduction to network flows over time
• Cancel-and-tighten algorithm for quickest flow problems
• Constructing maximal dynamic flows from static flows
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 956788 (Why is no real title available?)
• Minimum cost dynamic flows: the series-parallel case
• Minimum-cost dynamic flows: The series-parallel case
• Quickest Flows Over Time
• The quickest transshipment problem

Cited in

(5)

• Notes on the single route lateral transhipment problem
• scientific article; zbMATH DE number 1189258 (Why is no real title available?)
• Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
• Solution of a transshipment problem with uncertain parameters under impaired and enhanced flow
• Minimum-peak-cost flows over time

This page was built for publication: A note on the quickest minimum cost transshipment problem

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