Minimum Cost of Capacity Expansion for Time-Limited Transportation Problem On-Demand

Hui Ding^*, Zhimin Zou

School of Mathematics and Statistics, Sichuan University of Science and Engineering, Zigong, China.

DOI: 10.4236/jcc.2022.107004                

Abstract

The minimum cost of capacity expansion for time-limited transportation problem on-demand (MCCETLTPD) is to find such a practicable capacity expansion transportation scheme satisfying the time-limited T along with all origins’ supply and all destinations’ demands as well as the expanding cost is minimum. Actually, MCCETLTPD is a balance transportation problem and a variant problem of minimum cost maximum flow problem. In this paper, by creating a mathematical model and constructing a network with lower and upper arc capacities, MCCETLTPD is transformed into searching feasible flow in the constructed network, and consequently, an algorithm MCCETLTPD-A is developed as MCCETLTPD’s solution method basing minimum cost maximum flow algorithm. Computational study validates that the MCCETLTPD-A algorithm is an efficient approach to solving the MCCETLTPD.

Keywords

Capacity Expansion, Minimum Cost Maximum Flow, Transportation Problem, Network with Lower and Upper Arc Capacities

1. Introduction

The minimum cost of capacity expansion for time-limited transportation problem on-demand (MCCETLTPD) is an important optimization problem and prevalent in practice. For example, during the Shopping Festival (such as the “double 11” Festival), many people will take advantage of discounts and promotions to buy a large number of products online, and the products’ quantity is several times as much as usual. Logistics companies now promise to deliver express delivery to the destinations within 1 - 3 days to ensure customers’ online shopping experience. Hence, it is necessary to transport the suddenly increased products within the time-limit. At this time, it is much needed to expand the transportation capacity and even the storage space of the origins and destinations to meet the current demand. Furthermore, fresh milk and newly salvaged seafood, etc., need to be sent to the processing plant for processing within the time-limited to ensure the best quality so as to ensure its fresh taste. Therefore, within the time-limited, it is generally necessary to expand the transportation capacity to meet the transportation demand. Consequently, the MCCETLTPD we studied is very necessary, and the goal of MCCETLTPD is to find a plan that achieves the transportation scheme within a given time-limited and minimizes the expansion cost. Due to the practical application, many scholars have studied the capacity expansion problem as well as its various variants and obtained some valuable results. Following is a brief review of the researches on the capacity expansion problem.

Many works on the capacity expansion problem have been done from different perspectives by many scholars, and many significant results have been obtained. For example, Price studied the network capacity expansion problem where the expansion cost and expansion capacity are nonlinear functions [1] . Wang Hongguo and Ma Shaohan [2] studied the problem of undirected network capacity expansion and proposed how to minimize the cost when the capacity reached a certain fixed demand value R. Later, They [3] also studied the directed networks. Then, Wang Li ping et al. [4] established a general model of network capacity expansion problem with both time and cost constraints, and Wang Shuzhen et al. also studied it [5] . In addition, Liu Geng proposed three expansion modes [6] : point expansion, arc expansion, and the combination of point expansion and arc expansion. After, He [7] studied the capacity expansion problem of minimum cost and maximum flow. Liu Hui et al. [8] added the limit of the number of expansion edges on the basis of Wang Hongguo et al. [2] and then studied a kind of network bottleneck capacity expansion problem with restrictions. Liu Geng [9] also studied the capacity expansion problem of the maximum capacity path and three expansion methods were also adopted for modeling calculation respectively. The definition of capacity in the network has many forms; for instance, Kou fei et al. took the shortest path between two vertexes of the network as the flow path between them and then defined the capacity of every arc in the network as at least the total demands of the entire flow paths which include this arc [10] . Therefore, the capacity of the unsatisfied arcs is needed to expand. Many other scholars have conducted research on capacity expansion based on real-life examples. Such as, Zhang Yuanliang studied capacity expansion with the urban road network as the background [11] . Shin-yi Wu studied the problem of broadband network design and capacity expansion [12] . Margarida et al. studied the capacity expansion with the background of local telephone network [13] . Lynnette Dray [14] made a specific analysis of the flight information of specific airlines and obtained a theoretical analysis on whether the airport should expand capacity.

In addition to these above, there are many scholars have also studied capacity expansion in the transportation problem. Such as, in 2006, Pınar Yılmaz and Bṻlent Ḉatay [15] studied the problem of capacity planning for a three-stage production and transportation system, including single-product, multi-producer, shipper, distributor, etc., in which the capacity of each segment could be expanded. Guessous Y et al. [16] proposed a problem of time allocation under different traffic conditions in 2014. There are also some other research directions about capacity expansion. In 2020, Barahimi et al. proposed a two-level multi-objective urban transportation network design model, which aimed to improve the reliability of travel time by expanding the capacity of existing network links at a minimal cost [17] . The same year, Taghavi Majid and Huang Kai [18] considered the capacity expansion of network models affected by uncertainty and budget constraints.

