S-3 外文資料翻譯 殷琪

《S-3 外文資料翻譯 殷琪》由會員分享，可在線閱讀，更多相關《S-3 外文資料翻譯 殷琪（12頁珍藏版）》請在裝配圖網上搜索。

1、淮陰工學院畢業(yè)設計（論文）外文資料翻譯學院：交通工程學院專業(yè)：交通運輸姓名：殷琪學號：1071501134外文出處：Journal of Marine Scienceand Technology附件：1.外文資料翻譯譯文；2.外文原文。指導教師評語：簽名：2011年2 月 22 日附件1:外文資料翻譯譯文海洋樞紐規(guī)劃海洋樞紐和輻射網絡應用于發(fā)送集裝箱船已經有二十多年了，但很少有人注意 到這些網絡上。海運網絡問題作為一個解決中心位置的問題，所涉及的包括最優(yōu)區(qū) 位的輻射和在運輸網絡中的分配，當然分配也可以在輻射路線之間。在本文中提出 了令人滿意的解決方法。二次整數模型由兩階段組成：一個中心選址模型

2、，一個輻 分配模型。我們就應用一個基于最短路徑規(guī)則和試驗性路徑的基礎上的啟發(fā)式方 案，驗證了該模型的正確性和提出解決問題的方法。結果表明，所建立的模型是一 個凹函數，這是利用開發(fā)方面的中心數利潤總額的規(guī)模經濟得出的。這樣輻射分配 可能變化為一個樞紐的最佳選擇位置。最近進行了對樞紐和輻射的網絡設計模型的研究，盡管海洋樞紐和輻射網絡用 于發(fā)送集裝箱船已經有二十年了，但是只有少數文章重視到這些網絡。一些文章制 訂數學規(guī)劃模型來發(fā)送集裝箱船，但這些模型忽視集裝箱船的特征路線。不同的系 統(tǒng)需要不同的模型描述情景模式并且需要充分根據其自身特點。這篇論文的目的是 建立一個更適合的模型來獲得海洋運輸的特征網絡

3、，同時最大化運輸網絡的利潤。在交通運輸網絡中，從它的起源節(jié)點移動到其目的節(jié)點，通常能組成樞紐系統(tǒng)。 在這種系統(tǒng)中，運輸樞紐作為特殊節(jié)點鞏固和交換連接著許多的原始地和目的地。 這些相互聯系的樞紐就有了很多的應用，例如航空旅行，通信網絡，郵政的交貨系 統(tǒng)，集裝箱船。使用樞紐和輻射系統(tǒng)的主要原因是因為樞紐更加適合于從大的聯合 交通向小數目的樞紐連接樞紐的規(guī)模經濟。因此降低了在這些連接中的運輸成本。 樞紐和輻射網絡系統(tǒng)通常由至少兩個等級的系統(tǒng)做成，他們是樞紐層和輻射層。樞紐定位問題是要確定一個最佳數值使交通運輸樞紐布局以及其輻射定位在 一個網絡上。通常，總的運輸成本總是最低的。自從歐凱利第一次提出一個

4、二次的 整數規(guī)劃，二次啟發(fā)式算法去解決樞紐定位問題，越來越多的研究已經涉及到原型 的問題，。比如坎貝爾，偶凱利和米勒的研究?？藏悹柼岢鰧⑦@個問題分成四個類 別：設計樞紐中位數問題、可行的樞紐選址問題、樞紐中心問題和樞紐覆蓋面問題。 其中前兩個為研究重點。如果樞紐的數量沒有給定，那么樞紐定位問題就是設計樞 紐中位數問題。不一樣的假設可能導致不一樣的問題結構和網絡模式。例如單一的 分配意味著每一輻射對應著一個樞紐，而一個多重分配則允許輻射連接一個以上的 樞紐。在某些情況下，允許輻射之間存在直接的路徑，這將導致“非嚴格中心樞紐 策略”問題。盡管它有廣泛的使用，但是設計樞紐和輻射系統(tǒng)仍然是一個挑戰(zhàn)性任

