1. Introduction
Operations research and cybernetics [1], using mathematics and computer science as core tools, focuses on addressing modeling, analysis, planning, design, control, and optimization challenges in diverse systems. As a critical research domain within this field, transportation problems hold a pivotal position in socioeconomic development. Encompassing scenarios from material distribution and passenger transport to enterprise operations and global supply chain management, the effective resolution of transportation challenges significantly boosts resource allocation efficiency, cuts costs, and enhances service quality, thereby playing a key role in driving progress across industries. The study defines transportation problems as a category of linear programming with specific structural characteristics, explicitly clarifying their mathematical essence through constraints in transportation tables and supply-demand equilibrium conditions, thereby establishing a standardized theoretical framework to support subsequent methodological research. By systematically reviewing the evolution of mathematical modeling and solution approaches from classical tabular methods to dual theory, the research addresses logical gaps between discrete knowledge points and constructs a structured knowledge framework. Enhancing transportation efficiency reduces logistics costs, ultimately strengthening industrial competitiveness.
2. Definition and Mathematical Model of the Transportation Problem
2.1. Definition
The transportation problem [2] is a type of linear programming problem with special structure. Its typical scenario involves transporting a certain product from multiple sources to multiple destinations. Given the supply capacity of each source and the demand requirement of each destination, the task is to determine the optimal transportation plan from numerous feasible options that minimizes the total transportation cost.
2.2. Mathematical Model
Suppose there are
sources with supply amounts
and
destinations with demand amounts
. The transportation cost per unit from source
to destination
is
, and the transportation quantity from source
to destination
is
. The mathematical model for the transportation problem can be expressed as:
If the total output in the transportation problem is equal to the total sale volume (
), this kind of transportation problem is called a transportation problem with balanced production and sale [3]. Otherwise, it is called a transportation problem with unbalanced production and sale.
The transportation problem with unbalanced production and sales can be transformed into a transportation problem with balanced production and sales by adding a fictitious source or a fictitious destination. The coefficient matrix of the constraint equations in the transportation model has a special structure. Each column contains only two elements equal to 1, and the remaining elements are all 0.
3. Solution Methods for Transportation Problems
3.1. Tabular Method [4]
3.1.1. Initial Solution Generation
Northwest corner method [5]: It starts from the northwest corner cell of the transportation table and allocates transportation quantities sequentially according to the constraints of source supplies and destination demands to determine the production-sales relationships. For example, firstly, the transportation quantity in the northwest corner cell is set as the smaller value between the supply of the row and the demand of the column where the cell is located. Then, adjust the remaining supply of the row or the remaining demand of the column accordingly, and continue the above operation in the new northwest corner cell (i.e., the adjacent cell to the right or below the current cell) until all supply and demand quantities are fully allocated.
Minimum cost method [6]: Its core idea is to prioritize allocating transportation quantities starting from the cell with the smallest unit transportation cost in the transportation table (i.e., “nearest supply” in cost terms). When selecting cells, the path with the lowest unit transportation cost is chosen first. The transportation quantity in that cell is set as the smaller value between the supply of its row and the demand of its column. Subsequently, the remaining supply and demand are adjusted accordingly, and the process continues by continuously selecting the cell with the smallest transportation cost for allocation until the entire transportation plan is completed.
Vogel’s approximation method [7]: It determines production-sales relationships by calculating the penalty (the difference between the smallest and second-smallest elements) for each row and column in the transportation table. A larger penalty indicates that if the smallest element in that row or column is not chosen for allocation, the resulting increase in transportation cost is likely to be greater. The method prioritizes allocating transportation quantities to the cell with the smallest transportation cost in the row or column with the largest penalty, following allocation rules similar to those described above. This process is repeated until the initial transportation plan is obtained.
3.1.2. Optimality Test and Adjustment
Closed loop method [8]: By constructing a closed loop (circuit), calculate the test numbers (improvement potential) for each non-basic variable (empty cell) in the transportation table. If all the test numbers are greater than or equal to 0, then current solution is optimal; otherwise, adjustments to current solution are necessary.
Potential method [9]: By introducing row potentials (
) and column potentials (
), the test numbers are calculated as
to determine whether the optimal solution has been achieved. Calculating the test numbers by the potential method is essentially a tabular implementation of the approach to dual problem.
Tabular method is only applicable to the transportation problem with balanced production and sale. The transportation problem with unbalanced production and sale can be solved by transforming it into a balanced one and using tabular method.
3.2. Dual simplex Method [10]
Based on the duality theory of linear programming, dual simplex method (DSM) is to find the optimal solution by maintaining dual feasibility (non-negative reduced costs) and gradually eliminating primal infeasibility (negative right-hand side constants). Complementary to the primal simplex method [11], DSM is applicable to scenarios where the initial solution is dual feasible but primally infeasible. DSM’s core ideas and principles are as follows:
3.2.1. Dual Feasibility
The initial solution satisfies dual feasibility: all reduced costs (the coefficients of non-basic variables in the objective function row) are non-negative.
The primal problem may be infeasible: there exist basic variables taking negative values (i.e., the right-hand side constants are negative).
3.2.2. Iterative Process
The solution structure is gradually adjusted by selecting the leaving basic variable (the most negative basic variable) and the entering basic variable (while maintaining dual feasibility). In each iteration, one infeasibility of the primal problem is eliminated. Eventually, the primal problem becomes feasible, which means the optimal solution is reached.
As a classic tool for linear programming, the core value of the dual simplex method lies in its flexibility in handling changes in constraints. However, in large-scale, dynamic, and multi-objective scenarios, it is necessary to break through the bottleneck through algorithm integration, hardware acceleration, and model expansion. The direction of improvement needs to be closely integrated with practical demands (such as green logistics and real-time scheduling), using technology to empower and resolve the contradiction between efficiency and complexity.
4. Application Areas of the Transportation Problem
4.1. Logistics Distribution
In the logistics industry, solving transportation problems directly impacts distribution efficiency and costs. Logistics companies need to develop optimal transportation plans based on the sources (origins) of goods, destinations (sale locations), supply and demand quantities, and transportation costs to achieve efficient goods delivery and minimize costs. Below are the specific application cases.
Case of multi-warehouse collaborative distribution [12]: An e-commerce company used a transportation problem model to optimize the goods allocation from 3 warehouses to 20 distribution centers in the Beijing-Tianjin-Hebei region, thereby reducing transportation costs by 15%.
Case of instant delivery under dynamic demand [13]: An instant delivery platform shortened the average delivery time to 28 minutes and increased the on-time delivery rate to 95% through a dynamic transportation model.
4.2. Production and Manufacturing
Within production enterprises, raw material procurement and product distribution also involve transportation problems. Enterprises need to purchase raw materials from multiple suppliers (sources) and supply them to different production workshops (destinations), while transporting finished products to various sale points (destinations). By optimizing transportation plans, enterprises can reduce raw material inventory backlogs, lower production costs, and improve production efficiency and product delivery speed. The optimization of internal transportation within manufacturing enterprises should adhere to the “three synergy” principles:
1) Production-transportation synergy [14]: Utilize mixed-integer programming (MIP) models to dynamically adjust production layouts and transportation routes;
2) Inventory-transportation synergy: Integrate economic order quantity (EOQ) with transportation cost functions to balance procurement batch sizes and inventory holding costs;
3) Supplier-enterprise synergy: Implement vendor managed inventory (VMI) and data sharing mechanisms to achieve precise alignment of raw material supply with production demand.
Below are the specific application cases:
Cases of multi-factory collaborative production and material allocation [15]: An automotive group coordinated material allocation between 3 component factories and 2 assembly plants through a transportation model, reducing inter-factory transportation costs by 18%.
Cases of raw material procurement and supplier selection [16]: A steel enterprise optimized its iron ore procurement strategy by a transportation problem model, reducing comprehensive costs by 12% and increasing the supplier on-time delivery rate to 90%.
4.3. Supply Chain Management
In the global supply chain system [17], transportation issues pervade all stages, including raw material supply, production and manufacturing, and product sale. Enterprises need to coordinate transportation activities among suppliers, production bases, distribution centers, and sale terminals in different countries and regions, optimize transportation routes and modes, reduce supply chain costs, and enhance the overall competitiveness of the supply chain [18]. Below are the specific application cases:
Cases of supplier selection and raw material procurement: A food enterprise selected 5 suppliers by a transportation model, reducing comprehensive costs by 18% and increasing the on-time delivery rate to 95%.
Cases of warehouse network optimization and inventory allocation [19]: A retail enterprise optimized its national warehouse layout, reducing the number of warehouses from 12 to 8 and decreasing logistics costs by 20%.
4.4. Transportation System Planning
Transportation planning (including urban and regional systems) must address the allocation of both passenger and freight flow. In urban public transit systems [20], this involves rational arrangement of bus routes and vehicle scheduling to meet travel demands of residents across diverse zones [21], while enhancing operational efficiency, reducing energy consumption, and alleviating traffic congestion. In regional transportation planning, it requires strategic design of highway and railway networks to achieve efficient flow of personnel and goods between cities. Below are the specific application cases:
Cases of regional multimodal corridor planning: By integrating various modes of transportation and constructing an efficient transportation network, the Yangtze River Delta region is gradually forming a modern comprehensive transportation system, providing valuable experience for the in-depth promotion of the regional multimodal transportation corridor planning.
Cases of emergency logistics coordination [22]: The strategies and infrastructure of COVID-19 vaccine distribution networks, such as cold chain logistics arrangements and delivery route optimization, offer practical models and insights for enhancing emergency logistics coordination in handling large-scale, time-sensitive distribution tasks in emergency scenarios.
5. Research Hotspots and Development Trends of Transportation Problems
The study of transportation problems is one of the core topics in the fields such as operations research, logistics management, and transportation engineering. In recent years, with technological advancements and changes in social needs, its research hotspots and development trends have exhibited prominent characteristics of multidisciplinary integration and technology-driven development. Here is a summary of the main research directions and trends:
5.1. Multi-Objective Optimization
Traditional transportation problems primarily focus on minimizing transportation costs, but in practical applications, multiple objectives often need to be considered simultaneously, such as minimizing transportation time, maximizing transportation reliability, and reducing carbon emissions. Therefore, research on multi-objective transportation problems [23] has become a hotspot. Scholars develop multi-objective optimization models and use methods such as weighting approaches, ε-constraint methods, and multi-objective evolutionary algorithms [24] to solve them, so as to obtain Pareto optimal solutions that meet different requirements.
5.2. Uncertain Transportation Problems
In real-world transportation processes, there are many uncertain factors, such as uncertainty in transportation time, fluctuations in transportation costs, and changes in demand. To address these uncertainties, studies on fuzzy transportation problems [25], stochastic transportation problems, and other related areas have emerged. By introducing methods such as fuzzy set theory and probability theory, researchers model and analyze these uncertain factors to develop more robust transportation strategies.
5.3. Integration With Intelligent Technologies
With the rapid development of intelligent technologies such as artificial intelligence, big data, and the Internet of Things (IoT), applying these technologies to the study of transportation problems has become a trend. For example, historical transportation data is analyzed using big data to predict transportation demand and costs; IoT technology is used for real-time monitoring of the location and status of transport vehicles to achieve dynamic optimization of the transportation process; and artificial intelligence algorithms (such as neural networks [26] and genetic algorithms) are employed to solve complex transportation problems, improving solution efficiency and quality.
5.4. Green Transportation [27]
Against the backdrop of growing environmental awareness, green transportation has come to the forefront of attention. Research on how to reduce energy consumption and environmental pollution in the transportation process, such as optimizing transportation routes to minimize vehicle mileage, internalizing carbon emission costs and promoting new energy transport vehicles, has become an important direction in the study of transportation issues.
6. Conclusions
The transportation problem, as a classical subject in operations research and control theory, has developed a comprehensive research system across three dimensions model construction, algorithm design, and engineering applications through over half a century of theoretical exploration and practical verification. From establishing fundamental theoretical frameworks to innovating diversified solving algorithms, and from single cost optimization to complex system decision making, its research achievements have not only propelled the development of mathematical tools such as linear programming and combinatorial optimization but have also profoundly penetrated critical national economic domains including global supply chain management and smart city construction.
With times evolution and technological advancements, the transportation problem is facing new challenges and opportunities. Multi-objective optimization, uncertainty handling, intelligent technology integration, and green transportation are emerging as a key research directions in the future. Further in-depth research on transportation problems holds significant theoretical importance and practical value for enhancing resource allocation efficiency and promoting economic sustainable development.
Current research is transitioning from traditional operations research to an integrated paradigm combining artificial intelligence, operations research optimization, and digital technologies. Future breakthroughs will rely on interdisciplinary technology integration and deep convergence with vertical application scenarios. Academia should focus on addressing genuine industrial challenges such as ultra large scale problem solving and data fragmentation, while enterprises need to establish rapid trial error iteration mechanisms to translate cutting-edge algorithms into production forces.