Less attention has been paid to developing capacity expansion for time-limited transportation problem. In fact, much-existing research on capacity expansion can be summarized as follows: on the one hand, when the cost budget is limited, how to arrange the expansion to maximize the route capacity [2] [3] [4] [6] ? On the other hand, how to minimize the expansion cost when route capacity must reach the given value R [2] [3] [5] ? However, for both the above cases, the capacity of any route for transportation problem is expanded to a same fixed value. Hence, the capacity of some routes is expanded but does not play a role, which not only makes the expansion meaningless but also increases the cost burden. Moreover, they did not consider the time-limited. Therefore, this paper studies capacity expansion for specified routes of transportation problem under the time-limited. In other words, within the time-limited, we find a suitable product transportation scheme through the minimum cost maximum flow algorithm, and as per the transportation scheme and the actual route shipping capacity finiteness, we know which routes need capacity expansion and the amount of expansion, if other routes’ capacity can meet the transportation scheme, we do not need to expand their capacity to meet the requirement.

Obviously, when Shopping Festivals and other situations occur, we need to ship all goods to destinations within time-limited T, so we need to expand the transportation capacity and the storage capacity of the origins and destinations to meet the current demand. Since this situation is temporary, so we must seriously consider the economic pressure brought by the expansion cost. Therefore, it is necessary to expand at the minimum cost. So we expand the capacity according to the actual demand, and it not only saves a large part of the expansion cost but also minimizes the transportation cost.

The main contribution of this paper is as follows. The MCCETLTPD is a balance of origin supply and destination demand transportation problem [19] , and actually also is a minimum cost maximum flow problem. By creating a mathematical model and constructing a network with lower and upper arc capacities, MCCETLTPD is transformed into a collection of seeking the feasible flow in the constructed network. Based on the MCMF-A in [20] for searching minimum cost maximum flow in the constructed network, an algorithm called MCCETLTPD-A is proposed for solving MCCETLTPD. According to the MCCETLTPD-A, a practicable transportation scheme is found. As per the transportation scheme and the route actual shipping capacity finiteness, the final needed capacity expansion routes and capacity expansion quantity are obtained with minimum expanding cost. It is proven that our algorithm MCCETLTPD-A is able to seek out MCCETLTPD’s optimal solution.

The rest parts of this paper are shown below. In Section 2, the mathematical formulation and solving method of the MCCETLTPD are presented. Section 3 demonstrates the applications of MCCETLTPD-A with examples and validates our algorithm is efficient solving method for MCCETLTPD. The last section shows the conclusions.

2. Mathematical Formulation and Solving Approach for MCCETLTPD

2.1. Usable Notations

To preferably comprehend the solving approach to MCCETLTPD, the following usable notations are introduced.

Notation

2.2. Mathematical Model and Solving Analysis

MCCETLTPD is depicted below. Under the normal case, homogeneous products are to be supplied from m origins including origin $i\in I=\left\{1,2,\cdots ,m\right\}$ to $\tilde{n}$ destinations including destination $j\in J=\left\{1,2,\cdots ,\tilde{n}\right\}$ . The shipping capacity for the route from origin $i\in I$ (with available supply as $s_i^o$ ) to destination $j\in J$ (with demand as $d_j^o$ ) is $u_{ij}$ . In a specified limited time T, a large number of sudden increased goods are needed to be supplied from m origins to $\tilde{n}$ destinations. Within the time-limited T, the shipping capacity and time for the route from origin $i\in I$ (with sudden increase supply as $s_i$ ) to destination $j\in J$ (with sudden increase demand as $d_j$ ) are ${u^{\prime }}_{ij}$ and $t_{ij}$ respectively. Moreover, the expansion cost per unit of the route from origin $i\in I$ to destination $j\in J$ is $b_{ij}^e$ and for the origin $i\in I$ and the destination $j\in J$ are $b_i^o$ and $b_j^d$ respectively. For each $\left(i,j\right)\in I\times J$ , $t_{ij}>0$ , $u_{ij}>0$ , ${u^{\prime }}_{ij}>0$ , $b_{ij}^e>0$ , $b_i^o>0$ and $b_j^d>0$ . for each $i\in I$ , $s_i^o>0$ , $s_i>0$ ; and for each $j\in J$ , $d_j^o>0$ , $d_j>0$ . Under the aforementioned circumstances, when a large number of sudden increased goods are needed to be transported within time-limited T, the goal is to seek a practicable capacity expanding transportation scheme satisfying the time-limit T as well as all origins’ supply and all destinations’ demands, so that the expanding cost is minimized.

