This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems.Using the duality theory of the linear programmin...This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems.Using the duality theory of the linear programming and convex theory,the generalized directional derivative of the general multicommodity minimal cost flow problems is derived.The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions.展开更多
Introducing InterSatellite Links(ISLs)is a major trend in new-generation Global Navigation Satellite Systems(GNSSs).Data transmission scheduling is a crucial problem in the study of ISL management.The existing researc...Introducing InterSatellite Links(ISLs)is a major trend in new-generation Global Navigation Satellite Systems(GNSSs).Data transmission scheduling is a crucial problem in the study of ISL management.The existing research on intersatellite data transmission has not considered the capacities of ISL bandwidth.Thus,the current study is the first to describe the intersatellite data transmission scheduling problem with capacity restrictions in GNSSs.A model conversion strategy is designed to model the aforementioned problem as a length-bounded single-path multicommodity flow problem.An integer programming model is constructed to minimize the maximal sum of flows on each intersatellite edge;this minimization is equivalent to minimizing the maximal occupied ISL bandwidth.An iterated tree search algorithm is proposed to resolve the problem,and two ranking rules are designed to guide the search.Experiments based on the BeiDou satellite constellation are designed,and results demonstrate the effectiveness of the proposed model and algorithm.展开更多
VPN service providers (VSP) and IP-VPN customers have traditionally maintained service demarcation boundaries between their routing and signaling entities. This has resulted in the VPNs viewing the VSP network as an o...VPN service providers (VSP) and IP-VPN customers have traditionally maintained service demarcation boundaries between their routing and signaling entities. This has resulted in the VPNs viewing the VSP network as an opaque entity and therefore limiting any meaningful interaction between the VSP and the VPNs. A key challenge is to expose each VPN to information about available network resources through an abstraction (TA) [1] which is both accurate and fair. In [2] we proposed three decentralized schemes assuming that all the border nodes performing the abstraction have access to the entire core network topology. This assumption likely leads to over- or under-subscription. In this paper we develop centralized schemes to partition the core network capacities, and assign each partition to a specific VPN for applying the decentralized abstraction schemes presented in [2]. First, we present two schemes based on the maximum concurrent flow and the maximum multicommodity flow (MMCF) formulations. We then propose approaches to address the fairness concerns that arise when MMCF formulation is used. We present results based on extensive simulations on several topologies, and provide a comparative evaluation of the different schemes in terms of abstraction efficiency, fairness to VPNs and call performance characteristics achieved.展开更多
This study presents a descriptive and prescriptive analysis of rail service subsidies for China Railway Express(CRE)in the China-Europe freight transportation market.The analysis is conducted by advanced mathematical ...This study presents a descriptive and prescriptive analysis of rail service subsidies for China Railway Express(CRE)in the China-Europe freight transportation market.The analysis is conducted by advanced mathematical modeling and programming methods.Specifically,we implemented a multicommodity multimodal freight transportation network equilib-rium model that can be used for predicting the commodity-specific mode-route cargo flow pattern and hence for assessing the effectiveness and limitations of the current CRE subsidy scheme.To properly quantify the impact of subsidies on individual shippers’decision mak-ing,the model explicitly characterizes individual shippers’mode-route choice behavior and takes into account shipping cost,transit time,capacity-induced congestion surcharge,and unobserved transportation impedances as shippers’disutility.The solution of the net-work equilibrium model resorts to a disaggregate simplicial decomposition(DSD)algo-rithm within the well-known Lagrangian relaxation framework.A bi-level network-based subsidy optimization model is constructed,in which the upper level aims at mini-mizing the sum of revenue loss and congestion charge,and the lower level is the aforemen-tioned freight transportation network equilibrium model.A tabu search procedure is proposed and implemented to derive the solution of the bi-level model.The above models and algorithms are then applied to the China-Europe containerized freight transportation network,which comprises all China-Europe liner shipping lines,all CRE service lines,and the highway networks in China and Europe.The evaluation and optimization results show that the current subsidy scheme creates an imbalanced capacity utilization pattern across CRE service lines while an optimized line-specific subsidy solution can yield note-worthy improvements in the service utilization and economic efficiency of CRE.展开更多
基金the National Natural Science Foundation of China ( 1 0 4 71 0 94) ,the ScienceFoundation of Shanghai Technical Sciences Committee ( 0 2 ZA1 40 70 ) and the Science Foundation ofShanghai Education Committee( 0 2 DK0 6)
文摘This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems.Using the duality theory of the linear programming and convex theory,the generalized directional derivative of the general multicommodity minimal cost flow problems is derived.The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions.
基金This work was supported by the National Natural Science Foundation of China(Nos.61773120 and 71901213)the Foundation for the Author of National Excellent Doctoral Dissertation of China(No.2014-92).
文摘Introducing InterSatellite Links(ISLs)is a major trend in new-generation Global Navigation Satellite Systems(GNSSs).Data transmission scheduling is a crucial problem in the study of ISL management.The existing research on intersatellite data transmission has not considered the capacities of ISL bandwidth.Thus,the current study is the first to describe the intersatellite data transmission scheduling problem with capacity restrictions in GNSSs.A model conversion strategy is designed to model the aforementioned problem as a length-bounded single-path multicommodity flow problem.An integer programming model is constructed to minimize the maximal sum of flows on each intersatellite edge;this minimization is equivalent to minimizing the maximal occupied ISL bandwidth.An iterated tree search algorithm is proposed to resolve the problem,and two ranking rules are designed to guide the search.Experiments based on the BeiDou satellite constellation are designed,and results demonstrate the effectiveness of the proposed model and algorithm.
文摘VPN service providers (VSP) and IP-VPN customers have traditionally maintained service demarcation boundaries between their routing and signaling entities. This has resulted in the VPNs viewing the VSP network as an opaque entity and therefore limiting any meaningful interaction between the VSP and the VPNs. A key challenge is to expose each VPN to information about available network resources through an abstraction (TA) [1] which is both accurate and fair. In [2] we proposed three decentralized schemes assuming that all the border nodes performing the abstraction have access to the entire core network topology. This assumption likely leads to over- or under-subscription. In this paper we develop centralized schemes to partition the core network capacities, and assign each partition to a specific VPN for applying the decentralized abstraction schemes presented in [2]. First, we present two schemes based on the maximum concurrent flow and the maximum multicommodity flow (MMCF) formulations. We then propose approaches to address the fairness concerns that arise when MMCF formulation is used. We present results based on extensive simulations on several topologies, and provide a comparative evaluation of the different schemes in terms of abstraction efficiency, fairness to VPNs and call performance characteristics achieved.
基金sponsored by National Natural Science Foundation of China(Nos.72171175 and 71771150)the Open Foundation of Key Laboratory of Transport Industry of Comprehensive Transportation Theory,and the Fundamental Research Funds of Central Universities at Tongji University.
文摘This study presents a descriptive and prescriptive analysis of rail service subsidies for China Railway Express(CRE)in the China-Europe freight transportation market.The analysis is conducted by advanced mathematical modeling and programming methods.Specifically,we implemented a multicommodity multimodal freight transportation network equilib-rium model that can be used for predicting the commodity-specific mode-route cargo flow pattern and hence for assessing the effectiveness and limitations of the current CRE subsidy scheme.To properly quantify the impact of subsidies on individual shippers’decision mak-ing,the model explicitly characterizes individual shippers’mode-route choice behavior and takes into account shipping cost,transit time,capacity-induced congestion surcharge,and unobserved transportation impedances as shippers’disutility.The solution of the net-work equilibrium model resorts to a disaggregate simplicial decomposition(DSD)algo-rithm within the well-known Lagrangian relaxation framework.A bi-level network-based subsidy optimization model is constructed,in which the upper level aims at mini-mizing the sum of revenue loss and congestion charge,and the lower level is the aforemen-tioned freight transportation network equilibrium model.A tabu search procedure is proposed and implemented to derive the solution of the bi-level model.The above models and algorithms are then applied to the China-Europe containerized freight transportation network,which comprises all China-Europe liner shipping lines,all CRE service lines,and the highway networks in China and Europe.The evaluation and optimization results show that the current subsidy scheme creates an imbalanced capacity utilization pattern across CRE service lines while an optimized line-specific subsidy solution can yield note-worthy improvements in the service utilization and economic efficiency of CRE.