5、務，主要 困難在于模型提法和算法的解為特征的一個特別系統(tǒng)。作為解決樞紐定位問題的需 要，以前的論文主要地關注啟發(fā)式算法比較多一些。歐凱利第一次建立了基于距離 原則解決設計樞紐選址問題的假說，這就將所有輻射和一個一個的樞紐相互關聯起 來了?？铝炙咕S茨提出了兩套基于多目標距離和流動原則的思維，而不是單一的距 離?？铝炙咕S茨首先先確定中心樞紐的位置，然后將輻射線分配到確定的樞紐上， 然后通過分配到樞紐的輻射線來進行優(yōu)化。其他的啟發(fā)式聚類分成一些節(jié)點，然后 把樞紐分配到每一個組。在之后的工作中，柯林斯維茨考慮用禁忌搜索，貪婪搜索 程序尋求外局部最優(yōu)。阿金是第一個考慮用拉格朗日松弛解決設計樞紐的規(guī)模問

6、題，此外阿金還提供一個分支定界算法和一個以貪婪為依據德交換啟發(fā)式模型來解 決樞紐定位問題的不嚴密性。在嚴格的樞紐中，所有的交通量必須通過樞紐進行轉 運，柯林斯維茨提出了無容量限制的雙上升過程來解決樞紐定位問題。歐凱利提出 算法來解決方案的兩個下界。坎貝爾是第一個制定貪婪的交換的啟發(fā)式搜索來解決 容量限制多路徑樞紐定位問題的人。最大流動啟發(fā)式由最大流準則來分配輻射線到 樞紐。而全流量的目的是為了將量減少整個網絡的成本。斯科林-科波夫首次提出 混合整數配方來尋求單一和多任務的分配問題的解決方法。恩斯特和肯斯穆斯里還 制定了分兩個階段產生的確切解決方案。思恩和帕克提出了一個解決單一和多個設 計樞紐的

7、定位問題的模型。恩斯特提供了基于無容量限制的啟發(fā)式算法來解決樞紐 定位問題。而恩波利為了解決多樞紐分配問題而提出了基于基于最短路徑的混合整 數分支定界算法。而博蘭等人利用預處理程序和受約束的混合整數模型來解決多重 分配任務。海洋集裝箱船是由樞紐和輻射決定，其中集裝箱運輸船攜帶貨物從始發(fā)港，通 過運輸網絡中的樞紐到達目的港。在這篇文章中，正如以前研究樞紐定位問題那樣， 但是也有三點不同：1）在過去的樞紐定位問題中，樞紐是完全的相互聯系的，但是在實際的海洋問題 中，樞紐并沒有得到充分的網絡，他們更像是穿梭的部分，樞紐的連接是按順序直 接連接的。2）在過去的樞紐定位問題中，交通是通過建立樞紐運行的，

8、每個輻射線必須連接 到一個樞紐，在海洋問題中，某些輻射線可能繞過其他的輻射線連接到樞紐，按照 這樣的分配海洋網絡問題可以說是不嚴密的樞紐分法。3）在過去的樞紐定位問題中，中間樞紐的成本只是根據中心環(huán)節(jié)計算，但是在海 洋問題中，中間樞紐的成本包括中間樞紐之間的連接的費用之和，他放映了樞紐的 層次結構。因此，在本文中添加了這些特征作為問題的一部分，也就是不嚴密的樞 紐定位問題。這些問題先前的文獻中尚未研究過。由于交通樞紐港口的增加，海洋運輸經營者可受益于樞紐港口船舶形成的規(guī)模 經濟。為了充分的利用這個優(yōu)勢，海洋運輸經營者必須解決海洋運輸的不嚴密的樞 紐定位問題。然而這些問題只是在某些文獻中得到了有