Let $x_{ij}$ be the products quantity transported from origin $i\in I$ to destination $j\in J$ . Denote the expanding cost by z.Then, MCCETLTPD ’s mathematical model is presented below.

$\text{MCCETLTPD}:\{\begin{array}{l}\min z={\displaystyle \underset{\left(i,j\right)\in I\times J}{\sum }\left(b_{ij}^e\left(x_{ij}-u_{ij}\right)+b_i^o\left({\displaystyle \underset{j\in J}{\sum }{x}_{ij}}-s_i^o\right)+b_j^d\left({\displaystyle \underset{i\in I}{\sum }{x}_{ij}}-d_j^o\right)\right)}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \underset{j\in J}{\sum }{x}_{ij}=s_i\forall i\in I}\\ {\displaystyle \underset{i\in I}{\sum }{x}_{ij}=d_j\forall j\in J}\\ 0\le x_{ij}\le {u^{\prime }}_{ij}\forall i\in I\text{and}\forall j\in J\end{array}\end{array}$

Due to the high time requirement of transportation in reality, then it is considered that minimize the expanding cost under a certain time-limited T. Because of the advanced science and technology, origins and destinations of the logistics industry usually adopt electronic equipment instead of manual operation [21] , so both the origins and destinations are processed at the same time. Thus the actual transportation time is the maximum shipping time among all routes, that is $\text{max}\left\{t_{ij}|\forall i\in I,j\in J\right\}$ where $t_{ij}$ is the shipping time from origin $i\in I$ to destination $j\in J$ . In fact, for any route from origin $i\in I$ to destination $j\in J$ , the shipping time $t_{ij}$ consists of two parts, i.e., a constant part $t_{ij}^1$ , and another part $t_{ij}^2$ that is a linear function of the products quantity $x_{ij}$ transported from origin $i\in I$ to destination $j\in J$ , denoted as $t_{ij}^2=g\left(x_{ij}\right)$ . Therefore, the shipping time $t_{ij}$ $\left(i,j\right)\in I\times J$ satisfies the inequality that $t_{ij}\le T$ for any $\left(i,j\right)\in I\times J$ , where $t_{ij}=\{\begin{array}{l}{t}_{ij}^1+t_{ij}^2,x_{ij}>0\\ 0,x_{ij}=0\end{array}$ .

For the second part $t_{ij}^2$ , it is clear that the more a vehicle loads, the slower it moves. In addition, the exact value of time $t_{ij}^1$ for any route $\left(i,j\right)\in I\times J$ can be calculated, if let $v_i^s$ and $v_j^d$ denote as the operating speed of origin $i\in I$ and destination $j\in J$ , respectively, $v_{ij}^e$ denotes as the empty vehicle running speed, and $d{t}_{ij}$ denotes as the distance of the route from origin $i\in I$ to destination $j\in J$ . Then there are the relationships as follows:

$t_{ij}^1=\frac{s_i}{v_i^s}+\frac{d_j}{v_j^d}+\frac{d{t}_{ij}}{v_{ij}^e},\forall i\in I\text{and}j\in J$ (1)

$t_{ij}^2=\max \left\{0,T-t_{ij}^1\right\},\forall i\in I\text{and}j\in J$ (2)

$g\left(x_{ij}^e\right)\le t_{ij}^2,\forall i\in I\text{and}j\in J$ (3)

Thus, from inequality (3), we can get the maximum transportation quantity $x_{ij}^e$ for the route from origin $i\in I$ to destination $j\in J$ within the time-limited T.

To efficiently solve MCCETLTPD model, we give following definition.

Definition 1. As shown in Figure 1, a network with lower and upper arc capacities $G=\left(V,s,t;A;\underset{\_}{C},\bar{C};B\right)$ is constructed for MCCETLTPD model. Node set $V=\left\{1,2,\cdots ,m,m+1,\cdots ,m+2,\cdots ,m+\tilde{n}+1,m+\tilde{n}+2\right\}$ . Source $s=m+\tilde{n}+1$ . Sink $t=m+\tilde{n}+2$ . Arc set $A=\left\{\left(i,m+k\right)|i\in I,j\in J\right\}\cup \left\{\left(s,k\right)|k\in I\right\}\cup \left\{\left(m+k,t\right)|k\in J\right\}$ . The lower and upper capacity of arc $\left(s,k\right)$ ( $k\in I$ ) in set A are $s_k$ . The lower and upper capacity of arc $\left(m+k,t\right)$ ( $k\in J$ ) in set A are $d_k$ . The lower and upper capacity of arc $\left(i,m+k\right)$ ( $i\in I$ , $k\in J$ ) in set A are zero and $u_{ik}$ , respectively. The number of nodes in G is $n=m+\tilde{n}+2$ . As per Definition 1 in [22] , lower and upper arc capacity matrices $\underset{\_}{C}={\left({\underset{\_}{C}}_{ij}\right)}_{n\times n}$ and $\bar{C}={\left({\bar{C}}_{ij}\right)}_{n\times n}$ are determined by following stipulations. If $i=s$ and $j=k$ ( $k\in I$ ), then both ${\underset{\_}{C}}_{ij}$ and ${\bar{C}}_{ij}$ are set as $s_k$ . If $i=m+k$ ( $k\in J$ ) and $j=t$ , then both ${\underset{\_}{C}}_{ij}$ and ${\bar{C}}_{ij}$ are set as $d_k$ . If $i\in I$ and $j=m+k$ ( $k\in J$ ), then ${\underset{\_}{C}}_{ij}$ and ${\bar{C}}_{ij}$ are set as zero and $u_{ik}$ , respectively. For other situation, if $i=j$ , then ${\underset{\_}{C}}_{ij}$ and ${\bar{C}}_{ij}$ are set as zero and positive infinity ( $+\infty$ ) respectively, else both ${\underset{\_}{C}}_{ij}$ and ${\bar{C}}_{ij}$ are set as zero. And the expansion cost per unit matrix $B={\left(B_{ij}\right)}_{n\times n}$ is determined by following stipulations. If $i=s$ and $j=k$ ( $k\in I$ ), then $B_{ij}$ is set as $b_k^o$ . If $i=m+k$ ( $k\in J$ ) and $j=t$ , then $B_{ij}$ is set as $b_k^d$ . If $i\in I$ and $j=m+k$ ( $k\in J$ ), then $B_{ij}$ is set as $b_{ik}^e$ . For other situation, if $i=j$ , then $B_{ij}$ is set as zero.

Obviously, in the constructed network G by Definition 1, if there is a feasible flow from source s to sink t, then for each $\left(i,k\right)\in I\times J$ , let $x_{ik}$ be the flow on arc $\left(i,m+k\right)$ , hence we derive MCCETLTPD model’s a feasible solution as $x=\left\{x_{ij}|\left(i,j\right)\in I\times J\right\}$ . So we get following Proposition 1.

Figure 1. Network with lower and upper arc capacities, G.

Proposition 1. The constructed network G by Definition 1 reflects the structure of the MCCETLTPD model’s feasible solutions. That is to say, there exists one-to-one correspondence between the feasible solution of the MCCETLTPD model and the feasible flow in the constructed network G by Definition 1, i.e., a feasible flow in the constructed network G by Definition 1 corresponds to a feasible solution of the MCCETLTPD model, and vice versa. Furthermore, whether there exists a feasible flow in the constructed network G by Definition 1 equals whether there exists a feasible solution of the MCCETLTPD model.

For the route $\left(i,k\right)$ from origin $i\in I$ to destination $k\in J$ in network G, if feasible flow $f_{ij}$ ( $j=m+k$ ) on arc $\left(i,m+k\right)$ ( $\forall i\in I$ , $k\in J$ ) is no more than $u_{ij}$ , it means that arc $\left(i,m+k\right)$ of the network G is allowed to transport flow $f_{ij}$ ( $j=m+k$ ); otherwise arc $\left(i,m+k\right)$ of G needs to be expended.

2.3. Solving Method of MCCETLTPD

The MCCETLTPD is actually equivalent to the minimum cost maximum flow problem of G constructed by Definition 1, so we can get Theorem 1 as follows.

Theorem 1. The algorithm called MCCETLTPD-A judges the existence of the MCCETLTPD model’s feasible solution and finds the MCCETLTPD model’s optimum solution if existing.

MCCETLTPD-A:

Step 1: For any route $\left(i,j\right)\in I\times J$ , input all the known parameters under normal conditions, such as $\left(s_i^o,d_j^o,u_{ij}\right)$ . Then construct network $G=\left(V,s,t;A;\underset{\_}{C},\bar{C}\right)$ by Definition 1. For each $i,j\in \left\{1,2,\cdots ,n\right\}$ , set $C_{ij}={\bar{C}}_{ij}$ to keep matrix $\bar{C}$ in $C=\left(C_{ij}\right)$ .

Step 2: For any route $\left(i,j\right)\in I\times J$ , input all the known parameters about capacity expansion, such as $\left(s_i,d_j,T,b_i^o,b_j^d,b_{ij}^e,d{t}_{ij},v_i^s,v_j^d,v_{ij}^e\right)$ , then find the time value of $t_{ij}^1$ and $t_{ij}^2$ by formulas (1) and (2) respectively, and then find the maximum transportation quantity $x_{ij}^e$ by inequality (3) under the time-limited T, and let ${u^{\prime }}_{ij}=x_{ij}^e$ . For each $\left(i,j\right)\in I\times J$ , set $u_{ij}={u^{\prime }}_{ij}$ to keep variable ${u^{\prime }}_{ij}$ as $u_{ij}$ , then construct new network $G=\left(V,s,t;A;\underset{\_}{C},\bar{C};B\right)$ by Definition 1. Set $Y=0$ .

Step 3: Call minimum cost maximum flow algorithm MCMF-A in [19] for currently gotten new network $G=\left(V,s,t;A;\underset{\_}{C},\bar{C};B\right)$ . If MCMF-A in [19] finds a feasible flow’s flow matrix as $F={\left(f_{ij}\right)}_{n\times n}$ for currently gotten new network G, then consecutively operate as below: “If the flow amount ${\displaystyle \underset{\left(s,i\right)\in A}{\sum }{f}_{si}}-{\displaystyle \underset{\left(i,s\right)\in A}{\sum }{f}_{is}}$ is equal to the total expanding goods amounts ${\displaystyle \underset{i\in I}{\sum }{s}_i}$ (or equal to ${\displaystyle \underset{j\in J}{\sum }{d}_j}$ ) then the transportation scheme with time-limited T is satisfied, set $Y=1$ and go Step 4”; otherwise, it means that the transportation task cannot be completed within time-limited T, then stop;

Step 4: By the flow matrix $F={\left(f_{ij}\right)}_{n\times n}$ , the capacity expansion matrix $R={\left(r_{ij}\right)}_{n\times n}$ is obtained as follows: For any $i,j\in \left\{1,2,\cdots ,n\right\}$ , if $f_{ij}>C_{ij}$ , let $r_{ij}=f_{ij}-C_{ij}$ ; else let $r_{ij}=0$ . Here in, for any $i,j\in \left\{1,2,\cdots ,n\right\}$ , if $r_{ij}>0$ , then the capacity for the route $\left(i,j\right)$ needs to be expend. So, if $R={\left(r_{ij}\right)}_{n\times n}$ is not a zero matrix, according to capacity expansion matrix $R={\left(r_{ij}\right)}_{n\times n}$ and the expansion cost per unit matrix $B={\left(B_{ij}\right)}_{n\times n}$ , the minimum expansion cost $z^{\prime }={\displaystyle \underset{i,j\in V}{\sum }{B}_{ij}{r}_{ij}}$ is obtained. then go to Step 5;

Step 5: If $Y=1$ , then set $x_{ij}=f_{ij}$ for each $\left(i,j\right)\in I\times J$ , set $z=z^{\prime }$ , output MCCETLTPD model’s optimum solution $x=\left\{x_{ij}|\left(i,j\right)\in I\times J\right\}$ and optimum objective value z, and output $Y=1$ to indicate that MCCETLTPD model’s optimum solution and optimum objective value are found. Otherwise, output $Y=0$ to indicate that feasible solution is not existent for MCCETLTPD model.

To preferably comprehend the solving algorithm MCCETLTPD-A, an algorithm flow chart of MCCETLTPD-A is shown in Figure 2. The algorithm flow chart clearly shows the idea of algorithm MCCETLTPD-A.

3. Illustrative Examples

This section illustrates the applications and advantages of MCCETLTPD-A with

Figure 2. The algorithm flow chart of MCCETLTPD-A algorithm.

examples. The MCCETLTPD-A is coded with MATLAB, and run on PC with Intel(R) Pentium(R) CPU 3825U @ 1.90 GHz and RAM 4.00 GB, on which we perform all presented computational experiments.

3.1. A small Scale Instance

Consider an MCCETLTPD instance of 3 origins and 4 destinations, i.e., 3 × 4 problem [21] , which was first discussed by LI Zhen-ping et al., but we make improvements to illustrate the effectiveness of our algorithm MCCETLTPD-A. In the paper of [21] , within time-limited $T=15h$ , the transportation scheme was not completed under the normal case. However, we can not only complete the transportation scheme within time-limited $T=15h$ by expanding the route capacity, but also the number of products increases suddenly.

Firstly, we give the data ( $s_i^o$ , $d_j^o$ , $u_{ij}$ ) shown in Table 1 under the normal case. Then we give the goods sudden increase data ( $s_i$ , $d_j$ , $d{t}_{ij}$ ), ( $b_i^o$ , $b_j^d$ , $b_{ij}^e$ ), and ( $v_i^s$ , $v_j^d$ , $v_{ij}^e$ ) shown in Table 2, Table 3 and Table 4, respectively, i.e., the goods sudden increase and need to capacity expand within time-limited T. By running MCCETLTPD-A based MATLAB computational programs, we apply MCCETLTPD-A to solve 3 × 4 problem, and validate the efficiency for MCCETLTPD-A to solve MCCETLTPD.

Solution: As per Table 1, the known parameters are below. Origins’ number m = 3. Destinations’ number $\tilde{n}=4$ . Under the normal case, the origin supply vector $S^o=\left(s_1^o,s_2^o,s_3^o\right)$ , destination demand vector $D^o=\left(d_1^o,d_2^o,d_3^o,d_4^o\right)$ and the route shipping capacity matrices $U=\left(u_{ij}\right)$ are below.

Table 1. The route shipping normal capacity ( $u_{ij}$ ), normal supply ( $s_i^o$ ), and normal demand ( $d_j^o$ ) for 3 × 4 problem.

Table 2. The route shipping distance ( $d{t}_{ij}$ ), expanding supply ( $s_i$ ), and expanding demand ( $d_j$ ) for 3 × 4 problem.

$S^o=\left(7,4,9\right)$ ; $D^o=\left(3,6,5,6\right)$ ; $U=\left[\begin{array}{cccc}9& 5& 8& 8\\ \text{10}& \text{5}& \text{3}& \text{8}\\ \text{2}& \text{5}& \text{11}& \text{5}\end{array}\right]$

As per Table 2, Table 3 and Table 4, the origin expanding supply vector $S=\left(s_1,s_2,s_3\right)$ , destination expanding demand vector $D=\left(d_1,d_2,d_3,d_4\right)$ , the route shipping distance matrices $Dt=\left(d{t}_{ij}\right)$ , origin capacity expansion cost per unit vector $Bs=\left(b_1^o,b_2^o,b_3^o\right)$ , destination capacity expansion cost per unit vector $Bd=\left(b_1^d,b_2^d,b_3^d,b_4^d\right)$ , the route capacity expansion cost per unit matrices $Be=\left(b_{ij}^e\right)$ , the origin operating speed vector $Vs=\left(v_1^s,v_2^s,v_3^s\right)$ , the destination operating speed vector $Vd=\left(v_1^d,v_2^d,v_3^d,v_4^d\right)$ , and the route empty vehicle running speed matrices $Ve=\left(v_{ij}^e\right)$ are below. The time-limited $T=15\text{h}$ . The $t_{ij}^1$ and $t_{ij}^2$ (see Table 5) are obtained by Equations (1) and (2), respectively. Next, by inequality (3) of $g\left(x_{ij}^e\right)=\frac{1}{2}{x}_{ij}^e\le t_{ij}^2$ , the route maximum shipping quantity $x_{ij}^e$ under the time-limited T is obtained shown in Table 6.

Table 3. The route capacity expansion cost ( $b_{ij}^e$ ), origin capacity expansion cost ( $b_i^o$ ), and destination capacity expansion cost ( $b_j^d$ ) for 3 × 4 problem.

Table 4. The route empty vehicle running speed ( $v_{ij}^e$ ), origin operating speed ( $v_i^s$ ), and destination operating speed ( $v_j^d$ ) for 3 × 3 problem.

Table 5. The shipping time ( $t_{ij}^1$ ), and shipping time ( $t_{ij}^2$ ) for 3 × 4 problem.

$S=\left(17,14,19\right)$ ; $D=\left(13,16,5,16\right)$ ; $Bs=\left(1,2,3\right)$ ;

$Bd=\left(2,1,3,1\right)$ ; $Vs=\left(10,10,10\right)$ ; $Vd=\left(10,10,10,10\right)$

$Dt=\left[\begin{array}{cccc}\text{10}& \text{2}& \text{8}& \text{3}\\ \text{10}& \text{3}& \text{9}& 4\\ 6& 12& 10& 4\end{array}\right]$ ; $Be=\left[\begin{array}{cccc}\text{1}& \text{2}& \text{2}& \text{1}\\ \text{1}& \text{3}& \text{2}& \text{1}\\ \text{1}& 1& 1& 2\end{array}\right]$ ; $Ve=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\end{array}\right]$

