决定支持灵活的班轮运输

文摘

我们代表结合班轮运输问题和不定期航运,在使用其他运输方式也是一个选择。作为一个例子,我们考虑托盘化运输冷冻鱼从俄罗斯和挪威终端在挪威,荷兰和英国。我们提出一个数学模型规划问题与每个旅游和显示问题实例相关联的实际大小可以解决最优使用标准软件。

1。介绍

海洋运输是国际货物运输的主要运输方式。根据联合国贸易和发展会议(1),2013年全球海洋货物几乎达到96亿吨。其他运输方式也携带了大量的商品,但是,尤其是对于低value-per-ton大宗商品远距离海运运输为主导。通常区分三种不同的操作模式,在海上运输:工业、衬垫和流浪汉运输(2]。工业运输,货物所有者还拥有或控制所使用的船只,然后我们的目标是至少执行所需的货物运输成本。流浪汉航运货物,可以被视为一个出租车系统在船舶运营商利润最大化通过执行运输任务。班轮运输可以比作一个总线系统;船只遵循一个出版行程和时间表。概述船舶路由和调度问题可以发现在2]。

许多现实世界的海上交通规划问题符合上述的操作模式之一,但船也可以操作的方式不符合任何标准的模式。在本文中,我们解决规划问题在班轮运输是主要的概念,但在已知模型决策需要扩展和调整以适应真实的世界。这样做的原因是,在一段时期的高需求,航运公司的经营者面临时间和能力的限制,使得有必要使用其他运输方式,甚至跳过港口调用和留下货物,为了避免延误。

存在大量的研究计划与班轮运输相关的问题;本研究的主要部分是致力于战略或战术问题。在班轮运输战略规划最佳的舰队和航线网络的设计进行了论述;见,例如,(3]。战术规划包括作业船舶航线(4和对货物的路由路径选择5]。在班轮运输作业计划问题的文献很少。这只是一个期望,班轮运输的本质表明同样的安排应遵循每一个旅程,这安排发表,有效期为一段相对较长的时间(几个月或几年)进入未来。一个路由和调度问题的分类方案在班轮运输建议(6];这项工作显然也反映了战略和战术规划的主导地位在班轮运输问题。

提出了问题,另一方面,显然是操作,处理每一个旅行的计划。出版计划或时间表告诉原产地当船离开港口,港口可以访问,和在时间,沿途,它告诉船什么时候到达目的港。对于大多数航运公司,发布的时间表是这样的,所有端口,或者可以访问每一个旅行。这并非如此在当前的问题。时间表包含太多端口允许所有人访问了在每一个旅程。这是因为季节的需求,在需求较低的时期,只有一个子集的港口有对运输的需求。

决策者在班轮运输经常面临一些问题,如波动需求创造能力问题和延迟由于拥挤的港口、罢工、恶劣天气。为工业客户,这种干扰可能造成严重后果,因为货物在运输过程中越来越多地用作管道在全球供应链库存缓冲保存至少降低成本。目前,常见的解决问题的办法是引入松弛船期表,导致一个更长的管道为客户,并要求更多的船只相同的能力;参见[7]。另一种可能灵活的班轮运输,使用更严格的时间表,但灵活性的机会跳过一些港口调用和留下一些货物。的一些港口跳过可能仍然是通过服务访问端口使用各种预处理或posttransportation(即模式。支线服务驳船和卡车),考虑到船舶容量允许。

联合运输”反映了至少两种传输模式的结合在一个单一的传递链,不改变容器的商品”(8,400页),这个领域的研究在过去的十年中受到更多的关注。文献[8)操作概述研究模型和建模问题需要处理;(9)提出了规划决策的概述和分类方案相关的规划问题。一些研究人员强调需要更多的专注于联合运输。

本文重点是选择哪些端口的问题经过什么货物前或posttransport公路运输与高需求期,由于对时间的限制和船的能力。类似的决策问题报告使用灵活的路由从其他班轮运输服务由陆路运输策略,包括临时停靠的变化序列,或跳过的港口7]。这种类型的决策问题也与流浪汉航运问题,分享一些属性,在这两种情况下,它必须决定哪些端口访问,货物运输,在顺序选择端口应该访问。许多航运公司流浪汉市场操作的混合合同货物必须装船,以及可选的货物的船公司可以盈利的方式如果他们能这样做。船舰队调度决策支持系统,主要针对流浪汉航运、描述(10]。

