《海洋枢纽规划-外文资料翻译.docx》由会员分享，可在线阅读，更多相关《海洋枢纽规划-外文资料翻译.docx（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、附件1：外文资料翻译译文海洋枢纽规划 海洋枢纽和辐射网络应用于发送集装箱船已经有二十多年了,但很少有人注意到这些网络上。海运网络问题作为一个解决中心位置的问题,所涉及的包括最优区位的辐射和在运输网络中的分配,当然分配也可以在辐射路线之间。在本文中提出了令人满意的解决方法。二次整数模型由两阶段组成:一个中心选址模型，一个辐分配模型。我们就应用一个基于最短路径规则和试验性路径的基础上的启发式方案，验证了该模型的正确性和提出解决问题的方法。结果表明,所建立的模型是一个凹函数,这是利用开发方面的中心数利润总额的规模经济得出的。这样辐射分配可能变化为一个枢纽的最佳选择位置。最近进行了对枢纽和辐射的网络设
2、计模型的研究，尽管海洋枢纽和辐射网络用于发送集装箱船已经有二十年了，但是只有少数文章重视到这些网络。一些文章制订数学规划模型来发送集装箱船，但这些模型忽视集装箱船的特征路线。不同的系统需要不同的模型描述情景模式并且需要充分根据其自身特点。这篇论文的目的是建立一个更适合的模型来获得海洋运输的特征网络，同时最大化运输网络的利润。在交通运输网络中,从它的起源节点移动到其目的节点,通常能组成枢纽系统。在这种系统中,运输枢纽作为特殊节点巩固和交换连接着许多的原始地和目的地。这些相互联系的枢纽就有了很多的应用，例如航空旅行，通信网络，邮政的交货系统，集装箱船。使用枢纽和辐射系统的主要原因是因为枢纽更加适合
3、于从大的联合交通向小数目的枢纽连接枢纽的规模经济。因此降低了在这些连接中的运输成本。枢纽和辐射网络系统通常由至少两个等级的系统做成，他们是枢纽层和辐射层。枢纽定位问题是要确定一个最佳数值使交通运输枢纽布局以及其辐射定位在一个网络上。通常，总的运输成本总是最低的。自从欧凯利第一次提出一个二次的整数规划，二次启发式算法去解决枢纽定位问题，越来越多的研究已经涉及到原型的问题,。比如坎贝尔，偶凯利和米勒的研究。坎贝尔提出将这个问题分成四个类别：设计枢纽中位数问题、可行的枢纽选址问题、枢纽中心问题和枢纽覆盖面问题。其中前两个为研究重点。如果枢纽的数量没有给定，那么枢纽定位问题就是设计枢纽中位数问题。不一
4、样的假设可能导致不一样的问题结构和网络模式。例如单一的分配意味着每一辐射对应着一个枢纽，而一个多重分配则允许辐射连接一个以上的枢纽。在某些情况下，允许辐射之间存在直接的路径，这将导致“非严格中心枢纽策略”问题。尽管它有广泛的使用，但是设计枢纽和辐射系统仍然是一个挑战性任务，主要困难在于模型提法和算法的解为特征的一个特别系统。作为解决枢纽定位问题的需要，以前的论文主要地关注启发式算法比较多一些。欧凯利第一次建立了基于距离原则解决设计枢纽选址问题的假说，这就将所有辐射和一个一个的枢纽相互关联起来了。柯林斯维茨提出了两套基于多目标距离和流动原则的思维，而不是单一的距离。柯林斯维茨首先先确定中心枢纽的
5、位置，然后将辐射线分配到确定的枢纽上，然后通过分配到枢纽的辐射线来进行优化。其他的启发式聚类分成一些节点，然后把枢纽分配到每一个组。在之后的工作中，柯林斯维茨考虑用禁忌搜索，贪婪搜索程序寻求外局部最优。阿金是第一个考虑用拉格朗日松弛解决设计枢纽的规模问题，此外阿金还提供一个分支定界算法和一个以贪婪为依据德交换启发式模型来解决枢纽定位问题的不严密性。在严格的枢纽中，所有的交通量必须通过枢纽进行转运，柯林斯维茨提出了无容量限制的双上升过程来解决枢纽定位问题。欧凯利提出算法来解决方案的两个下界。坎贝尔是第一个制定贪婪的交换的启发式搜索来解决容量限制多路径枢纽定位问题的人。最大流动启发式由最大流准则来
6、分配辐射线到枢纽。而全流量的目的是为了将量减少整个网络的成本。斯科林-科波夫首次提出混合整数配方来寻求单一和多任务的分配问题的解决方法。恩斯特和肻斯穆斯里还制定了分两个阶段产生的确切解决方案。思恩和帕克提出了一个解决单一和多个设计枢纽的定位问题的模型。恩斯特提供了基于无容量限制的启发式算法来解决枢纽定位问题。而恩波利为了解决多枢纽分配问题而提出了基于基于最短路径的混合整数分支定界算法。而博兰等人利用预处理程序和受约束的混合整数模型来解决多重分配任务。海洋集装箱船是由枢纽和辐射决定，其中集装箱运输船携带货物从始发港，通过运输网络中的枢纽到达目的港。在这篇文章中，正如以前研究枢纽定位问题那样，但是
7、也有三点不同： 1)在过去的枢纽定位问题中，枢纽是完全的相互联系的，但是在实际的海洋问题中，枢纽并没有得到充分的网络，他们更像是穿梭的部分，枢纽的连接是按顺序直接连接的。 2)在过去的枢纽定位问题中，交通是通过建立枢纽运行的，每个辐射线必须连接到一个枢纽，在海洋问题中，某些辐射线可能绕过其他的辐射线连接到枢纽，按照这样的分配海洋网络问题可以说是不严密的枢纽分法。 3)在过去的枢纽定位问题中，中间枢纽的成本只是根据中心环节计算，但是在海洋问题中，中间枢纽的成本包括中间枢纽之间的连接的费用之和，他放映了枢纽的层次结构。因此，在本文中添加了这些特征作为问题的一部分，也就是不严密的枢纽定位问题。这些问
8、题先前的文献中尚未研究过。由于交通枢纽港口的增加，海洋运输经营者可受益于枢纽港口船舶形成的规模经济。为了充分的利用这个优势，海洋运输经营者必须解决海洋运输的不严密的枢纽定位问题。然而这些问题只是在某些文献中得到了有限的重视。罗能回顾过去十年的文献发现了路线和调度的问题，并且只有少数涉及到发送集装箱运输船。拉娜和维克森提出了混合整数非线性规划的分解来解决最佳路径问题。哈拉米略和帕拉卡斯以及鲍威尔开发了线性规划来描述航线集装箱船和部署方案。克里斯提森和纳格林提出了一种基于最优解分支定界和容量限制来解决船舶航线问题。 弗格霍斯特通过为每个船舶类型编号以及相关的班轮航运线路问题来确定最佳船舶类型。陆提
9、出了一个与周期和船舶限制的分支界定算法来寻求船舶的最佳路径。楚等人提出了用混合整数模型来确定集装箱港口调用和受周期限制的港口需求之间的最优序列。阿扎荣和肯法采用了基于随机动态规划半马氏决策过程和网络流理论找到船舶的动态最短路径问题。这些路径都忽视了真实的海洋路径，那些复杂的模型结果中会产生不切实际解决方案。最近毛柔等人开发了整数规划模型来解决基于枢纽和辐射网络的船舶分配问题。谢和常提出了一个整数规划模型，其中部分修改了欧凯利的模型以解决不严密的海洋枢纽定位问题。在以后的工作中，谢和王提出了基于同一问题的距离规则的启发式算法的二次整数最小化模型。在本文中我们提出了一个有广泛应用的途径来解决不严密
10、的海洋枢纽定位问题，该模型比谢和王的成本最小化模型更大更复杂，这是因为: (1)成本最小化模型只考虑运输成本，而这个模型同时考虑收入之间的权衡及相关费用（固定成本，航行成本，港口成本，营运成本，燃油成本） (2)在成本最小化模型，没有船的分类是考虑在内。在这种模式中，不同大小的船分成两个层次的系统，引进了更多的限制条件（负载能力，当运载货物时船舶出发和返回，计划时限） (3)在此模型中，服务的频率和船的数量只被视为决策变数。有了这些考虑，该模型可以更充分地代表在现实中存在的问题。以我们最好的知识，这是第一次提出在枢纽定位问题中收入和成本如何权衡，即使我们看到有许多相似的应用。我们的方法是从跨越
11、太平洋航线上得到数据。部分的交通流从各个资源中估计，这是因为真实的数据并不是都是可用的。 Marine hub location problemsMarine hub-and-spoke networks have been applied to routing containerships for over two decades, but few papers have devoted their attention to these networks. The marine network problems are known as single assignment nonstrict
12、 hub location problems (SNHLPs),which deal with the optimal location of hubs and allocation of spokes to hubs in a network, allowing direct routes between some spokes. In this paper we present a satisfactory approach for solving SHNLPs.The quadratic integer profit programming consists of two-stage c
13、omputational algorithms: a hub location model and a spoke allocation model. We apply a heuristic scheme based on the shortest distance rule and an experimental case based on the Trans-Pacific Routes is presented to illustrate the models formulation and solution methods.The results indicate that the
14、model is a concave function, exploiting the economies of scale for total profit with respect to the number of hubs. The spoke allocation may change an optimal choice of hub locations.A number of studies have recently been done on the network design problem for hub-and-spoke patterns.Although marine
15、hub-and-spoke networks have been applied to routing containerships for over two decades,few papers have so far devoted their attention to these networks. Some papers formulated mathematical programming models for routing containerships, but these models neglect the characteristics of containerships
16、routes. Different systems require different models to adequately portray scenario patterns based upon their characteristic features (OKelly, 1998; Bryan and OKelly, 1999). The aim of this paper is to develop a more adequate model for capturing the particular characteristics of marine networks, while
17、 maximizing the total transportation profit of the network.Transportation networks, in which traffic moves from its origin node to its destination node, are often configured as hub-and-spoke systems. In such systems, hubs are special nodes that serve as consolidation and switching points that connec
18、t many origins and destinations. The concept of these interacting hubs arises frequently in many applications, such as air passenger travel, telecommunication network, postal delivery systems, and containerships. The major incentive for employing a hub-and-spoke systems is that hubs enjoy economies
19、of scale achieved by larger consolidating traffic into smaller number of hub-to-hub links, thus generating lower unit transportation cost on those links. Hub-and-spoke networks usually consist of at least a two-level system: hub level and spoke level. The hubto- hub portion is usually discounted by
20、a factor (0 1) to account for the concept of hubbing economies。 The hub location problems (HLPs) are to determine an optimal number and location of hubs, and allocation of spokes (non-hubs) to these hubs in a network such that, typically, the total transportation cost is minimized. Since OKelly (198
21、6a, 1986b, 1987) first proposed a quadratic integer programming and two heuristic algorithms for solving the HLPs, an increasing number of studies have been done on this prototype of he problems, such as Campbell (1994) and OKelly and Miller (1994). Campbell (1994) presented the HLPs into four diffe
22、rent basic categories: the p-hub median problem, the uncapacitated hub location problem, phub center problems, and hub covering problems. Most of work on HLPs has focused on the former two problems. If the number of hubs is not given in a network, the phub median problem is usually the HLP. In uncap
23、acitated HLPs, there is a fixed cost for establishing a hub, but no constraint on the number of hubs (Campbell, 1994; Klincewicz, 1996; Ebery et al., 2000). Different assumptions may result in different problem structures and network patterns. For example, a single assignment is structured so that e
24、ach spoke is assigned to only one hub (OKelly, 1987, 1992; Klincewicz, 1991, 1992;Campbell, 1994, 1996; Skorin-Kapov and Skorin-Kapov, 1994; Skorin-Kapov et al., 1996; Aykin, 1990, 1995; Ernst and Krishnamoorthy, 1996; Kara, et al. 2003). A multiple assignment allows spokes to interact with more tha
25、n one hub (Campbell, 1994; OKelly and Lao, 1991; Klincewicz, 1996; Skorin-Kapov et al., 1996; Krishnamoorthy et al., 1998, 2000). Occasionally, there is also a fixed cost to establish a hub (OKelly, 1992; Campbell, 1994; Aykin, 1995; OKelly et al., 1996; Sohn and Park, 1998). In some cases, it is po
26、ssible to allow direct routes between some spokes, resulting in a problem called “Nonstrict Hubbing Policy” (Aykin,1994, 1995).Despite its widespread use, designing efficient hub-and-spoke systems remains a challenging task. A primary difficulty lies in model formulations and solution algorithms for
27、 the characteristic of a particular system. As a result of the computational needs in solving HLPs, previous studies primarily focused on heuristic algorithms rather than exact solutions for models. OKelly (1987) was first to develop two enumeration- based heuristics using distance rule for solving
28、the single assignment p-hub median problem, in which every spoke is allocated to exactly one hub and all hub linkages are fully interconnected (i.e., a pure hub-and-spoke network). Klincewicz (1991) proposed two sets of heuristics for larger problems based on a multi-criteria distance and flow rule
29、rather than on distance alone. Klincewiczs exchange heuristics first determine the hub locations, and then assignment of spokes to hubs, with changes the solution made by the assignment of hubs to spokes. The other clustering heuristics divide the nodes into several groups and assign a hub for each
30、group. In later work, Klincewicz (1992) considered tabu search and greedy search procedures to explore solutions beyond local optima. Skorin- Kapov and Skorin-Kapov (1994) developed other tabu search heuristic, assigning equal importance to the location and allocation portions of the problem. Aykin
31、(1994) was first to consider the Langrangian relaxation for the p-hub median problem with hub capacity. Aykin (1995) provided a branch-and-bound algorithm and a simulated annealing based on greedy interchange heuristic for investigating the effects of strict and nonstrict on the HLPs. In strict hubb
32、ing, all traffic must ship via a set of hubs; nonstrict hubbing allows some direct trips between some spokes. Klincewicz (1996) proposed a dual ascent procedure for a sequence of uncapacitated HLPs. OKelly et al. (1995) presented algorithm to determine two lower bounds on the optimal solution. Skori
33、n-Kapov et al. (1996) developed effective mixed integer formulations with tight linear programming relaxations laxations for the HLPs. Campbell (1996) was first one to formulate a greedy exchange heuristic to solve uncapacitated, multiple assignment HLPs. The MAXFLO heuristic assigns spoke to hub by
34、 maximum flow rule, whereas the ALLFLOs purpose is to minimize the total network cost. By modifying Campbells model (Campbell, 1996), Skorin-Kapov et al. (1996) were first to propose mixed integer formulations for finding exact solutions for the single and multiple assignment problems. Ernst and Kri
35、shnamoorthy (1996) also developed a two-stage approach to produce exact solutions. Sohn and Park (1998) provided a reduced size formulation model for uncapacitated single and multiple p-hub location problems. Ernst and presented exact and heuristic algorithms for the uncapacitated multiple assignmen
36、t HLPs, while Ebery et al. (2000) presented mixed integer formulations using branchand- bound algorithm, based on the shortest path rule, for the capacitated multiple assignment problem. Boland et al. (2004) considered pre-processing procedures and tightening constraints with existing mixed integer
37、linear programming model for multiple assignment problem.Marine containership routes are hub-and-spoke structures, in which containerships carry cargo from their origin ports, through hub ports in the network, to their destination ports. In this paper, the problem is the HLP as previously studied, b
38、ut for different applications. There are three fundamental differences: (1) In past HLPs, hubs are fully interconnected, whereas in marine problems, hubs are not fully networks; rather they are more like shuttle patterns. The hub connections are sequential and in the same directional order (Hsieh an
39、d Chang, 2001). (2) In past HLPs, traffic is shipped via set of hubs, and each spoke connects to a hub. In marine problems, however, some spokes may bypass others to connect to a hub (see Gilman, 1981; Pearson and Fossey, 1983). In such an allocation, marine network problems can be classified as non
40、strict hubbing policy, as defined by Aykin (1995). (3) In past HLPs, the interhub cost counts by only cost with hub link. In marine problems, the interhub cost has to accumulate all cost on each interhub link, reflecting the hub level structure. Consequently, the definition of our problem having suc
41、h features to be discussed in this paper is referred to as single assignment, nonstrict hub location problems (SNHLPs). These problems have not yet been studied in previous literature.Due to the increased traffic at hub ports, marineliner operators can benefit from the scale economies of ship capaci
42、ty utilized at hub ports (Chadwin et al.,1990). In order to take full advantage of this, however, it is critical for liner operators to solve marine SNHLPs. Yet these problems have received limited attention in the literature. Ronen (1993) reviewed literature from the last decade regarding routing a
43、nd scheduling problems and identified only a few that pertained to routing containerships. Rana and Vickson (1998, 1991) proposed a mixed integer nonlinear programming combined with decomposition to solve the optimal routing problem. Jaramillo and Perakis (1991), Cho and Perakis (1996), and Powell a
44、nd Perakis (1997) developed linear programming to describe the routing containerships and deployment scenario. Christiansen and Nygreen (1998) presented an optimal solution based on branch-andbound search with inventory constraints for ship routing problems.Fagerholt (1999) identified optimal ship t
45、ypes, the number for each type, and coherent routes for the liner shipping problem. Lu (2002) proposed a branch-andbound algorithm with cycle time and vessel constraints for an optimal ship routing. Chu et al. (2003) proposed a mixed integer model to determine an optimal sequence of port calls and c
46、ontainer flow between demand ports with cycle time constraints. Azaron and Kianfar (2003) applied a stochastic dynamic programming based on semi-Markov decision processes and network flow theory to find the dynamic shortest path for ship routing problem. These studies neglected the reality of marine
47、 routing problem, resulting in models that were complicated and possibly generated unrealistic solutions to marine SNHLPs. Recently, Mourao et al. (2002) developed an integer programming model to solve ship fleet assignment with defined voyages based on hub-andspoke networks. Hsieh and Chang (2001)
48、proposed an integer linear programming, which modified OKellys model (OKelly, 1987), to solve marine SNHLPs. In later work, Hsieh and Wong (2003) proposed a quadratic integer cost minimization model with heuristic algorithms based on distance rule for the same problem. In this paper we propose an ex
49、tensive approach for marine SNHLPs. The model is larger and more complicated than the cost minimization model of Hsieh and Wong (2003) because: (1) the cost minimization model considered only transportation cost, whereas this model considers simultaneously the tradeoffs between revenue and related costs (e.g., fixed cost, sailing cost, port cost, operational cost, and bunker cost). (2) In cost minimization model, no ship