Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. Triangle packing problem is a special case of p...Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. Triangle packing problem is a special case of polygon packing problem and also NP-hard, so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. In this paper, a new concept of rigid placement is proposed, based on which a discrete solution space called rigid solution space is constructed. Each solution in the rigid solution space can be built by continuously applying legal rigid placements one by one until all the triangles are placed into the rectangle container without overlapping. The proposed Least-Destruction-First (LDF) strategy determines which rigid placement has the privilege to go into the rectangle container. Based on this, a heuristic algorithm is proposed to solve the problem. Combining Least-Destruction-First strategy with backtracking, the corresponding backtracking algorithm is proposed. Computa- tional results show that our proposed algorithms are efficient and robust. With slight modification, these techniques can be con- veniently used for solving polygon packing problem.展开更多
This paper measures the efficiency of ports in the Yangtze River Delta Region(YRDR) in 2008 and 2013 using port berth quantity, quay length, and human resources as input indicators, using cargo and container throughpu...This paper measures the efficiency of ports in the Yangtze River Delta Region(YRDR) in 2008 and 2013 using port berth quantity, quay length, and human resources as input indicators, using cargo and container throughput as output indicators, and considering traditional(foreign trade dependence and industrialization level) and modern environmental factors(traffic line density, financial development level, and informatization level). To achieve such aim, this study constructs a multi-stage data envelopment analysis model(DEA) that identifies effective port decision-making units(DMUs) and generates a highly accurate conclusion by eliminating the interference from the exogenous environment and random errors. First, the external environment significantly affects port efficiency, with the traditional environmental factors showing huge fluctuations and the modern environmental factors producing great benefits. Second, the efficiency of ports in YRDR has increased from 2008 to 2013 primarily because of their pure technical efficiency. Third, the weighted standard deviation ellipse(SDE) analysis results reveal that the efficiency pattern of ports significantly deviates from their throughput pattern, while the center of SDE of port efficiency moves from the eastern coastal regions to the northwest regions. Based on these findings, this paper proposes spatial development strategies for YRDR, such as creating an unblocked environment where spatial elements can freely circulate, intensifying port-city joint development, implementing differentiated policies, and focusing on the spatial collaboration of port efficiency.展开更多
文摘Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. Triangle packing problem is a special case of polygon packing problem and also NP-hard, so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. In this paper, a new concept of rigid placement is proposed, based on which a discrete solution space called rigid solution space is constructed. Each solution in the rigid solution space can be built by continuously applying legal rigid placements one by one until all the triangles are placed into the rectangle container without overlapping. The proposed Least-Destruction-First (LDF) strategy determines which rigid placement has the privilege to go into the rectangle container. Based on this, a heuristic algorithm is proposed to solve the problem. Combining Least-Destruction-First strategy with backtracking, the corresponding backtracking algorithm is proposed. Computa- tional results show that our proposed algorithms are efficient and robust. With slight modification, these techniques can be con- veniently used for solving polygon packing problem.
基金Under the auspices of National Natural Science Foundation of China(No.41271136,41501142)
文摘This paper measures the efficiency of ports in the Yangtze River Delta Region(YRDR) in 2008 and 2013 using port berth quantity, quay length, and human resources as input indicators, using cargo and container throughput as output indicators, and considering traditional(foreign trade dependence and industrialization level) and modern environmental factors(traffic line density, financial development level, and informatization level). To achieve such aim, this study constructs a multi-stage data envelopment analysis model(DEA) that identifies effective port decision-making units(DMUs) and generates a highly accurate conclusion by eliminating the interference from the exogenous environment and random errors. First, the external environment significantly affects port efficiency, with the traditional environmental factors showing huge fluctuations and the modern environmental factors producing great benefits. Second, the efficiency of ports in YRDR has increased from 2008 to 2013 primarily because of their pure technical efficiency. Third, the weighted standard deviation ellipse(SDE) analysis results reveal that the efficiency pattern of ports significantly deviates from their throughput pattern, while the center of SDE of port efficiency moves from the eastern coastal regions to the northwest regions. Based on these findings, this paper proposes spatial development strategies for YRDR, such as creating an unblocked environment where spatial elements can freely circulate, intensifying port-city joint development, implementing differentiated policies, and focusing on the spatial collaboration of port efficiency.
