英语原文共 17 页，剩余内容已隐藏，支付完成后下载完整资料
时间约束多商品网络流问题及其在班轮运输网络设计中的应用
Abstract:The multi-commodity network flow problem is an important sub-problem in several heuristics and exact methods for designing route networks for container ships. The sub-problem decides how cargoes should be transported through the network provided by shipping routes. This paper studies the multi-commodity network flow problem with transit time constraints which puts limits on the duration of the transit of the commodities through the network. It is shown that for the particular application it does not increase the solution time to include the transit time constraints and that including the transit time is essential to offer customers a competitive product.
摘要：多商品网络流问题是集装箱船航线网络设计中的一个重要子问题。子问题决定了如何通过航线提供的网络运输货物。研究了具有运输时间约束的多商品网络流问题，该问题限制了商品通过网络的运输时间。结果表明，对于特定的应用，包含运输时间约束并不增加解决问题的时间，而包含运输时间对于向客户提供有竞争力的产品是必不可少的。
According to IMO (2014) 90% of global trade is carried out via the sea, and ships flying EU flags emit more than 20 million tons of CO2(Maritime CO2, 2014). Container Shipping involves the transportation of a major share of the worlds goods and has been steadily growing (with a small decrease around 2009 due to the economic crisis). Reliance on container shipping to transport goods internationally is only expected to increase due to its economic advantages compared to other transportation modes. Additionally, the CO2 emissions per ton cargo transported using maritime transport is significantly lower than road and rail transport. Hence, even small improvements in the underlying network of a liner shipping company can have a significant impact, both economically and environmentally. Despite this, the Liner Shipping Network Design (LSND) problem has not received a lot of attention in the Operations Research literature and it is far from being a well-solved problem (Meng et al., 2014). Christiansen et al. (2004, 2013) provide comprehensive reviews of the literature published within the field of maritime optimization and liner shipping.
根据IMO（2014年）的数据，全球贸易的90%是通过海洋进行的，悬挂欧盟旗帜的船只排放的二氧化碳超过2000万吨（海洋二氧化碳，2014年）。集装箱运输占世界货物运输的主要份额，并且一直在稳步增长（由于经济危机，2009年前后略有下降）。与其他运输方式相比，国际上对集装箱运输的依赖只会因为其经济优势而增加。此外，海运每吨货物的二氧化碳排放量明显低于公路和铁路运输。因此，即使班轮运输公司基础网络的微小改进，也会在经济和环境方面产生重大影响。尽管如此，班轮运输网络设计（LSND）问题在运筹学文献中并没有得到太多的关注，也远没有得到很好的解决（Meng等人，2014）。Christiansen等人。（2004年和2013年）全面回顾了海运优化和班轮运输领域内发表的文献。
A liner shipping network consists of a number of rotations, which are round trips. It is common to have weekly departures at each port, hence a sufficient number of vessels are deployed to each rotation, to ensure the requested frequency. Fig. 1 shows an example of a real-world rotation. Different vessels have varying capacity and speed, and the transport of a commodity through the network may include the use of several rotations to connect between the origin and destination port. The switch from one rotation to another is referred to as transshipment and there is a cost associated with this since the container must be handled by the quay-cranes at the transshipment ports and possibly stored temporarily at the container yard. On top of this, the container will experience a wait time during the transfer process. Because of the associated cost and transit time and the risk of goods being damaged containers are at most subject to a few transshipments, when traveling from their origin to destination. The transit time is the time it takes a commodity to travel from origin to destination. Transit time is counted in days and allowed transit times may vary from one day to several months Brouer et al. (2014b). Liner shipping networks that are optimized only with respect to cost get an unrealistically high network utilization as containers are allowed on detours that offer unused capacity but in practice they will violate transit time restrictions.
班轮运输网络由若干轮运组成，这些轮运是往返运输。每个港口每周都有离港航班，因此每个轮班都部署了足够数量的船舶，以确保要求的频率。图1示出了真实世界的轮转的示例。不同的船只有不同的容量和速度，通过网络运输一种可能包括在始发港和目的港之间使用若干个轮转的商品。从一个轮换到另一个轮换被称为转运，这是有成本的，因为集装箱必须由转运港的码头起重机搬运，并可能临时储存在集装箱堆场。除此之外，在传输过程中，容器将经历一段等待时间。因为相关的成本和运输时间和货物从原产地到目的地的运输过程中，集装箱受损的风险最多只能承受几次转运。过境时间是商品从原产地到目的地所需的时间。转运时间以天为单位计算，允许转运的时间可能从一天到几个月不等。（2014年b）。班轮运输网络只在成本方面进行了优化，因此网络利用率高得离谱，因为集装箱可以绕道而提供未使用的容量，但实际上它们会违反运输时间限制。
Given a candidate network a multi-commodity network flow (MCF) problem is solved in order to decide, which of the available cargoes should be shipped on which routes. An extensive treatment of the MCF problem can be found in e.g., Ahuja et al. (1993). The MCF problem can be formulated as a linear programming problem which can be solved in polynomial time and there are many algorithms for solving it. One of these methods is by delayed column generation, see Desaulniers et al. (2005) and Ahuja et al. (1993). In order to include the transit time constraint one has to solve an extended version of the problem, the time constrained MCF problem, which is NP-hard. This is easily shown by reduction from the shortest weight constrained path problem (Garey and Johnson, 1979). (We transform this problem into a time constrained MCF by having only one commodity with source and destination as given by the shortest path problem.) This paper presents an algorithm for the time constrained MCF problem and given the LSND application several possible improvements are presented.
给定一个候选网络，解决了多商品网络流（MCF）问题，以确定哪些可用货物应在哪些路线上装运。可在例如Ahuja等人中找到MCF问题的广泛治疗方法（1993年）。MCF问题可以表示为一个可在多项式时间内求解的线性规划问题，求解该问题的算法很多。其中一种方法是延迟色谱柱生成，见Desaulniers等人（2005）和Ahuja等人。（1993年）。为了包含运输时间约束，必须求解该问题的扩展版本，即时间约束MCF问题，这是NP难问题。这很容易通过从最短权重约束路径问题（Garey和Johnson，1979）的归约来证明。本文提出了一种求解时间约束MCF问题的算法，并给出了LSND应用的几种可能的改进。
To the best of our knowledge, most algorithms for the LSND problem do not include transit time restrictions for shipped commodities. This paper studies the consequence of neglecting the transit time restrictions in existing networks. This is done by taking the networks produced by a LSND heuristic and comparing the estimated revenue with and without including the t
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[240423]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
