Blockage is a kind of phenomenon frequently occurred in a transport network, in which the human beings are the moving subjects. The minimum flow of a network defined in this paper means the maximum flow quantity throu...Blockage is a kind of phenomenon frequently occurred in a transport network, in which the human beings are the moving subjects. The minimum flow of a network defined in this paper means the maximum flow quantity through the network in the seriously blocked situation. It is an important parameter in designing and operating a transport network, especially in an emergency evacuation network. A branch and bound method is presented to solve the minimum flow problem on the basis of the blocking flow theory and the algorithm and its application are illustrated by examples.展开更多
This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building...This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.展开更多
In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second meth...In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second method are given. The methods are applied to approximate the efficient frontier of the stochastic minimum cost flow problem with the moment bicriterion. Two numerical examples including the comparison of the proposed algorithms with two other literature derivative free methods are given.展开更多
Path marginal cost （PMC） is the change in totaltravel cost for flow on the network that arises when timedependentpath flow changes by 1 unit. Because it is hardto obtain the marginal cost on all the links, the local...Path marginal cost （PMC） is the change in totaltravel cost for flow on the network that arises when timedependentpath flow changes by 1 unit. Because it is hardto obtain the marginal cost on all the links, the local PMC,considering marginal cost of partial links, is normallycalculated to approximate the global PMC. When analyzingthe marginal cost at a congested diverge intersection, ajump-point phenomenon may occur. It manifests as alikelihood that a vehicle may unsteadily lift up （down） inthe cumulative flow curve of the downstream links. Previously,the jump-point caused delay was ignored whencalculating the local PMC. This article proposes an analyticalmethod to solve this delay which can contribute toobtaining a more accurate local PMC. Next to that, we usea simple case to calculate the previously local PMC and themodified one. The test shows a large gap between them,which means that this delay should not be omitted in thelocal PMC calculation.展开更多
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 ...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.展开更多
Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different c...Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.展开更多
Two new methods were presented for power flow tracing(PFT).These two methods were compared and the results were discussed in detail.Both methods use the active and reactive power balance equations at each bus in order...Two new methods were presented for power flow tracing(PFT).These two methods were compared and the results were discussed in detail.Both methods use the active and reactive power balance equations at each bus in order to solve the tracing problem.The first method considers the proportional sharing assumption while the second one uses the circuit laws to find the relationship between power inflows and outflows through each line,generator and load connected to each bus of the network.Both methods are able to handle loop flow and loss issues in tracing problem.A formulation is also proposed to find the share of each unit in provision of each load.These methods are applied to find the producer and consumer's shares on the cost of transmission for each line in different case studies.As the results of these studies show,both methods can effectively solve the PFT problem.展开更多
In the multiple protocol label-switched (MPLS) networks, the commodities are transmitted by the label-switched paths (LSPs). For the sake of reducing the total cost and strengthening the central management, the MPLS n...In the multiple protocol label-switched (MPLS) networks, the commodities are transmitted by the label-switched paths (LSPs). For the sake of reducing the total cost and strengthening the central management, the MPLS networks restrict the number of paths that a commodity can use, for maintaining the quality of service (QoS) of the users, the demand of each commodity must be satisfied. Under the above conditions, some links in the network may be too much loaded, affecting the performance of the whole network drastically. For this problem, in [1], we proposed two mathematical models to describe it and a heuristic algorithm which quickly finds transmitting paths for each commodity are also presented. In this paper, we propose a new heuristic algorithm which finds a feasible path set for each commodity, and then select some paths from the path set through a mixed integer linear programming to transmit the demand of each commodity. This strategy reduces the scale of the original problem to a large extent. We test 50 instances and the results show the effectiveness of the new heuristic algorithm.展开更多
To reduce the transmission cost in 5G multicast networks that have separate control and data planes, we focus on the minimum-power-cost network-coding subgraph problem for the coexistence of two multieasts in wireless...To reduce the transmission cost in 5G multicast networks that have separate control and data planes, we focus on the minimum-power-cost network-coding subgraph problem for the coexistence of two multieasts in wireless networks. We propose two suboptimal algorithms as extensions of the Steiner tree multicast. The critical 1-cut path eliminating （C1CPE） algorithm attempts to find the minimum-cost solution for the coexistence of two multicast trees with the same throughput by reusing the links in the topology, and keeps the solution decodable by a coloring process. For the special case in which the two multicast trees share the same source and destinations, we propose the extended selective closest terminal first （E-SCTF） algorithm out of the CICPE algorithm. Theoretically the complexity of the E-SCTF algorithm is lower than that of the C1CPE algorithm. Simulation results show that both algorithms have superior performance in terms of power cost and that the advantage is more evident in networks with ultra-densification.展开更多
Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we c...Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we consider both types of the weighted Hamming distances for measuring the adjustment.In the sum-type case,it is shown that the inverse problem is APX-hard.In the bottleneck-type case,we present a polynomial time algorithm.展开更多
文摘Blockage is a kind of phenomenon frequently occurred in a transport network, in which the human beings are the moving subjects. The minimum flow of a network defined in this paper means the maximum flow quantity through the network in the seriously blocked situation. It is an important parameter in designing and operating a transport network, especially in an emergency evacuation network. A branch and bound method is presented to solve the minimum flow problem on the basis of the blocking flow theory and the algorithm and its application are illustrated by examples.
文摘This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.
文摘In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second method are given. The methods are applied to approximate the efficient frontier of the stochastic minimum cost flow problem with the moment bicriterion. Two numerical examples including the comparison of the proposed algorithms with two other literature derivative free methods are given.
文摘Path marginal cost （PMC） is the change in totaltravel cost for flow on the network that arises when timedependentpath flow changes by 1 unit. Because it is hardto obtain the marginal cost on all the links, the local PMC,considering marginal cost of partial links, is normallycalculated to approximate the global PMC. When analyzingthe marginal cost at a congested diverge intersection, ajump-point phenomenon may occur. It manifests as alikelihood that a vehicle may unsteadily lift up （down） inthe cumulative flow curve of the downstream links. Previously,the jump-point caused delay was ignored whencalculating the local PMC. This article proposes an analyticalmethod to solve this delay which can contribute toobtaining a more accurate local PMC. Next to that, we usea simple case to calculate the previously local PMC and themodified one. The test shows a large gap between them,which means that this delay should not be omitted in thelocal PMC calculation.
文摘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.
文摘Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.
文摘Two new methods were presented for power flow tracing(PFT).These two methods were compared and the results were discussed in detail.Both methods use the active and reactive power balance equations at each bus in order to solve the tracing problem.The first method considers the proportional sharing assumption while the second one uses the circuit laws to find the relationship between power inflows and outflows through each line,generator and load connected to each bus of the network.Both methods are able to handle loop flow and loss issues in tracing problem.A formulation is also proposed to find the share of each unit in provision of each load.These methods are applied to find the producer and consumer's shares on the cost of transmission for each line in different case studies.As the results of these studies show,both methods can effectively solve the PFT problem.
文摘In the multiple protocol label-switched (MPLS) networks, the commodities are transmitted by the label-switched paths (LSPs). For the sake of reducing the total cost and strengthening the central management, the MPLS networks restrict the number of paths that a commodity can use, for maintaining the quality of service (QoS) of the users, the demand of each commodity must be satisfied. Under the above conditions, some links in the network may be too much loaded, affecting the performance of the whole network drastically. For this problem, in [1], we proposed two mathematical models to describe it and a heuristic algorithm which quickly finds transmitting paths for each commodity are also presented. In this paper, we propose a new heuristic algorithm which finds a feasible path set for each commodity, and then select some paths from the path set through a mixed integer linear programming to transmit the demand of each commodity. This strategy reduces the scale of the original problem to a large extent. We test 50 instances and the results show the effectiveness of the new heuristic algorithm.
基金Proje ct supported by the National Natural Science Foundation of China(No.61571055)the Fund of SKL of MMW(No.K201815)the Important National Science&Technology Specific Projects(No.20 17ZX03001028)
文摘To reduce the transmission cost in 5G multicast networks that have separate control and data planes, we focus on the minimum-power-cost network-coding subgraph problem for the coexistence of two multieasts in wireless networks. We propose two suboptimal algorithms as extensions of the Steiner tree multicast. The critical 1-cut path eliminating （C1CPE） algorithm attempts to find the minimum-cost solution for the coexistence of two multicast trees with the same throughput by reusing the links in the topology, and keeps the solution decodable by a coloring process. For the special case in which the two multicast trees share the same source and destinations, we propose the extended selective closest terminal first （E-SCTF） algorithm out of the CICPE algorithm. Theoretically the complexity of the E-SCTF algorithm is lower than that of the C1CPE algorithm. Simulation results show that both algorithms have superior performance in terms of power cost and that the advantage is more evident in networks with ultra-densification.
文摘Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we consider both types of the weighted Hamming distances for measuring the adjustment.In the sum-type case,it is shown that the inverse problem is APX-hard.In the bottleneck-type case,we present a polynomial time algorithm.
