← 研踪 PaperTrailarXiv:2611.01387 · v1
Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
首次提交 2026-11-01 08:47
版本更新 2026-11-01 08:47
雷达观测 2026-11-04 23:43
摘要
The three-phase time minimization transportation problem partitions the origin-terminal links into three sets used in consecutive phases and minimizes the sum of the phase shipment times. Optimal solutions may leave a phase idle, as in the main example of the original study. We require every phase to carry a positive integer quantity while leaving the split of the total requirement across phases free. Discarding idle solutions from the original algorithm does not, in general, solve this variant. We prove that the optimum is attained by fixing one witness link in each of two phases and deciding the third phase by a single network flow computation, with the optimal Phase-3 time of each witness pair located by binary search. The resulting exact algorithm is strongly polynomial. It extends to any fixed number of phases, whereas, when the number of phases is part of the input, even non-idle feasibility is strongly NP-complete; feasibility alone is fixed-parameter tractable in the number of phases via known rainbow-matching results. We also characterize the minimum time of each phase. On the main example, non-idleness raises the optimum from 38 to 41. On 3,650 random instances with up to $50\times50$ links the algorithm took at most 50.2 seconds, and non-idleness raised the optimal value in 41% of the 2,250 instances with equal phase sizes; on 90 sampled instances it was faster than a mixed integer programming solver on 80 with a direct formulation and on 65 with a tighter threshold formulation.
作者备注：44 pages (37-page main article and 7-page supplement), 0 figures; reproducibility code and data included as ancillary files
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-01 08:47 · 最新观测版本
Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
The three-phase time minimization transportation problem partitions the origin-terminal links into three sets used in consecutive phases and minimizes the sum of the phase shipment times. Optimal solutions may leave a phase idle, as in the main example of the original study. We require every phase to carry a positive integer quantity while leaving the split of the total requirement across phases free. Discarding idle solutions from the original algorithm does not, in general, solve this variant. We prove that the optimum is attained by fixing one witness link in each of two phases and deciding the third phase by a single network flow computation, with the optimal Phase-3 time of each witness pair located by binary search. The resulting exact algorithm is strongly polynomial. It extends to any fixed number of phases, whereas, when the number of phases is part of the input, even non-idle feasibility is strongly NP-complete; feasibility alone is fixed-parameter tractable in the number of phases via known rainbow-matching results. We also characterize the minimum time of each phase. On the main example, non-idleness raises the optimum from 38 to 41. On 3,650 random instances with up to $50\times50$ links the algorithm took at most 50.2 seconds, and non-idleness raised the optimal value in 41% of the 2,250 instances with equal phase sizes; on 90 sampled instances it was faster than a mixed integer programming solver on 80 with a direct formulation and on 65 with a tighter threshold formulation.
查看此版本解读 →查看此版本原文 ↗