9、限的重視。羅能回顧過去十 年的文獻發(fā)現了路線和調度的問題，并且只有少數涉及到發(fā)送集裝箱運輸船。拉娜 和維克森提出了混合整數非線性規(guī)劃的分解來解決最佳路徑問題。哈拉米略和帕拉 卡斯以及鮑威爾開發(fā)了線性規(guī)劃來描述航線集裝箱船和部署方案?？死锼固嵘图{ 格林提出了一種基于最優(yōu)解分支定界和容量限制來解決船舶航線問題。弗格霍斯特通過為每個船舶類型編號以及相關的班輪航運線路問題來確定最 佳船舶類型。陸提出了一個與周期和船舶限制的分支界定算法來尋求船舶的最佳路 徑。楚等人提出了用混合整數模型來確定集裝箱港口調用和受周期限制的港口需求 之間的最優(yōu)序列。阿扎榮和肯法采用了基于隨機動態(tài)規(guī)劃半馬氏決策過程和網絡流

10、理論找到船舶的動態(tài)最短路徑問題。這些路徑都忽視了真實的海洋路徑，那些復雜 的模型結果中會產生不切實際解決方案。最近毛柔等人開發(fā)了整數規(guī)劃模型來解決 基于樞紐和輻射網絡的船舶分配問題。謝和常提出了一個整數規(guī)劃模型，其中部分 修改了歐凱利的模型以解決不嚴密的海洋樞紐定位問題。在以后的工作中，謝和王 提出了基于同一問題的距離規(guī)則的啟發(fā)式算法的二次整數最小化模型。在本文中我 們提出了一個有廣泛應用的途徑來解決不嚴密的海洋樞紐定位問題，該模型比謝和 王的成本最小化模型更大更復雜，這是因為：（1）成本最小化模型只考慮運輸成本，而這個模型同時考慮收入之間的權衡及相 關費用（固定成本，航行成本，港口成本，營運

11、成本，燃油成本）（2）在成本最小化模型，沒有船的分類是考慮在內。在這種模式中，不同大小的 船分成兩個層次的系統(tǒng)，引進了更多的限制條件（負載能力，當運載貨物時船舶出發(fā)和返回，計劃時限)(3) 在此模型中，服務的頻率和船的數量只被視為決策變數。有了這些考慮，該 模型可以更充分地代表在現實中存在的問題。以我們最好的知識，這是第一次提出 在樞紐定位問題中收入和成本如何權衡，即使我們看到有許多相似的應用。我們的方法是從跨越太平洋航線上得到數據。部分的交通流從各個資源中估 計，這是因為真實的數據并不是都是可用的。Marine hub location problemsMarine hub-and-spok

12、e 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 hub location problems (SNHLPs),which deal with the optimal location of hubs and allocation

13、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 computational algorithms: a hub location model and a spoke allocation model. We apply a heuri

14、stic 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 model is a concave function, exploiting the economies of scale for total profit with respect

15、 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 hub-and-spoke networks have been applied to routing containerships for over two decades,few

16、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 routes. Different systems require different models to adequately portray scenario patterns b

17、ased 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 maximizing the total transportation profit of the network.Transportation networks, in which

18、 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 connect many origins and destinations. The concept of these interacting hubs arises frequently in

19、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 of scale achieved by larger consolidating traffic into smaller number of hub-to-hub links, t

20、hus 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 a factor ( 0 ) to account for the concept of hubbing economies。The hub location problems (HL

21、Ps) 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 (1986a, 1986b, 1987) first proposed a quadratic integer programming and two heuristic algorithms

22、for solving the HLPs, an increasing number of studies have been done on this prototype of he problems, such as Campb ell (1994) and OKelly and Miller (1994). Campbell (1994) presented the HLPs into four different basic categories: the p-hub median problem, the uncapacitated hub location problem, hub