相同类型的决策也必须在一些变异的车辆路径问题(VRP)。VRP的标准版本,必须找到最好的路线的车辆为一组客户服务与给定的需求。VRP问题研究;概述中可以找到模型和解决方案的方法(11]。一些常见的属性不定期航运和这里讨论的问题都还发现在VRP的变体。的开放式车辆路径问题是一个蚁群,车辆不必返回到仓库;这个属性在海上路由也常见,船是很少需要返回仓库。开放的VRP是通过精确的解决方法和启发式;见,例如,(12,13]。的越野识途比赛的问题是一个路由的问题,网络中节点具有与其相关联的奖品或利润;目标是访问节点的一个子集,收集尽可能多的利润总额,受约束(14]。这也经常被观察到在船路由,必须选择要访问的节点并跳过只要时间和/或能力的限制使它不可能满足所有的需求。

我们声称此处提出的问题,就像许多其他真实的交通规划问题,不能处理标准和著名的模型和解决方案方法的文献。在大多数情况下,一个工业所面临的一个具体的规划问题演员相当复杂,是几种问题类型的组合。这意味着手工计划非常耗时;此外,它不可能总是会找到一个很好的解决方案不支持从一个自动规划系统。从历史上看,海事部门已经传统手工规划基于经验(15],但越来越各种可用的模型,解决方法,为规划和软件系统,这可能会改变。

我们已经开发出一种灵活的班轮运输问题的数学模型。在许多情况下,不可能提前知道如果一个精确的方法可以做这项工作,或如果一个启发式方法是必要的。我们试图回答这个问题通过计算测试发现大约有多大问题实例可以解决最优使用标准软件。

本文的其余部分组织如下。更详细地提出了问题,介绍了一个数学模型,在部分2。计算测试中描述的部分3,其次是未来研究的结论和建议部分4。

2。问题定义

在本节中,我们首先描述实际问题提供的基础问题描述。然后我们描述问题更正式,紧随其后的是一个数学模型的制定和解释。

2.1。示例应用程序

灵活的班轮运输问题模型,解决了在本文基于一个实际的应用程序托盘化冷冻鱼从俄罗斯和挪威运送至终端在挪威,荷兰和英国。冷藏船是主要的交通方式,但公路运输也在需要的时候使用。冷藏船的时间表,在某种程度上,被视为一个班轮运输计划,许多港口提前电话是固定的,和定期重复的路线。另一方面,许多港口往往不是访问由于低需求,和一个小的地理区域内港口的访问顺序可能不同于一次。在这种情况下这意味着规划问题可以被视为一种变体的班轮运输与多式联运和操作路由决策方面的补充道。这里给出的决策问题发生在鱼的运输在东大西洋和巴伦支海国际渔船舰队。由于这段漫长的距离到达市场,冻结在海上的鱼是守恒的。相当比例的总抓着陆和托盘化终端长挪威海岸接壤的这些丰富的水域。大多数的终端都很小,没有基础设施容器处理。托盘化鱼冷藏船或通过卡车运送至终端在西方挪威、荷兰、或英国,作为原料在挪威或欧盟海产品加工业或集装箱化和进一步运输支线船只和洲际集装箱运营商降低劳动力成本处理器在远东。 Figure1显示了一个示例的路线从摩尔曼斯克,参观一些终端在挪威和荷兰,最后到达格里姆斯比在英国。应该注意的是,路线只有八个停止不是一个现实的情况;只是这里为了便于说明。还要注意,我们使用术语节点,港口,和终端互换;在此设置他们的意思是相同的。