By calling MCCETLTPD-A based MATLAB computational programs and using the above known parameters as input, the optimum transportation scheme (i.e., maximum flow $f_{ij}$ ) is obtained, see Table 7, and from Table 1 and Table 7, the route needed capacity expansion quantity $r_{ij}$ is obtained shown in Table 8.

So, the transportation scheme can be completed within time-limited $T=15\text{h}$ . Then, from Table 3 and Table 8, the expanding cost is obtained, that is z = 136.2.

3.2. A Medium Scale Instance

Similarly to the problem of 3 × 4 problem, we apply MCCETLTPD-A to 10 × 10

Table 6. The route maximum shipping quantity $x_{ij}^e$ under the time-limited T for 3 × 4 problem.

Table 7. The optimum transportation scheme for 3 × 4 problem.

Table 8. The route needed capacity expansion quantity ( $r_{ij}$ ), origin needed capacity expansion quantity ( $r_i^s$ ), and destination needed capacity expansion quantity ( $r_j^d$ ) for 3 × 4 problem

problem given in Tables 9-14. For 10 × 10 problem, we consider the normal case (i.e., the products are not sudden increase), but the products need to be transported within the specified time-limited $T=36\text{h}$ . By inequality (3) of $g\left(x_{ij}^e\right)=\frac{1}{2}{x}_{ij}^e\le t_{ij}^2$ , the route maximum shipping quantity $x_{ij}^e$ under the time-limited $T=36\text{h}$ is obtained shown in Table 15.

