A New Integer Linear Programming Model of Transportation Problem

Yan Dong, Yixuan Li, Jian‐Min Zuo, Yi JinTheoretical 2025 · DOI

TL;DR

This paper introduces a refined Integer Linear Programming (ILP) model that optimizes logistics by blending classical transportation problems with Minimum Spanning Tree (MST) techniques. By incorporating intermediate warehouses as flow-balancing nodes, the researchers provide a more realistic framework for minimizing costs in complex supply chains, specifically demonstrated through a case study of China’s automobile industry.

What Problem Does This Paper Address?

The "transportation problem" is a cornerstone of operations research: how do you move goods from point A to point B at the lowest possible cost? While the classical model is well-understood, real-world logistics are rarely a straight line from factory to storefront.

Modern supply chains involve a "topological graph" of nodes, including intermediate warehouses that act as buffers. The challenge lies in managing these intermediate points—ensuring that goods don't just sit there indefinitely and that the flow remains balanced across the entire network. The authors identify a gap in existing models that often struggle to adapt to these multi-layered, dynamic environments or fail to provide practical, scalable solutions for large-scale industrial applications.

Methods

The authors propose a novel ILP model that treats the logistics network as an undirected graph $G(V, E)$.

  • Flow Balance Constraints: The heart of the model is a set of equations ensuring that for any intermediate warehouse node, the quantity of products entering equals the quantity leaving. For factories, the net flow is negative (supply), and for retail stores, it is positive (demand).
  • MST Integration: The model seeks an "optimal spanning tree." By ensuring the solution is acyclic (no loops), the model identifies the most efficient paths that connect all necessary nodes without redundant travel.
  • Cycle Prevention: A specific constraint ($x^f_{ij} + x^f_{ji} \le \max\{x^f_{ij}, x^f_{ji}\}$) is used to ensure that if goods are moving from node $i$ to $j$, they aren't simultaneously moving from $j$ to $i$, effectively preventing inefficient circular routing.
  • Computational Tools: The model was implemented in Python and solved using the CPLEX solver, a high-performance mathematical programming tool capable of handling large-scale linear and integer challenges.

Datasets

The study utilizes real-world data from the China Association of Automobile Manufacturers (CAAM) as of June 2024.

  • Industry Context: The paper cites production and sales figures for passenger vehicles, commercial vehicles, and New Energy Vehicles (NEVs) in China.
  • Experimental Groups: The researchers created four specific datasets based on major Chinese automotive entities:
  • Guangzhou Vehicle Co., Ltd. (GVC)
    1. Beyond Guangzhou Vehicle (BGV)
    2. Shanghai Vehicle Co., Ltd. (SVC)
    3. Anhui Vehicle Co., Ltd. (AGC)
  • Parameters: Each dataset includes factory output capacities and weekly demands for six specific retail regions (LN, FJ, BJ, YN, SX, GZ).

Key Insights and Ideas

  • Warehouses as Active Nodes: Unlike models that treat warehouses as static endpoints, this model treats them as active "flow-through" nodes. This allows the system to use warehouses to "balance" the network, making it more flexible to real-world infrastructure.
  • Sparsity is an Advantage: The resulting decision matrix is "sparse" (mostly zeros). This is a feature, not a bug—it indicates that the model successfully identifies a few high-efficiency paths (the spanning tree) rather than spreading resources across every possible road.
  • Beyond Distance: The authors emphasize that "cost" ($c_{ij}$) in their model isn't just physical distance; it incorporates road conditions and infrastructure quality, providing a more nuanced "monetary expense" metric.

Key Results

The researchers successfully generated optimal transportation maps for the four automotive groups.

  • Scalability: By limiting the independent variables to under 1,000 per experimental group, the researchers ensured the problem remained computationally manageable for commercial solvers while still reflecting industrial complexity.
  • Visual Optimization: The results (visualized in Figure 4 of the paper) show clear, tree-like structures where the thickness of the edges represents the volume of goods. This provides logistics managers with an intuitive "transportation plan" that guarantees total supply meets total demand at the lowest cost.
  • Industry Applicability: The model confirmed its ability to handle the specific supply-demand ratios of the 2024 Chinese auto market, where production and sales are in the millions of units.

Limitations and Future Work

While the model is a significant step forward, the authors acknowledge several areas for growth:

  • Static vs. Dynamic: The current model uses fixed demand and supply. Future iterations aim to integrate time-series data to account for fluctuating market demands and variable production rates.
  • Capacity Constraints: The current model assumes edges can handle any volume. The authors suggest adding "maximum transport limits" for each edge to make the model even more robust.
  • Multi-Product Complexity: Currently, the model focuses on a single type of product. Expanding this to handle multiple product types (e.g., different car models or parts) within the same network is a primary goal for future research.

Summary updated

Abstract

The transportation problem has been a central focus in operational research, to determine the most cost-effective routes for moving goods or people. With the continuous development of modern logistics and the increasing complexity of supply chain management, optimizing transportation systems has become more crucial than ever. This paper introduces a novel approach that combines classical transportation problems with Minimum Spanning Tree (MST) techniques, enabling a more efficient way to address real-world logistics issues. Our model incorporates a topological graph that includes not only factories and retail stores but also intermediate warehouses to balance the flow of goods. To solve this problem efficiently, we propose a new Intger linear programming (ILP) model with flow balance constraints and using a CPLEX solver to get the numerical results. Through numerical experiments based on Chinas automobile transportation industry, we demonstrate the practical applicability of our approach in minimizing transportation costs. Additionally, we discuss future research directions,including the integration of dynamic demand and production capabilities.
BibTeX
@inproceedings{dong2025new,
  author = {Yan Dong and Yixuan Li and Jian‐Min Zuo and Yi Jin},
  title = {{A New Integer Linear Programming Model of Transportation Problem}},
  booktitle = {Theoretical},
  year = {2025},
  doi = {10.54254/2753-8818/2025.23342},
}

Loading related content...

Figure