Fixed Charges and Quantity Discounts in Unbalanced Transportation: Measured Limits of Exact Solving, an Amortized-Proxy Heuristic, and the Seed-Inheritance Anatomy of Ant Colony Optimization

Abstract

The unbalanced transportation problem rarely appears in practice with the symmetric penalties that textbooks assume: unshipped supply and unfilled demand carry heterogeneous costs, and carrier contracts add per-lane fixed charges and all-unit quantity discounts, which together render the model non-convex. What does the uniform-dummy convention actually cost, where does certified exact solving stop, what remains achievable in seconds, and what does a seeded ant colony contribute beyond its seed? We answer with one unified FCTP-QD model, one true-cost functional that scores every plan identically, six pipeline families, a certified MILP benchmark, and a seed-hierarchy ablation on instances from 3×4 to 200×200. The convention pays 5.11–89.01% above the MILP incumbent at nominal fixed charges, and the heterogeneous linear remedy, exact in the purely linear case, breaks down by +14.35–60.37% once charges become realistic. Certified MILP gaps grow from 0% up to 20×20 (at most ≈1.1% through 50×50) to 23.77% at 200×200, and on the 200×200 discount instance the solver returns no feasible incumbent within its 120 s budget. The amortized fixed-charge proxy LP, by contrast, is numerically indistinguishable from the 120 s incumbent at 200×200 (+0.003%) in about 0.5 s, and on the 200×200 discount instance it is the only pipeline returning a competitive plan (76,859.52, against 79,839.69 for the next-best linear pipeline). The dissection is unambiguous: strong LP seeds pass through the colony unchanged (±0), weaker seeds stall at their own basin, final quality rank equals seed rank, and unseeded colonies run +9.3–88.7% worse (Wilcoxon p=9.77e-04). Swarm quality here is inherited, not created. The result is a measured, honest benchmarking template — not an indictment of swarm methods, but a protocol for isolating what any mechanism adds.