Table 9. The route shipping normal capacity ( $u_{ij}$ ), normal supply ( $s_i^o$ ), and normal demand ( $d_j^o$ ) for 10 × 10 problem.

Table 10. The route shipping distance ( $d{t}_{ij}$ ), expanding expanding supply ( $s_i$ ), and demand ( $d_j$ ) for 10 × 10 problem.

Table 11. The route capacity expansion cost ( $b_{ij}^e$ ), origin capacity expansion cost ( $b_i^o$ ), and destination capacity expansion cost ( $b_j^d$ ) for 10 × 10 problem

Table 12. The route empty vehicle running speed ( $v_{ij}^e$ ), origin operating speed ( $v_i^s$ ), and destination operating speed ( $v_j^d$ ) for 10 × 10 problem.

Table 13. The shipping time ( $t_{ij}^1$ ) for 10 × 10 problem.

Table 14. The shipping time ( $t_{ij}^2$ ) for 10 × 10 problem.

Table 15. The route maximum shipping quantity $x_{ij}^e$ under the time-limited T for 10 × 10 problem.

Table 16. The optimum transportation scheme for 10 × 10 problem.

Table 17. The route needed capacity expansion quantity ( $r_{ij}$ ), origin needed capacity expansion quantity ( $r_i^s$ ), and destination needed capacity expansion quantity ( $r_j^d$ ) for 10 × 10 problem.

