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

Ali Mahmoud Assabri; Mohamed Al-Issawi Kajman; Naji Abdalaziz Ali; Abdulbasat Abdulghafar

المؤلفون

Ali Mahmoud Assabri Department of Engineering Management, College of Technical Sciences, Bani Walid, Libya المؤلف
Mohamed Al-Issawi Kajman Department of Computing and Information Technology, College of Technical Sciences, Bani Walid, Libya المؤلف
Naji Abdalaziz Ali Department of Mechanical Engineering, College of Technical Sciences, Bani Walid, Libya المؤلف
Abdulbasat Abdulghafar Department of Engineering Management, College of Technical Sciences, Bani Walid, Libya المؤلف

الكلمات المفتاحية:

fixed-charge transportation، quantity discounts، unbalanced transportation problem، ant colony optimization، matheuristic seeding، amortized heuristic، computational benchmarking

الملخص

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.

التنزيلات

تنزيل البيانات ليس متاحًا بعد.

REFERENCES

[1] F. L. Hitchcock, “The distribution of a product from several sources to numerous localities,” Journal of Mathematics and Physics, vol. 20, no. 1–4, pp. 224–230, 1941.

[2] T. C. Koopmans, “Optimum utilization of the transportation system,” Econometrica, vol. 17, pp. 136–146, 1949.

[3] F. S. Hillier and G. J. Lieberman, Introduction to Operations Research, 11th ed. New York, NY, USA: McGraw-Hill, 2021.

[4] H. A. Taha, Operations Research: An Introduction, 10th ed. Harlow, UK: Pearson, 2017.

[5] M. E. B. Brigden, “A variant of the transportation problem in which the constraints are of mixed type,” Operational Research Quarterly, vol. 25, no. 3, pp. 437–445, 1974.

[6] P. Pandian and G. Natarajan, “A new approach for solving transportation problems with mixed constraints,” Journal of Physical Sciences, vol. 14, pp. 53–61, 2010.

[7] M. M. Ahmed, N. Sultana, A. R. Khan, and S. Uddin, “An innovative approach to obtain an initial basic feasible solution for the transportation problems,” Journal of Physical Sciences, vol. 22, pp. 23–42, 2017.

[8] M. Dorigo, Optimization, Learning and Natural Algorithms, Ph.D. dissertation, Politecnico di Milano, Milan, Italy, 1992.

[9] M. Dorigo and T. Stützle, “Ant colony optimization: Overview and recent advances,” in Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds. New York, NY, USA: Springer, 2019, pp. 311–351.

[10] C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: Overview and conceptual comparison,” ACM Computing Surveys, vol. 35, no. 3, pp. 268–308, 2003.

[11] J. H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, MI, USA: University of Michigan Press, 1975.

[12] J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proc. IEEE Int. Conf. Neural Networks, Perth, WA, Australia, 1995, pp. 1942–1948.

[13] R. Jovanović, M. Tuba, and S. Voß, “An ant colony optimization algorithm for partitioning graphs with supply and demand,” Applied Soft Computing, vol. 41, pp. 317–330, 2016.

[14] D. Teodorović, “Swarm intelligence systems for transportation engineering,” Transportation Research Part C: Emerging Technologies, vol. 16, no. 6, pp. 651–667, 2008.

[15] D. H. Wolpert and W. G. Macready, “No free lunch theorems for optimization,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 67–82, 1997.

[16] T. Stamadianos, A. Taxidou, M. Marinaki, and Y. Marinakis, “Swarm intelligence and nature inspired algorithms for solving vehicle routing problems: A survey,” Operational Research, vol. 24, no. 3, Art. no. 47, 2024.

[17] F. A. Wireko, I. D. K. Mensah, E. N. A. Aborhey, S. A. Appiah, C. Sebil, and J. Ackora-Prah, “The maximum range method for finding initial basic feasible solution for transportation problems,” Results in Control and Optimization, vol. 19, Art. no. 100551, 2025.

[18] M. Korzeń and I. Gisterek, “Applying ant colony optimization to reduce tram journey times,” Sensors, vol. 24, no. 19, Art. no. 6226, 2024.

[19] H. Wu and Y. Gao, “An ant colony optimization based on local search for the vehicle routing problem with simultaneous pickup–delivery and time window,” Applied Soft Computing, vol. 139, Art. no. 110203, 2023.

[20] M. B. Fakhrzad, F. Goodarzian, and A. M. Golmohammadi, “Addressing a fixed charge transportation problem with multi-route and different capacities by novel hybrid meta-heuristics,” Journal of Industrial and Systems Engineering, vol. 12, no. 1, pp. 167–184, 2019.

[21] R. Elshaer and H. Awad, “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants,” Computers & Industrial Engineering, vol. 140, Art. no. 106242, 2020.

[22] E. M. U. S. B. Ekanayake, S. P. C. Perera, W. B. Daundasekara, and Z. A. M. S. Juman, “A modified ant colony optimization algorithm for solving a transportation problem,” Journal of Advances in Mathematics and Computer Science, vol. 35, no. 5, pp. 83–101, 2020.

[23] K. Govindan, A. Jafarian, and V. Nourbakhsh, “Designing a sustainable supply chain network integrated with vehicle routing: A comparison of hybrid swarm intelligence metaheuristics,” Computers & Operations Research, vol. 110, pp. 220–235, 2019.

[24] M. L. Balinski, “Fixed-cost transportation problems,” Naval Research Logistics Quarterly, vol. 8, no. 1, pp. 41–54, 1961, doi: 10.1002/nav.3800080104.

[25] V. Adlakha and K. Kowalski, “A simple heuristic for solving small fixed-charge transportation problems,” Omega, vol. 31, no. 3, pp. 205–211, 2003, doi: 10.1016/S0305-0483(03)00025-2.

[26] M. Hajiaghaei-Keshteli, M. Molla-Alizadeh-Zavardehi, and R. Tavakkoli-Moghaddam, “Addressing a nonlinear fixed-charge transportation problem using a spanning tree-based genetic algorithm,” Computers & Industrial Engineering, vol. 59, no. 2, pp. 259–271, 2010, doi: 10.1016/j.cie.2010.04.007.

[27] S. Molla-Alizadeh-Zavardehi, M. Hajiaghaei-Keshteli, and R. Tavakkoli-Moghaddam, “Solving a capacitated fixed-charge transportation problem by artificial immune and genetic algorithms with a Prüfer number representation,” Expert Systems with Applications, vol. 38, no. 8, pp. 10462–10474, 2011, doi: 10.1016/j.eswa.2011.02.093.

[28] V. Balachandran and A. Perry, “Transportation type problems with quantity discounts,” Naval Research Logistics Quarterly, vol. 23, no. 2, pp. 195–209, 1976, doi: 10.1002/nav.3800230203.