一个主要演员在这个运输链运营着一个航运公司使用三个2500 dwt冷藏船服务路线挪威海岸港口在欧盟每周的日程安排。渔业是高度季节性,所以运输的要求。在旺季,船舶在两个同时瓶颈。一个瓶颈是载货能力,另一个是时间,有50多个终端或其他地方产生运费,每个额外的停止服用额外的时间。船时间利用率接近100%,计划变得更加容易受到延误,可能会导致额外的成本高,如果船没有时间窗口进入欧盟港口或错过时间窗口提供托盘为填料容器在中间终端进一步运输支线船只洲际集装箱港口。

提高冷藏船操作的方法之一是节省时间的数量减少终端访问,替换一些pre -终端站和posttransportation使用卡车。这也可以缓解产能问题,pretransporting船的货物到码头卸货,因此释放能力。

选择的问题,终端经过什么货物前或posttransport变化去旅行,因为几个因素包括迁徙运动导致渔业资源的地理位置不稳定的需求模式和可能太复杂的解决最优的临时手工方法目前用于冷藏运输公司。决策支持基于数学模型可能会因此是一个好主意从实用的观点。如果沿线的所有端口的需求合理程度的确定原产地船离开港口之前,摩尔曼斯克在这种特殊情况下,可以用给定的需求数据和运行模型得到一个建议路线计划作为输出。重要的是要注意,解算器的输出应该被视为一个建议;人类的决策者应该审查建议的计划,做出最后的决定。在本文的工作中,我们假设需求是提前知道。如果是高度不确定的需求,必须把这个问题看作是一个随机优化问题。其他技术建模和解决问题就必须考虑,这是超出了本文的范围。

2.2。数学模型

我们现在联合运输问题的数学模型在前面的部分;总结了使用的符号符号结尾部分。增加可读性,我们使用书法字母集,数据的大写字母,小写字母的变量。

让节点的集合或终端,是开始节点(摩尔曼斯克在这种特殊情况下)和结束节点(格里姆斯比在本例中)。需要访问的一些终端;这些构成了设置的所需的节点。

五种链接或被认为在网络连接。限制变量的模型的大小和数量,我们不定义链接(因此不变量在这些链接),从来没有被使用,例如,长链接前往北方。是需求的链接代表求解算法,可能会有商品需求从原点运往目的地。两种类型的需求可能与每个相关需求联系;代表强制性的要求,要求必须满足,例如,因为货物被遗留在以前的旅行,或者因为一个或两个终端被认为是特别重要的航运公司的客户。第二种类型的需求可选的需求 ,代表要求可能留下,如果有必要,由于时间限制和/或能力。客户支付每吨/托盘的冷冻鱼运来。

链接设置,被称为海的链接,包含所有节点对冷藏船可能直接从原产地到目的地旅行。所需的任何链接经过一个由大量节点距离可以排除,因为船已经停止在所有节点。

链接设置包含路连接,这是链接,公路运输的航运公司可能使用时间和能力的限制使得有必要。邻近区域内的终端,这些链接可以用来运输货物不使用冷藏船。去年的链接集组合两个海洋和公路运输;是一组pretransport链接,卡车用于旅行的第一站和冷藏船用于其余的腿。同样,中的链接是posttransport链接,卡车用于最后一站。

链接都给海面上的距离(链接()和道路);给出在不同单位的距离(航海英里和公里);此外,实际的海运和公路之间距离可能不同很明显两个给定的终端。作为一个例子,两个终端位于两端的峡湾可能接近海的距离,但长期而言,道路距离如果没有渡轮航线或桥附近。另一方面,两边各有一个终端的地峡近邻的道路,而海运可能会有很大的距离。

我们遵循的运输成本模型的方法(16),只考虑燃料成本船每海里;这是因为总时间和旅行的人员数量是固定的,所以这些费用不会依赖于路由。模型还可以包括速度优化;见,例如,(17]。燃料成本将由立方近似函数,和船的速度将一个变量而不是参数,可能为每个单独的航行的腿。我们选择不要在这个方向,扩展模型的模型允许一些灵活性也当最大巡航速度的速度是固定的。每当有松弛的时间计划,船长可能减缓在海上或在港口等待。公路运输,我们假设一个固定的成本雇佣一辆卡车的成本每公里操作卡车和成本每吨装卸。我们假设没有道路运输任务需要不止一个卡车;这是根据来自运输经营者的信息。