23、 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 uncapacitated HLPs, there is a fixed cost for establishing a hub, but no constraint on the number

24、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 each spoke is assigned to only one hub (OKelly, 1987, 1992; Klincewicz, 1991, 1992;Campbell, 1

25、994, 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 than one hub (Campbell, 1994; OKelly and Lao, 1991; Klincewicz, 1996; Skorin-Kapov et al., 1996;

26、 Krishnamoorthy et al., 1998, 2000). Occasionally, there is also a fixed cost to establish a hub (O,Kelly, 1992; Campbell, 1994; Aykin, 1995; OKellyet al., 1996; Sohn and Park, 1998). In some cases, it is possible to allow direct routes between some spokes, resulting in a problem called “NonstrictHu

27、bbing 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 the characteristic of a particular system. As a result of the computational needs in solving

28、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 the single assignment -hub median problem, in which every spoke is allocated to exactly one hu

29、b 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 rather than on distance alone. Klincewiczs exchange heuristics first determine the hub location

30、s, 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 group. In later work, Klincewicz (1992) considered tabu search and greedy search procedures to

31、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 (1994) was first to consider the Langrangian relaxation for the -hub median problem with hub ca

32、pacity. 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 hubbing, all traffic must ship via a set of hubs; nonstrict hubbing allows some direct trips between

33、 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. Skorin-Kapov et al. (1996) developed effective mixed integer formulations with tight linear programmi

34、ng 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 maximum flow rule, whereas the ALLFLOs purpose is to minimize the total network cost. By modify

35、ing Campbells model (Campbell, 1996), Skorin-Kapovet al. (1996) were first to propose mixed integer formulations for finding exact solutions for the single and multiple assignment problems. Ernst and Krishnamoorthy (1996) also developed a two-stage approach to produce exact solutions. Sohn and Park

36、(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 assignment HLPs, while Ebery et al. (2000) presented mixed integer formulations using branchand- bound alg

37、orithm, 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 linearprogramming model for multiple assignment problem.Marine containership routes are hub-and-s

38、poke 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, but for different applications. There are three fundamental differences: (1) In past HLPs, hubs are

39、 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 and Chang, 2001). (2) In past HLPs, traffic is shipped via set of hubs, and each spoke connects to a

40、 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 nonstrict hubbing policy, as defined by Aykin (1995). (3) In past HLPs, the interhub cost counts by o

41、nly 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 such features to be discussed in this paper is referred to as single assignment, nonstrict hub locati

42、on 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 capacity utilized at hub ports (Chadwin et aJ1990). In order to take full advantage of this, however, it

43、 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 and scheduling problems and identified only a few that pertained to routing containerships. Rana and

44、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 and Perakis (1997) developed linear programming to describe the routing containerships and deployment

45、 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 types, the number for each type, and coherent routes for the liner shipping problem. Lu (2002) propos

46、ed 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 container flow between demand ports with cycle time constraints. Azaron and Kianfar (2003) applied a

47、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 routing problem, resulting in models that were complicated and possibly generated unrealistic solut

48、ions 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) proposed an integer linear programming, which modified OKellys model (OKelly, 1987), to solve marine

49、 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 extensive approach for marine SNHLPs. The model is larger and more complicated than the cost minimizat

50、ion 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 min

51、imization model, no ship assignment is included. In this model, however, different ship sizes are deployed to the two-level system, introducing additional sets of constraints (e.g., load capacity, cargo carried when vessel outgoing and returning, planning horizon). (3) In this model, the frequency o

52、f service and the number of vessels are viewed as decision variables. With these considerations, the model can more adequately represent the reality of the existing problems. To the best of our knowledge, this is the first work to provide a means to explicitly address tradeoffs between revenue and cost on the HLPs in the literature; even we can imagine many similar applications.Our approaches are tested on a data set from Trans- Pacific Routes. Parts of traffic flow are estimated from various sources because real data are not generally available.