For 10 × 10 problem, by calling MCCETLTPD-A based MATLAB computational programs and using the above known parameters as input, the optimum shipping scheme (i.e., maximum flow $f_{ij}$ ) is obtained, see Table 16, and from Table 9 and Table 16, the needed capacity expansion quantity $r_{ij}$ is obtained shown in Table 17. So, the transportation scheme can be completed within time-limited $T=36\text{h}$ . From Table 11 and Table 17, the expanding cost is obtained, that is $z=44$ .

Although there is no sudden increase in goods, the capacity expansion may be required to complete the transportation scheme within the specified time-limited T, so our method can also solve such problems. Furthermore, if we know the transportation cost per unit, we also can get the total cost of completing the transportation scheme, i.e., the sum of transportation cost and expanding cost.

4. Conclusions

Capacity expansion for time-limited transportation problem on demand is a vital optimization problem worthy of further research in practice due to the pervasiveness of transportation problem as well as the importance of time and the finiteness of resources or capacity. The minimum cost of capacity expansion for time-limited transportation problem on demand is to find a feasible transportation scheme with minimum expanding cost meeting the restrictions for origin supply and destination demand as well as route shipping capacity and time-li- mited.

In this paper, MCCETLTPD was a balance of origin supply and destination demand transportation problem, and actually also was a minimum cost maximum flow problem. By making full use of the problem’s network flow structure characteristic and creating a mathematical model as well as constructing a network with lower and upper arc capacities, MCCETLTPD was transformed into a collection of seeking the feasible flow in the constructed network. Based on the minimum cost maximum flow algorithm for searching minimum cost maximum flow in the constructed network, an algorithm called MCCETLTPD-A was proposed for solving MCCETLTPD. According to the MCCETLTPD-A, a practicable transportation scheme was found. As per the transportation scheme and the route’s actual shipping capacity finiteness, the final needed capacity expansion routes and capacity expansion quantity were obtained with minimum expanding cost, where route capacity was expanded according to actual needs, and any route that needn’t expand can stay unchanged. Accordingly, as a robust and efficient solving approach to MCCETLTPD, our algorithm is a powerful tool for solving other relative optimization problems.