所需的时间访问终端分为一个固定的时间停靠;这被认为是相同的所有终端。此外,处理时间每吨货物的装载/卸载终端添加;处理时间取决于设备和其他终端的特性。

的一些终端可能有一个时间窗口的最后期限时,容器必须卸载完成。这是因为一些负载的冷冻鱼塞进容器和转移到一个集装箱支线船舶与一个固定的起飞时间。此外,有两个时间窗口在最后终端因为船需要到达在格里姆斯比潮流是足够高的。

我们需要几套变量代表的决定为每个冷藏船的旅行。是货物的总量(吨)需求链接一起发货吗,通过船运输数量和数量由卡车运输。大量的货物运输在预处理和postlinks等于和,分别。冷藏船机上的负载,当它离开码头等于。对于每一个终端,变量,,代表到达时间,在港口时间,分别与起飞时间。

二进制变量指标跟踪的实际船舶采取的路线和道路使用的链接是卡车。我们使用表示,如果直接从节点冷藏船旅行到节点;是用来表示如果一条链接使用的卡车。最后,我们使用变量表明如果pretransport链接通过来使用;以同样的方式用于posttransport链接吗通过来。

2.3。模型公式

在本节中,我们提出的模型一起制定的解释和评论: 受

目标函数(1)最大化利润,计算收入减去运输成本的总和。第一项是收入的总和收集来自客户,第二项是所有海腿航行成本。剩下的三方面占公路运输与pretransport, posttransport,和“纯”道路运输。

约束集(2)和(3)确保出货数量之间的任何一对终端至少是强制需求,最多的和强制性的和可选的需求。约束(4)和(5)计算海运和卡车。在第一组中,所有链接除了路链接是;路链接处理(5)。所有链接,海运数量=运输总量-数量通过公路运输。道路运输可能前或posttransport的距离变量的一部分和分别,或者它可能是道路运输所有的从起点到终点的途径。

约束集(6),(7)和(8)确保所有二进制决策变量表明运输一个给定的路上,前置或posttransport链接,设置为1时所使用的链接。在相同的方式,约束(9)和(10)确保容器访问所有终端商品在哪里拿起或交付。

负载时船离开每个设定的终端约束集(11),(12)和(13)。方程(11)确保负载当离开第一个终端等于总数量从摩尔曼斯克运来,(12)确保容器不超载,(13)计算负载离开任何终端时除了第一。这个词是用来约束有效链接没有乘坐这艘船。

约束(14)和(15)处理容器的路由。根据(14),船舶必须离开开始节点和所有需要的节点,和(15)确保所有节点,除了第一个和最后一个,船已经到达和离开相同数量的时间。在一起,这两个约束集导致船的路线离开摩尔曼斯克,访问一些终端,最终在格里姆斯比。

约束集(16)计算到达时间为每个访问终端除了开始节点。到达时间将大于或等于起飞时间前终端+终端之间的旅行时间。再一次,这个词用于取消任何链接不习惯的约束。在(17在每个终端),港口时间是固定的时间的总和计算加上装卸船舶所需的时间。注意,我们允许一些松弛或等待时间之间的终端(减速)和在每个终端(等待)。然后计算出发的时间(18)。约束(19)确保船总是让一个终端,和(20.)和(21)处理到达时间限制将在格里姆斯比潮流。最后,给出了约束变量域(22)通过(29日)。

3所示。计算实验

这里描述的计算实验有两个目的。一是检查模型是否正确对本文给出的问题描述,另一个是找出大约多大实例可以解决最优标准优化软件包。MIP模型提出了部分2.2在Pyomo编码,解决与Gurobi 6.0.0 2.7 GHz电脑8 GB的RAM。

3.1。测试数据

航行的距离来自日志数据从导航系统下载的冷藏船,船的位置,速度,和课程每分钟自冷藏船航行两年前推出。货物跟踪数据被用来确定货物装卸参数在每个终端。更详细的描述数据的推导过程可以发现在18]。

