Minimum Cost of Capacity Expansion for Time-Limited Transportation Problem On-Demand ()
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
to
destinations including destination
. The shipping capacity for the route from origin
(with available supply as
) to destination
(with demand as
) is
. In a specified limited time T, a large number of sudden increased goods are needed to be supplied from m origins to
destinations. Within the time-limited T, the shipping capacity and time for the route from origin
(with sudden increase supply as
) to destination
(with sudden increase demand as
) are
and
respectively. Moreover, the expansion cost per unit of the route from origin
to destination
is
and for the origin
and the destination
are
and
respectively. For each
,
,
,
,
,
and
. for each
,
,
; and for each
,
,
. 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
be the products quantity transported from origin
to destination
. Denote the expanding cost by z.Then, MCCETLTPD ’s mathematical model is presented below.
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
where
is the shipping time from origin
to destination
. In fact, for any route from origin
to destination
, the shipping time
consists of two parts, i.e., a constant part
, and another part
that is a linear function of the products quantity
transported from origin
to destination
, denoted as
. Therefore, the shipping time
satisfies the inequality that
for any
, where
.
For the second part
, it is clear that the more a vehicle loads, the slower it moves. In addition, the exact value of time
for any route
can be calculated, if let
and
denote as the operating speed of origin
and destination
, respectively,
denotes as the empty vehicle running speed, and
denotes as the distance of the route from origin
to destination
. Then there are the relationships as follows:
(1)
(2)
(3)
Thus, from inequality (3), we can get the maximum transportation quantity
for the route from origin
to destination
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
is constructed for MCCETLTPD model. Node set
. Source
. Sink
. Arc set
. The lower and upper capacity of arc
(
) in set A are
. The lower and upper capacity of arc
(
) in set A are
. The lower and upper capacity of arc
(
,
) in set A are zero and
, respectively. The number of nodes in G is
. As per Definition 1 in [22] , lower and upper arc capacity matrices
and
are determined by following stipulations. If
and
(
), then both
and
are set as
. If
(
) and
, then both
and
are set as
. If
and
(
), then
and
are set as zero and
, respectively. For other situation, if
, then
and
are set as zero and positive infinity (
) respectively, else both
and
are set as zero. And the expansion cost per unit matrix
is determined by following stipulations. If
and
(
), then
is set as
. If
(
) and
, then
is set as
. If
and
(
), then
is set as
. For other situation, if
, then
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
, let
be the flow on arc
, hence we derive MCCETLTPD model’s a feasible solution as
. 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
from origin
to destination
in network G, if feasible flow
(
) on arc
(
,
) is no more than
, it means that arc
of the network G is allowed to transport flow
(
); otherwise arc
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
, input all the known parameters under normal conditions, such as
. Then construct network
by Definition 1. For each
, set
to keep matrix
in
.
Step 2: For any route
, input all the known parameters about capacity expansion, such as
, then find the time value of
and
by formulas (1) and (2) respectively, and then find the maximum transportation quantity
by inequality (3) under the time-limited T, and let
. For each
, set
to keep variable
as
, then construct new network
by Definition 1. Set
.
Step 3: Call minimum cost maximum flow algorithm MCMF-A in [19] for currently gotten new network
. If MCMF-A in [19] finds a feasible flow’s flow matrix as
for currently gotten new network G, then consecutively operate as below: “If the flow amount
is equal to the total expanding goods amounts
(or equal to
) then the transportation scheme with time-limited T is satisfied, set
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
, the capacity expansion matrix
is obtained as follows: For any
, if
, let
; else let
. Here in, for any
, if
, then the capacity for the route
needs to be expend. So, if
is not a zero matrix, according to capacity expansion matrix
and the expansion cost per unit matrix
, the minimum expansion cost
is obtained. then go to Step 5;
Step 5: If
, then set
for each
, set
, output MCCETLTPD model’s optimum solution
and optimum objective value z, and output
to indicate that MCCETLTPD model’s optimum solution and optimum objective value are found. Otherwise, output
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
, the transportation scheme was not completed under the normal case. However, we can not only complete the transportation scheme within time-limited
by expanding the route capacity, but also the number of products increases suddenly.
Firstly, we give the data (
,
,
) shown in Table 1 under the normal case. Then we give the goods sudden increase data (
,
,
), (
,
,
), and (
,
,
) 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
. Under the normal case, the origin supply vector
, destination demand vector
and the route shipping capacity matrices
are below.
Table 1. The route shipping normal capacity (
), normal supply (
), and normal demand (
) for 3 × 4 problem.
Table 2. The route shipping distance (
), expanding supply (
), and expanding demand (
) for 3 × 4 problem.
;
;
As per Table 2, Table 3 and Table 4, the origin expanding supply vector
, destination expanding demand vector
, the route shipping distance matrices
, origin capacity expansion cost per unit vector
, destination capacity expansion cost per unit vector
, the route capacity expansion cost per unit matrices
, the origin operating speed vector
, the destination operating speed vector
, and the route empty vehicle running speed matrices
are below. The time-limited
. The
and
(see Table 5) are obtained by Equations (1) and (2), respectively. Next, by inequality (3) of
, the route maximum shipping quantity
under the time-limited T is obtained shown in Table 6.
Table 3. The route capacity expansion cost (
), origin capacity expansion cost (
), and destination capacity expansion cost (
) for 3 × 4 problem.
Table 4. The route empty vehicle running speed (
), origin operating speed (
), and destination operating speed (
) for 3 × 3 problem.
Table 5. The shipping time (
), and shipping time (
) for 3 × 4 problem.
;
;
;
;
;
;
;
By calling MCCETLTPD-A based MATLAB computational programs and using the above known parameters as input, the optimum transportation scheme (i.e., maximum flow
) is obtained, see Table 7, and from Table 1 and Table 7, the route needed capacity expansion quantity
is obtained shown in Table 8.
So, the transportation scheme can be completed within time-limited
. 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
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 (
), origin needed capacity expansion quantity (
), and destination needed capacity expansion quantity (
) 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
. By inequality (3) of
, the route maximum shipping quantity
under the time-limited
is obtained shown in Table 15.
Table 9. The route shipping normal capacity (
), normal supply (
), and normal demand (
) for 10 × 10 problem.
Table 10. The route shipping distance (
), expanding expanding supply (
), and demand (
) for 10 × 10 problem.
Table 11. The route capacity expansion cost (
), origin capacity expansion cost (
), and destination capacity expansion cost (
) for 10 × 10 problem
Table 12. The route empty vehicle running speed (
), origin operating speed (
), and destination operating speed (
) for 10 × 10 problem.
Table 13. The shipping time (
) for 10 × 10 problem.
Table 14. The shipping time (
) for 10 × 10 problem.
Table 15. The route maximum shipping quantity
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 (
), origin needed capacity expansion quantity (
), and destination needed capacity expansion quantity (
) 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
) is obtained, see Table 16, and from Table 9 and Table 16, the needed capacity expansion quantity
is obtained shown in Table 17. So, the transportation scheme can be completed within time-limited
. From Table 11 and Table 17, the expanding cost is obtained, that is
.
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.