As a prospect, it is an interesting work in the future to consider that there is an unbalanced relationship between the origins supply and destinations demand, and the transportation time and the transportation volume are nonlinear functions. Moreover, it is also an interesting and challenging work in the future to combine our approach with general network problems to solve other related complex optimization problems.

Acknowledgements

This work is supported by Innovation and Entrepreneurship Foundation for College Students of Sichuan University of Science and Engineering under Grant cx2021152. We are in sincere appreciation of all the supports.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Price, W.L. (1967) Increasing the Capacity of a Network Where the Costs Are Non-Linear: A Brach-and-Bound Algorithm. CORS Journal, 5, 100-114.
[2]	Wang, H.-G. and Ma, S.-H. (2000) Capacity Expansion Problem on Undirected Network. Joural of Shangdong University, No. 4, 418-425.
[3]	Wang, H.-G. and Ma, S.-H. (2001) The Capacity Expansion Problem on Directed Network. Journal of Applied Mathematics in Universities A, No. 4, 471-480.
[4]	Wang, L., Wang, S. and Xu, G. (2003) The Network Capacity Expansion Problem with the Time and Cost Constraint. Computer Engineering and Applications, No. 11, 176-178.
[5]	Wang, S., Wang, D., Liu, H. and Xu, G. (2004) Network Capacity Expansion Problem with the Time and Cost Constraint. Computer Engineering, No. 1, 33-35.
[6]	Liu, G. (2007) Study on Capacity Expansion Problems on Directed Networks. Huazhong University of Science and Technology, Wuhan.
[7]	Liu, G. (2009) Research on Capacity Expansion with Minimum-Cost and Maximum Network Flow. Logistics Technology, No. 12, 153-154+161.
[8]	Lui, H., Yang, C. and Yang, J. (2014) A Class of Network Bottleneck Capacity Expansion Problem with Constraints. Chinese Journal of Management Science, 22, 40-48.
[9]	Liu, G. (2020) Research on Expansion of Maximum Capacity Path. Logistics Technology, 39, 94-96.
[10]	Kou, F., Xu, C. and Xu, C.-J. (2009) A Class of Capacity Expansion Problem on Networks. Journal of Qingdao University (Natural Science Edition), 22, 30-33.
[11]	Zhang, Y.-L. (2009) Research on Expanding Capacity of Urban Road Network. Southwest Jiaotong University, Chengdu.
[12]	Wu, S.-Y. (2007) Optimal Infrastructure Design and Expansion of Broadband Wireless Access Networks. European Journal of Operational Research, 178, 322-329. https://doi.org/10.1016/j.ejor.2006.01.024
[13]	Margarida, C.-R. and Luïs, G. (2007) Network Flow Models for the Local Access Network Expansion Problem. Computers Operations Research, 34, 1141-1157. https://doi.org/10.1016/j.cor.2005.07.001
[14]	Lynnette, D. (2020) An Empirical Analysis of Airport Capacity Expansion. Journal of Air Transport Management, 87, Article ID: 101850. https://doi.org/10.1016/j.jairtraman.2020.101850
[15]	Yilmaz, P. and Catay, B. (2006) Strategic Level Three-Stage Production Distribution Planning with Capacity Expansion. Computers & Industrial Engineering, 51, 609-620. https://doi.org/10.1016/j.cie.2006.05.004
[16]	Guessous, Y., Aron, M., Bhouri, N. and Cohen, S. (2014) Estimating Travel Time Distribution under Different Traffic Conditions. Transportation Research Procedia, 3, 339-348. https://doi.org/10.1016/j.trpro.2014.10.014
[17]	Hossein, B.A., Alireza, E. and Abdolah, A. (2020) Bi-Level Multi-Objective Model for Existing Link Capacity Expansion Problem across Urban Transportation Network Considering Travel Time Reliability: Presenting Dynamic Particle Swarm Algorithm. Sādhanā, 45, Article No. 257. https://doi.org/10.1007/s12046-020-01486-z
[18]	Taghavi, M. and Huang, K. (2020) A Lagrangian Relaxation Approach for Stochastic Network Capacity Expansion with Budget Constraints. Annals of Operations Research, 284, 605-621. https://doi.org/10.1007/s10479-018-2862-7
[19]	Ma, Y.-Y., Li, N., Xu, Q.-Y. and Li, Z.-P. (2010) Network Flow Approach to Minimum Cost Transport Problem with Time Constraint. Logistics Technology, 29, 79-81+84.
[20]	Xie, F., Jia, Y. and Jia, R. (2012) Algorithm for Minimum Cost Maximum Flow in Transportation Network. Journal of Convergence Information Technology, 7, 7.
[21]	Li, Z.-P., Xu, Q.-Y., Li, N. and Ma, Y.-Y. (2011) A Method for Solving the Minimum Cost Transportation Problem with Time Limited. Operations Research and Management Science, 20, 9-14
[22]	Xie, F., Butt, M.M., Li, Z. and Zhu, L. (2017) An Upper Bound on the Minimal Total Cost of the Transportation Problem with Varying Demands and Supplies. Omega, 68, 105-118. https://doi.org/10.1016/j.omega.2016.06.007