路的距离计算道路交通(使用一个基于web的旅游计划19]。成本数据是在最近的一项研究发现在运输和物流成本模型16]。成本模型包括冷藏船和termo-trucks,让时间和距离依赖成本的交通工具除了装卸成本每吨每批以及港口费用。很不幸,尽管我们无法获得真实世界的数据,我们已经能够构造一组现实在下一小节中所描述的测试实例。

3.2。问题实例

我们使用的16个问题实例四个不同的尺寸在我们的实验。为每个实例的大小,我们组装一个实例的参数值对需求,船的速度,和每个端口调用所需时间根据可用的实际数据,除了选择这样少量的商品的需求必须留下由于容器容量限制。每组的三个实例是基于第一个;有更高的需求,以迫使模型留下更多的货物,在未来我们减少船的速度,这样时间就变成了一个瓶颈,并在过去的实例我们有高需求和低速度,这意味着我们面临时间和能力的问题。最小的有十个实例终端需求,和更大的实例有16个,20和25个终端,分别。

3.3。结果

次表中列出的解决方案1。列标题的“基本”、“时间”,“帽”和“TimeCap”指的是实例特征描述的部分3所示。2。

十的实例终端都在约0.1秒内解决;16终端从15到80秒才找到一个最佳的解决方案。实例与船的速度和减少需求增加(“TimeCap”)是16个终端中最难的实例。减少的速度使我们有必要对预处理和posttransport使用卡车,和一些需求留下是因为船容量限制。在图2时,我们可以看到一个典型的情况下时间和容量约束:奥勒松地区的一些终端是由卡车的,它们之间的距离很短。直线在海上指示船的路线,和线道路指示后,卡车路线。

尽管时间增加解决的六个终端添加时,这个尺寸仍然是很容易处理的。正如所料,解决时间继续增加20终端当问题规模的增加而增加。现在花了20秒解决“基本”实例;三个约束实例需要10至16分钟来解决。最后,我们设法解决只有25终端的两个实例在不到10小时;另外两个实例之间需要3 - 6天的时间的解决方案。

20终端实例代表一个现实的问题大小对于我们的示例应用程序,但偶尔多达25终端都包含在一个旅程。这意味着,对于这个特殊的航运公司,我们精确解的方法可能会遇到问题在旺季,因此启发式解法应该被视为如果船运公司决定实现一个决策支持系统。以类似的方式对许多其他航运公司操作,20站超过他们通常在一个旅游,从而为旅游规划最优解可在合理的时间。

4所示。结论和未来的工作

本文提出了一种结合海/公路运输,公路运输问题是用来缓解班轮运输路线由于能力和时间的限制。相关决策问题的数学模型提出了与中小型问题实例的最优解。

未来的研究在这个问题上包括模型的进一步发展,以确保所有现实问题的重要方面。需要更多的工作来找出最优解可以找到更大的实例和如果启发式解法需要真实的实例。

符号:输入数据用于模型

	节点/终端/端口
	所需的节点
:	需求的链接
:	海的链接
:	路连接
:	Pretransport链接
:	Posttransport链接
,:	强制性的商品的需求数量(吨)需要发货来
,:	可选的商品的需求数量(吨),可能从来
,:	海的距离来在海里(海里)
,:	路的距离来在千米(公里)
,:	价格每吨货物的运输来
:	每海里的海上运输成本
:	每公里的公路运输成本
:	公路运输装卸成本每吨
	固定成本/道路运输卡车
	船的速度
	船的能力
:	最新起飞时间节点
:	最早到达时间结束节点
:	最新的到达时间结束节点
	很大的数字。

在模型中使用符号:变量

连续变量

, :	货物从来
,:	货物从所感动来
,:	货物从所感动来
,:	货物运输的道路来然后通过海运来(pretransport路)
,:	海上货物运输来然后通过公路来(posttransport路)
:	当离开终端负载在船上
:	到达时间在终端
:	港时间在终端
:	从终端出发时间

二元变量

, :	1如果船直接从旅行来,否则
,:	1如果一个卡车直接从旅行来,否则
:	1如果pretransport链接(),否则
:	1如果posttransport链接(),否则。

