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.展开更多
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.展开更多
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.展开更多
The algorithm under this name, together with the variants, is a method that solves the problems of optimal flow and costs. Examples of such problems are planning and procurement, scheduling by contractors, distributio...The algorithm under this name, together with the variants, is a method that solves the problems of optimal flow and costs. Examples of such problems are planning and procurement, scheduling by contractors, distribution and supply systems, transport on the road or rail network, electricity transmission, computer and telecommunications networks, pipe transmission systems (water, oil, …), and the like. The main goal of any business organization is to increase profits and satisfy its customers. Because business is an integral part of our environment, their goals will be limited by certain environmental factors and economic conditions. The out-of-kilter algorithm is used to solve a complex allocation problem involving interactive and conflicting personal choices subject to interactive resource constraints. The paper presents an example of successful use of this algorithm and proposes an extension to the areas of corporate and social planning. Customer demand, warehousing, and factory capacity were used as input for the model. First, we propose a linear programming approach to determine the optimal distribution pattern to reduce overall distribution costs. The proposed model of linear programming is solved by the standard simplex algorithm and the Excel-solver program. It is noticed that the proposed model of linear programming is suitable for finding the optimal distribution pattern and total minimum costs.展开更多
In the optimization of train diagrams, selecting the arrival and departure paths of the through gains has a great impact on the dwell time at district stations. In this paper, on the basis of train paths and the throu...In the optimization of train diagrams, selecting the arrival and departure paths of the through gains has a great impact on the dwell time at district stations. In this paper, on the basis of train paths and the through train connection time standard at district stations, we built a mathematical model aiming at minimizing dwell time of through trains at two adjacent district stations, and then converted this into a network flow model to which is added a source and a sink node. Then, we propose a new algorithm for solving the network flow model based on the minimum-cost flow algorithm. A case study for through trains from the Guiyang South Railway Station to the Chongqing West Railway Station shows that the algorithm is reliable and efficient for solving the problem of through train connections, and there is a reduction in the total dwell time that the through trains spend at two adjacent district stations.展开更多
文摘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.
文摘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.
文摘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.
文摘The algorithm under this name, together with the variants, is a method that solves the problems of optimal flow and costs. Examples of such problems are planning and procurement, scheduling by contractors, distribution and supply systems, transport on the road or rail network, electricity transmission, computer and telecommunications networks, pipe transmission systems (water, oil, …), and the like. The main goal of any business organization is to increase profits and satisfy its customers. Because business is an integral part of our environment, their goals will be limited by certain environmental factors and economic conditions. The out-of-kilter algorithm is used to solve a complex allocation problem involving interactive and conflicting personal choices subject to interactive resource constraints. The paper presents an example of successful use of this algorithm and proposes an extension to the areas of corporate and social planning. Customer demand, warehousing, and factory capacity were used as input for the model. First, we propose a linear programming approach to determine the optimal distribution pattern to reduce overall distribution costs. The proposed model of linear programming is solved by the standard simplex algorithm and the Excel-solver program. It is noticed that the proposed model of linear programming is suitable for finding the optimal distribution pattern and total minimum costs.
文摘In the optimization of train diagrams, selecting the arrival and departure paths of the through gains has a great impact on the dwell time at district stations. In this paper, on the basis of train paths and the through train connection time standard at district stations, we built a mathematical model aiming at minimizing dwell time of through trains at two adjacent district stations, and then converted this into a network flow model to which is added a source and a sink node. Then, we propose a new algorithm for solving the network flow model based on the minimum-cost flow algorithm. A case study for through trains from the Guiyang South Railway Station to the Chongqing West Railway Station shows that the algorithm is reliable and efficient for solving the problem of through train connections, and there is a reduction in the total dwell time that the through trains spend at two adjacent district stations.