利益冲突

作者宣称没有利益冲突有关的出版。

承认

这里提出的问题描述和数据工作是基于Ola后期的博士工作Bø莫尔德大学2009 - 2012年期间。

引用

1. 联合国贸易和发展会议”,对海上运输,“技术代表、联合国贸易与发展会议,2014。视图:谷歌学术搜索
2. m·克里斯琴森k . Fagerholt b Nygreen, d . Ronen”船在新世纪路由和调度。”欧洲运筹学杂志》上,卷228,不。3、467 - 483年,2013页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
3. k . Fagerholt“最佳一艘舰队设计路由问题,”在运筹学国际交易》第六卷,没有。5,453 - 464年,1999页。视图:出版商的网站|谷歌学术搜索
4. b·j·鲍威尔和a . n . Perakis”舰队部署优化班轮运输:一个整数规划模型,”海事政策与管理,24卷,不。2、183 - 192年,1997页。视图:出版商的网站|谷歌学术搜索
5. r·阿加瓦尔和O。水系,“船舶调度和网络设计路由在班轮运输中,货物”交通科学,42卷,不。2、175 - 196年,2008页。视图:出版商的网站|谷歌学术搜索
6. k . h . Kjeldsen”分类班轮运输船舶路由和调度问题,“有限公司卷,49号2、139 - 152年,2011页。视图:出版商的网站|谷歌学术搜索
7. t . e . Notteboom“时间因素在班轮运输服务,”海洋经济和物流,8卷,不。1,第19 - 39页中,2006。视图:出版商的网站|谷歌学术搜索
8. c . Macharis和y . m . Bontekoning”的机会或联运货物运输研究:回顾,“欧洲运筹学杂志》上,卷153,不。2、400 - 416年,2004页。视图:出版商的网站|谷歌学术搜索
9. a . Caris c . Macharis g·k·詹森,“计划联运货物运输中存在的问题:成就和前景,”交通规划和技术没有,卷。31日。3、277 - 302年,2008页。视图:出版商的网站|谷歌学术搜索
10. k . Fagerholt”船舰队scheduling-experience计算机决策支持系统,未来的研究,“决策支持系统,37卷,不。1、形成反差,2004页。视图:出版商的网站|谷歌学术搜索
11. g . Laporte“五十年的车辆路径”,交通科学,43卷,不。4、408 - 416年,2009页。视图:出版商的网站|谷歌学术搜索
12. A·n·拉提佛、j . Lysgaard和r·w·Eglese”branch-and-cut算法对生产开放式车辆路径问题,“运筹学学会》杂志上,卷。58岁的没有。12日,第1651 - 1642页,2007年。视图:出版商的网站|谷歌学术搜索
13. Derigs和英国路透社,“一个简单、高效的禁忌搜索的启发式求解开放式车辆路径问题,“运筹学学会》杂志上,60卷,不。12日,第1669 - 1658页,2009年。视图:出版商的网站|谷歌学术搜索
14. 体能训练时m . Fischetti这样j·j·萨拉查冈萨雷斯,p .托斯”通过branch-and-cut解决定向问题,”通知杂志上计算,10卷,不。2、133 - 148年,1998页。视图:出版商的网站|谷歌学术搜索|MathSciNet
15. k . Fagerholt”,设计最佳的航线班轮运输问题,”海事政策与管理没有,卷。31日。4、259 - 268年,2004页。视图:出版商的网站|谷歌学术搜索
16. s e . Grønland“货运和物流成本模型,”技术。众议员1127/2011,运输经济学研究所奥斯陆,挪威,2011。视图:谷歌学术搜索
17. 即Norstad、k . Fagerholt和g . Laporte”不定期船与速度优化路由和调度,“交通研究C部分,19卷,不。5,853 - 865年,2011页。视图:出版商的网站|谷歌学术搜索
18. o . Bø”,反对的可能性:实现商品跟踪网络中的独立的角度,”第23届NOFOMA年会学报》上,2011年。视图:谷歌学术搜索
19. http://kart.gulesider.no/veibeskrivelse/。

版权

版权©2016 Johan Oppen。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。