（纺织材料与纺织品设计专业论文）多种运输工具不同运载量寻找最优路径算法的研究[纺织材料与纺织品设计专业优秀论文].pdf

多种运输工具不同运载量寻找最优路径算法的研究 摘要 本文目的是在考虑在多种运输工具和不同运载量的网络 下，以单位质量运费最低为目标的最优路径的选择问题。 通过将实际问题建模成有向图。图中“点”表示物理地 点，inc0terms 和运输工具三个信息的结合。图中“边”表 示物流三种不同报价：海运报价，陆运报价和船代报价。考 虑不同“点”上的不同运载工具对于运载量的约束，以所运 货物的单位质量运载价格最低为目标，寻找最优路径。由于 考虑不同运输工具的不同运载量情况，因此，所构有向图中 每一条边的权重为变量，从而不能通过经典的d ijkst r a 算 法计算出最优路径。 寻找最优路径的方法是建立在经典方法d ijks t r a 算法 和m s 算法基础上，考虑到不同运输工具的最大运载量的约 束条件和物流报价中三种不同项目单位的报价，提出一个新 的算法。考虑到目标函数的分段区间非递增的性质，在目标 函数解集中不断缩小解集范围，提出“可接受解集和“最 优 解集。且通过理论证明，求得全局最优解有且存在于 “最优解集中。本文以为代码的形式，将新算法的每个步 骤都写出，并详细介绍了每个步骤地具体作用和功能。 计算机模拟结果显示，新算法在考虑运输工具运载量的 情况下能够精确计算出最优路径。且该结果明显区别于传统 的经典算法。 本文将理论研究与实际应用相结合，设计出一套应用软 件。该软件结合数据库技术和网络技术，设计出非常方便易 用的用户操作界面。且通过整理出的“基本项目”与 inc0te r ms 的相互对应关系，能够最大限度上的提高使用者 使用的效率，在输入数据的过程中自动产生所对应的 in co te r m s ，从而节约了用户的数据输入时间。且通过 “m a p pin g ”功能和对e x ce1 软件的支持，用户使用的方便 性和软件的通用型得到极大得提高。 该应用软件将本文所设计的算法融入其中，考虑物流运 用中的具体约束问题。从最终的计算机应用软件的“模拟” 结果中可以看出，该软件成功的通过算法将不同运载量的最 大运输能力考虑进去，遵循i n coterms 的实际应用规则能有 效地寻找出全局最优解。 通过在d e v c o t 公司的实际应用的效果可以看出，该软 件能满足中小企业物流部门对于数据管理、搜索的需求。 关键字最优路径，d ijkst r a 算法，m s 算法，运载量， 数据库技术 s t u d y o no p t i m u mp a t ha l g o r i t h m f o r t h e m u l t i p l et r a n s p o r t sa n dm u l i t p l el o a d i n g c a p a c i t e ss i t u a t l o n a bs t r u c t t h eo b j e c to ft h i sr e p o r ti st or e s o l v et h eo p t i m u mp a t hp r o b l e mt a k i n g a c c o u n to ft h el o w e s tt r a n s p o r tp r i c ep e ru n i ti nt h en e t w o r ko fm u l t i p l e t r a n s p o r tv e h i c l e sa n dm u l t i p l el o a d i n gc a p a c i t i e s t h er e a lp r o b l e mi sm o d e l e di n t oad i r e c t i o ng r a p h t h ev e r t e xo ft h e d i r e c t i o ng r a p hr e p r e s e n t st h ei n t e g r a t i o no fg e o g r a p h i cp l a c e ，i n c o t e r m sa n d t r a n s p o r tv e h i c l e t h ea r co ft h ed i r e c t i o ng r a p hr e p r e s e n t st h et h r e ed i f f e r e n t l o g i s t i cq u o t a t i o n s ：m a r i t i m e ，t e r r e s t r i a la n dt r a n s i tq u o t a t i o n i nc o n s i d e r a t i o n o ft h e l o a d i n gc a p a c i t yc o n s t r a i n tf r o mt h ed i f f e r e n tt r a n s p o r tt o o l si nt h e d i f f e r e n tv e r t i c e s ，a no p t i m u mp a t hi sf o u n da st h ep r i c eo ft h el o w e s tt o t a l t r a n s p o r tp r i c ef o rt h eu n i tt r a n s p o r t e dg o o d s d u et o t h ec o n s i d e r a t i o no ft h e d i f f e r e n tl o a d i n gc a p a c i t i e so ft h e d i f f e r e n tt r a n s p o r tv e h i c l e s ，t h ew e i g h to f e a c ha r ci nt h eg r a p hi sav a r i a b l e h e n c e t h ec l a s s i c a la l g o r i t h ma sd i j k s t r a a l g o r i t h mc a nn o tb e u s e dt or e s o l v et h i so p t i m u mp a t h an e wa l g o r i t h mt os o l v eo u rp r o b l e mi sb a s e du p o nt h ed i j k s t r a a l g o r i t h m a n dm sa l g o r i t h m t a k i n g a c c o u n to ft h ed i f f e r e n t l o a d i n g c a p a c i t i e sc o n s t r a i n ta n dt h et h r e ed i f f e r e n tl o g i s t i c a lq u o t a t i o n s d u et ot h e p r o g r e s s i v ed e c r e a s i n gp r o p e r t yo f t h eo b j e c t i v ef u n c t i o n ，t h es o l u t i o nd o m a i n i sr e d u c e ds t a g eb ys t a g e ，r e s u l t i n gi nt h e “a c c e p t a b l es o l u t i o ns e t a n d o p t i m u ms o l u t i o ns e t ”a n dt h r o u g ht h et h e o r e t i c a lp r o o f , t h e r ei so n ea n d o n l yo n eg l o b a lo p t i m u ms o l u t i o ni nt h e o p t i m u ms o l u t i o ns e t ”t h en e w a l g o r i t h mi sw r i t t e ni nt h ef o r mo fp s e u d oc o d ea n dt h ee x p l i c a t i o no fe v e r y c l a u s ei sg i v e n t h ec o m p u t a t i o n a ls i m u l a t i o ns h o w st h a tt h en e wa l g o r i t h mt a k e s a c c o u n to ft h el o a d i n gc a p a c i t yc o n s t r a i n ta n dg i v e st h ep r e c i s es o l u t i o n t h i s r e s u l ti st o t a l l yd i f f e r e n tf r o mt h eo n eo ft h ec l a s s i c a la l g o r i t h m i nv i e wo ft h ec o m b i n a t i o no ft h et h e o r e t i c a lr e s e a r c hw i t ht h ei n d u s t r i a l a p p l i c a t i o n ，as e to f s o f t w a r ei sc r e a t e d t h i ss o f t w a r eh a saf r i e n d l yi n t e r f a c e i n c l u d i n gt h ed a t a b a s ea n dn e t w o r kt e c h n o l o g y b yt h em u t u a lc o r r e s p o n d i n g r e l a t i o nb e t w e e nt h ep o s ta n di n c o t e r m sw h i c hi sw o r k e do u ti nt h i sr e p o r t ， t h i ss o f t w a r ec a na u g m e n tt h ee f f i c i e n c yo ft h ed a t ai n p u tp r o c e s s m e a n w h i l e ， w i t ht h eh e l po ft h e “m a p p i n g ”f u n c t i o n ，t h eu s e rc a nu s et h ee x c e l ，t h e f a c i l i t ya n dc o m m o n a l i t yo f t h es o f t w a r eh a sb e e nh u g e l yi n c r e a s e d t h i ss o f t w a r ei n t e g r a t e st h ea l g o r i t h mw h i c hh a sb e e nc r e a t e di nt h i s r e p o r t f r o mt h er e s u l to ft h ec o m p u t es i m u l a t i o n ，t h el o a d i n gc a p a c i t y c o n s t r a i n th a sb e e ns u c c e s s f u l l yt a k e ni n t oa c c o u n ta n dt h eg l o b a lo p t i m u m s o l u t i o nh a s b e e n f o u n dw h e nf o l l o w i n gt h e a c t u a l a p p l i c a t i o no ft h e i n c o t e r m sr u l e f r o mt h ea c t u a la p p l i c a t i o nb yt h ec o m p a n yd e v c o t ，t h i ss o f t w a r ec a n s a t i s f yt h ed e m a n d so ft h el o g i s t i cd e p a r t m e n ti nt h es m a l la n dm e d i u ms c a l e e n t e r p r i s ei nt h ea s p e c to ft h ed a t am a n a g e m e n ta n dd a t am i n i n g k e yw o r d s o p t i m a lp a t h ，d i j k s t r aa l g o r i t h m ，m sa l g o r i t h m ，l o a d i n g c a p a c i t y ，d a t a b a s et e c h n o l o g y 图片目录 图i ：例l 中两条不同的路径5 图2 ：例4 中物流运输路线1 3 图3 ：最大运载量的概念2 l 图4 ：例6 不同路径上最大运载量2 2 图5 ：路径s 的单位质量价格曲线和其上下界2 8 图6 ：d i j k s t r a 算法：3 0 图7 ：m s 算法( k = 5 ) 3 3 图8 ：当变量q 为常数时，函数f ( w ) = c e i l ( w q ) 的曲线图3 7 图9 ：全局最优解和各解集之间的关系3 9 图l o ：例7 中，四条路径和其上下界的函数曲线4 0 图l l ：算法框架图4 l 图l2 ：计算机模拟结果4 7 图1 3 ：计算机模拟结果统计曲线图5 2 图1 4 ：a n o v a 分析结果l 5 2 图l5 ：a n o v a 分析结果2 5 3 图16 ：图形化日期输入界面：6 l 图l7 ：“m a p p i n g ”功能界面6 4 图l8 ：e x c e l 中的i n f o 页面6 6 图l9 ：e x c e l 中的d a t a 页面6 6 图2 0 ：构建有向图的过程6 7 图21 ：快速模拟6 9 图2 2 ：完全模拟6 9 图2 3 ：“完全模拟”计算结果7 0 表格目录 表l ：例l 中各顶点的最大载货量5 表2 ：例1 中各路径的相对费用5 表3 ：例l 中各路径的绝对费用6 表4 ：例l 中路径的实际绝对费用一7 表5 ：例4 中物流运输详细报价1 4 表6 ：l n c o t e r m s 介绍1 6 表7 ：基本项目介绍。1 7 表8 ：基本项目与l n c o t e r m s 之间对应关系1 8 表9 ：例5 中基本项目具体费用和单位( 1 ) 1 9 表1 0 ：例5 中基本项目具体费用和单位( 2 ) 2 0 表l l ：例6 中不同顶点的最大运载量2 2 表1 2 ：2 4 组计算机模拟实验的参数4 9 表1 3 ：计算机模拟试验结果5 1 表1 4 ：“i n f o ”页面6 5 表i5 ：“d a t a ”页面6 5 0 多种运输t 具小问运载量jj 找最优路径算法的研究 附件一： 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师 的指导下，独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰 写，我对所写的内容负责，并完全意识到本声明的法律结果由本人承担。 学位论文作者签名 同期：了年朔 0 多种运输t 具小运载量、j 找最优路径算法的研究 附件二： 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权东华大学 可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 不保密阅。 一躲镧7 l j ! 要双、 日期：少鑫年弓月5 n 一即臭毫 同期：b 。莎年；月角 第一章弓l 言。 第一章引言弟一旱5i = 纺织工业是我国的基础工业，其生产需要大量的天然原材料，例 如：棉花，羊毛等。在天然原材料的国际贸易中，运费往往起着重要 的作用。如何能在众多的运输报价中找出一条价格最低的路径，是摆 在每一个纺织原料销售物流人员面前的一道难题。 对于纺织品天然原材料的运输，有其独特性。天然原材料的产地 有限，高品质的原材料的产地分布在世界各国，因此原材料的运输通 常情况下是跨大陆。这种长距离的运输往往需要涉及多种运输工具。 因此，不可避免的会产生运输工具之间的转换。例如，通过卡车将原 材料运到码头，然后通过远洋船再将原材料到另一个大陆的码头。最 后，通过火车运抵目的地。跨洋运输所需一定的时间，而原材料的交 易往往又是期货交易。因此在选择最理想的运输路径时，运输时间往 往不是一个重要的评判标准。 相反，运输的价格是选择最优运输路径的一个重要的参考指标。 运输费用在原材料交易成本中所占的比重变化巨大，对于不同的运输 路径，所花费的运费有可能存在巨大的差异。同时对于原材料的运 输，所要运输货物的总质量对于所运商品的单位质量所承担的运费有 很大的影响。 因此，对于纺织原材料的最优路径选择问题，运输的费用往往是 最优路选择的重要评判标准。 1 论文主题 本文的主题从实际出发，在一个全球范围内的复杂交通网络系统 中，挑选合适的路径来满足我们的要求。本文的主题为：物流系统中 考虑不同运输方式的最大运载量情况下，以所运货物的单位质量运费 最低为目标的最优路径选择问题。 2一2 目的 i i 2 目的 本论文有两个目的。 目的一：从理论上将问题抽象为数学形式，在考虑运输工具的单 位装载量的前提下，以优化单位质量的运输价格为目标，从不同的运 输线路和运输方式中，优化组合，挑选出运费最低的运输线路。 为此，通过数学定义、定理、性质和推导等一系列方法，证明该 问题的解的存在性和确定性，并给出解决问题的算法的具体实现形 式。 目的二：从实际应用角度看，提出一套具体的计算机辅助系统实 现形式，将所设计出的算法融入该系统中，从而帮助广大物流从业人 员解决最优路径选择的实际问题。 我们将编写一个数据库系统用来存储所有的物流交通数据。并且 编辑一套人机界面程序，完成计算机辅助的任务。同时将目标一所提 到的新算法融入到数据库系统中，从而构成一个可用的数据库计算机 辅助系统。 本文的第二章将介绍物流运输过程中所遇到的最优路径选择问 题，并分析问题的特殊性及其求解的难点，并综述一下该问题的发展 经历。第三章则介绍该问题中的所遇到的物流知识，为理论建模做好 铺垫。第四章通过图论的方法将最优路径选择问题进行数学建模，介 绍己存在的解决类似问题的两个经典算法，并通过对于目标函数性质 的分析理论上证明解的存在和确定性。第五章提出解的具体求解方 法，提供并分析算法的伪代码。第六章则通过计算机模拟的方式将新 的算法和经典算法作比较，从而说明新算法的优势。第七章将提供一 个实际应用案例说明算法的可行性。 第_ 审问题的提出 3 曼! ! ! ! 寰1 1 1 | | 1 ! ；一曼蔓曼曼! 曼! ! ! ! ! ! 曼曼 第二章问题的提出 本文的目的之一是设计一个新的算法用来计算出价格最低的最优 路径。这个算法将会考虑运输工具的最大装载量。同时算法也会从实 际应用出发，将 inco te r i n s( in te r n a tio n alco m m e r cia 1 tef t l ls ) 这个国际物流中通用的概念结合起来。新的算法是从最短路 经算法和第k 条最短路径算法中演变而来。在这一章中，我们首先讨 论最短路经问题。然后，提出本文所要解决的问题，并说明当用现存 算法来解决本文中所提出的问题时，现存算法所存在的缺陷。 1 最优路径 在解决与运输相关问题的时候，大多数情况下都是寻找一条在两 点之间价格最低的路径。该问题的本质，就是寻找一条最短路径。比 如说，一个包裹邮递员需要将一个包裹从甲城送往乙城。在两城市之 间没有直接的通路。邮递员需要从甲城出发经过几个不同的城市才能 到达乙城，须规划路线才能将所需经过的路程长度最小化。 最短路径的问题【1i 能够这样被抽象出：给定一个点的集合( 车 站，服务器) ，一个边的集合( 铁路线，网络线) 和一个权重的 集合( 长度，价格，流量) ，寻找到一条路径使其在给定的两点之 间的权重最小。 对于最短路径问题，他的目标函数可以写成如下形式： c ( j ) = m 峨i n c ( s ) ) ( 2 1 ) 在公式( 2 1 ) 。& 。代表所有从a 点到b 点的路径的集合。最短路径 问题的f l 标是在集合中，找到条路经s ，能够最小化总成本 c ( s ) 。这里的总成本c ( s ) 代表了路径上各个段落上权重的总和。每一 个段落( 边) 都被赋予一个值固定的权重。最短路径问题是重要的最 优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如 4 二2 问题的特殊点 曼i i i i i i i i i i i ；一o 曼曼曼曼皇曼曼曼舅皇鼍曼蔓曼曼 管道铺设、线路安排、厂区布局、设备更新等等，而且经常被作为一 个基本工具，用于解决其它的优化问题。 2 问题的特殊点 上节中所提到的问题是属于经典的最短路径问题( c sp p ， c1a ssics h o rtestp a thp r o b1e m ) 。但是，在本文中所遇到的问 题需发生些演变。 定义1 ：假设我们运输x 单位质量的货物，所需的运输费崩之和为 y ，则我们定义y 为相对费用。 定义2 ：假设我们运输x 单位质量的货物，所需的运输费用之和为 j ，则我们定义x y 为绝对费用。 根据最短路径问题我们得知，最短路径问题的目标函数是一个权 重( 距离，成本或者时间) 的总和。这个权重的值对于路径上的任何 一条边都是常量。也就是说，只要给定两点，如果上面存在一条边， 那么这个边上的权重是不受其他因素干扰而固定不变的。只要我们选 中了通过两顶点的一条边，那么这权重值就确定了。 但是，本文后面所提到的目标函数是一个非线性函数。因为即使 我们选择了固定的两点，如果两点间有一条边，其权重也会受到其他 因素的影响。如下公式为本文中所要求的目标函数。 c ( w 事) = m i n ( e ( w ) ) ( 2 2 ) j e s 曲 血s w s 。 在公式( 2 2 ) 中可以看到，我们所要求的最低的成本c j ( w 率) 受到最 优路径s 幸和最优质量w 宰两个因素的影响。我们所要计算的最低成本 c ( w ) 是一个比值。分母为所有商品( 原材料) 的运输费用，它是所有 经过的路段( 边) 上费用的总和。分子为商品的总质量。每一段路经 ( 边) 上的费用，会根据总路径所经过的点的改变而发生改变。其值 第一章可题的提出 5 为个非线性函数值。根据定义1 我们得知，h 桥函数的分母为相对 费片j 。根据定义2 得知目标函数值c ( w ) 为绝对费用。 在章节数学建模中，我们洋细讨论口标函数的建立，并对其 进行分析存此z 前为了能有一个直观的认识，我们将举个简单 的例子来说明单位运输成率这个概念。 倒1 ：假设有商品需要从a 点运往b 点。如图l ，图中一共有五 个顶点和血个囱边( 路段) 。l 当这个图应用到物流系统中时，就 r ，f 以把这五个有向边看作是五个不同的运输报价) 。在此例中，假设 远输的设备青6 为卡车。，表1 列出了每个点上可允许的最大载货量。表 2 列出每一个路段上所要消耗的相对费用即运费的相对价格。求绝 对费用最少的最优路径。 图l ：例1 中两条不同的路径 表l 倒1 中各顶点的最大载货量 i 顶点 bcc d l 最大载货量 2 0 立方吨1 8 立方吨2 0 立方吨1 8 立方吨2 0 立方吨 表2 ；例1 中各路径的相对费用 l路径 li 22 3 i 相对费用 2 0 0 美金1 9 0 美金2 0 0 美金1 9 0 美金1 8 0 美金 i 运输工具 卡生 6 二2 问题的特殊点 曼曼jl一!ii!皇曼!曼!曼曼皇 由表1 和表2 我们可以得出在每段边卜单能质量商晶所消 l 的 费用，其值等于边上的费用除以最大载货量，如表3 。对于每个路段 上的最大载货量，其值等于该路段所连的两个顶点( 起点和终点) 上 的最大载货量中较小的一个。由定义2 可知：二点间运输单位质量商 品所消耗的费用等于路段的相对费用除以路段的最大载货量。( 这里 暗示一个前提，即每个运输单位( 例如卡车) 都最大限度的满额运输 商品。) 由图1 可知：从a 点到b 点，一共有2 条路经( 1 ，2 ，3 ) 和( 1 ，2 ，3 ) 。我们要求从a 点到b 点，寻找绝对费用最低的路 径。 表3 ：例l 中各路径的绝对费用 路径 ll 22 3 最大载货量 ( 立方吨) 2 01 82 0182 0 绝对价格 ( 美金立方吨) 1 0l o 5 61 0l o 5 61 0 如果我们将此问题看作经典最短路径问题，则从a 点到b 点的总 费用为路径所经过的每段路段的绝对费用之和。则路径( 1 ，2 ，3 ) 的总费用为3 0 美金立方吨。而路径( 1 ，2 ，3 ) 的总费用为 3l ，12 美金立方吨。显而易见，此时路段( 1 ，2 ，3 ) 为最优路径。 然而，在实际应用中，如果从a 点到b 点选择路径( 1 ，2 ，3 ) 时， 在路段1 和2 上，卡车的最大运载量只有18 立方吨。因为路段3 对 卡车的最大运载量的规定为1 8 立方吨。而对于所有与路段3 相连的 路段来说，卡车的最大运载量都不能超过18 立方吨。又因为当我们 选择路径( 1 ，2 ，3 ) 的时候，路段1 ，2 与路段3 相连。所以，在路段 l 和2 上，卡车的最大运载量也被限制在18 立方吨以下。因此，针对 从a 点到b 点选择最优路径的情况，每个路段上的最大运载量和绝对 费用应改为如表4 。显而易见，此时的最优路径应为( 1 ，2 ，3 ) ， 其绝对费用总和为3l ，12 美金立方吨。而路径( 1 ，2 ，3 ) 的绝对费 第：章问题的提出7 用总和却有32 ，2 2 美金立方吨。可见，我们不能直接将例1 以经 典最优路径问题来对待。 表4 ：例1 中路径的实际绝对费用 路径 ll 22 3 最大载货量 l81 8l818 2 0 立方吨 ( 立方吨) 绝对价格 1 1 1 l1 0 5 6l1 1 11 0 5 6 l o ( 美金立方吨) 例2 ：我们可以对例l 进行进一步探讨。现假设我们要将货物从 a 点运往d 点。仍由表l 和表2 给出各路段上最大载货量和相对费 用。己知货物总质量为l0 0 立方吨，求最优路径。 如果我们选择路径( 1 ，2 ) ，由表l 知，总共需要5 辆卡车运输货 物。其运输的绝对费用为： ( 2 0 0 + 2 0 0 ) x 5 1 0 0 = 2 0 美金立方吨 ( 2 3 ) 。假设选择路径( 1 ，2 ) 。由表l 知，需要6 辆卡车才能将容纳 l00 立方吨的货物。因此，此时的运输绝对费用变为： ( 2 0 0 + 2 0 0 ) x 5 9 0 = 2 2 2 2 美金立方吨 ( 2 4 ) 由公式( 2 3 ) 和公式( 2 4 ) 可以看出，路径( 1 ，2 ) 为从a 点到d 点 运输l0 0 立方吨货物的最优路径。此时路段l 和2 不与路段3 相连， 此时路段l 和2 的最大载货量不受路段3 的影响。所以，路经( 1 ，2 ) 为最优路径。 由例l 与例2 的比较中可以发现，每一路段的最大载货量受该路 段所在路径上所有路段的最大载货量的影响。从而每一路段上的绝对 费用受该路段所在路径上其他路段的影响。换句话说，每一路段上的 绝肘费用在没有决定该路段属于哪条路径之前，都不是常量。这是本 文所要探讨的问题的一个特殊点。 8二3 问题的难点 曼o i 一：i i i i i ii i i 曼曼! ! ! ! ! 曼 例3 ：假设从例2 再进行变化。所需要运输的货物的质量为9 0 立方吨，则求从a 点到d 点的最优路径。 当选择路径( 1 ，2 ) 时，由表1 可知，仍然需要5 辆卡车运输货 物。其运输的绝对费用为： ( 2 0 0 + 2 0 0 ) ) 5 9 0 = 2 2 2 2 美金立方吨 ( 2 5 ) 而选择路径( 1 ，2 ) 时，由表l 知，只需要5 辆卡车。因此，此 时的运输绝对费用变为： ( 1 9 0 + 1 9 0 ) x 5 9 0 = 2 1 1 l 美金立方吨 ( 2 6 ) 从公式( 2 5 ) 和公式( 2 6 ) 不难看出，在运输9 0 立方吨的商品的 情况下，路径( 1 ，2 ) 是最优路径。 通过例3 不难发现，最终所求的最优路径还与所运货物的总质量 相关，其为问题的第二个特殊点。 3 问题的难点 从问题的第一个特殊点可以看出，对于每同一个路段( 边) ，如 果它所属的路径不同，则它对于某种运输工具的最大载货量也很有可 能发生变化。例如在例l 中，对于路段l ，当其所属路径为( 1 ，2 ， 3 ) 时，其绝对费用( 权重) 为1 1 11 美金立方吨。当其属于路径 ( 1 ，2 ) 时，其绝对费用( 权重) 变为10 美金立方吨。其原因是由 于路段上的最大载货量发生了变化。对于同条路段，既是相对费用 固定不变，绝对费用也会因为其最大载货量的变化而发生改变。由此 可见，我们无法在确定最终路径之前，就确定每个路段( 边) 上的绝 对价格。也就是说，即使给定个路段( 边) ，在不知道其属于哪一 条路经之前，我们无法确定这条边上的绝对费用( 权重) 。 对于经典最优路径问题，每一对固定顶点之间的边，无论其被包 括进哪一条路径，其权重总是固定不变。通过考虑每条边上的权重来 第章问题的提m 9 曼曼! ! 苎! ! 曼曼! ! ! 曼! ! 曼! ! ! 曼曼! ! 曼! 曼! 曼曼! 蔓i ： 1 一一 一一_ i 皂曼曼曼皇曼曼曼! ! 曼曼! 找出最优路径。而对于本文所描述的情况，只有在选中一条路经之 后，才能精确的计算出每条路径上边的权重，从而计算出整条路径的 最终总费用。也就是说，在确定每条边上的权重和找出最优路径之 间，解决问题的步骤的优先级次序问题上与经典最优路径问题产生了 冲突。问题的难点就是在于此。正由于这个优先级次序冲突的存在， 绎典最优路径问题的算法无法直接应用到本文的问题。 另一个难点在于，最终的总费用值还受到所运货物的总质量的影 响。从例2 和例3 的比较中看到，不同质量的货物，对于同一对起 点和终点，其最优路径会不同。如果对一批货物给定一个质量范围， 如何选择最优的质量从而能得到最优的路径和最低费用，也是本文要 讨论的问题。在数学建模章节中可以看到，在总绝对费用和总质 晕之间，存夺一个： f 线性函数关系。 4 文献综述 本文所提出的算法是基于dijkst r a 算法基础之上。 19 5 9 年， dijkst r a 在他的文章f 2 】中第一次提到解决两点之间最优路径的算 法。dijkstr a 算法最简单的实现方法是用一个链表或者数组来存储 所有顶点的集合矿，所以搜索矿中最小元素的运算( extr a ct - min ( 矿) ) 只需要线性搜索y 中的所有元素。假设矿集合的大小为玎，算法的运 行时间既为o f 甩2 ) 。 对于边数为m ( m n 2 ) 的稀疏图来说，我们可以用邻接表来更有 效的实现dijkstr a 算法。同时需要将一个二叉堆或者斐波纳契堆用 作优先队列来寻找最小的顶点( e x t r a ct min ) 。当用到二叉堆的时 候，算法所需的时间为o ( ( 卅+ n ) l o g 以) ，斐波纳契堆1 3 l 能稍微提高一些 性能，让算法运行时间达到o ( 所+ n l o g n ) 。一种新的算法在19 6 2 年由 b e l l m a n 和f o r d 发明，被称为b e ll m a n - f o r d 算法【4 ，”。该算法的 改进之处在于当边的权重有负数的时候，该算法仍然能够找到最优路 径。至此，对于最优路径的算法基本已经成形。其后面所推出的一系 1 0 4 文献综述 i i 一i ： i ； i ii ! 曼曼曼曼曼曼! ! 曼曼曼曼! ! ! 曼! 毫曼! ! 曼鼍曼曼曼! ! 曼! ! ! 曼! 曼! 蔓! ! ! ! 曼曼! ! ! ! 蔓 列新算法都是在以上两个算法的基础之上所提出的。例如现在被广泛 使用的a 术算法【6 1 。其在d ijkst r a 的基础之上再结合进启发式算法的 思想，通过利用已知信息来估计两点间最优路径，从而能够有效的缩 小搜索的范围应用在大型的数据库系统中。或者引入启发式箅法的概 念来求解大范围上的最优路径问题【7 1 。 但上述的算法及其演变出的新算法都只是针对边的权重为固定值 的情况。像本文中所提到的，边的权重随着边所处的路径的不同而发 生变化的情况，无法直接套用以上的算法。为此，我们需要引用另一 个工具：第k 条最短路径算法。m a rtins 教授在1984 年首先提出删除 算法( d e1etio na1g o rith m ) 的概念f 8 i 。该算法的的核心是通过存 有向图中己有的最短路径上删除某条弧，并寻找替换的弧来寻找下。 条可选的最短路径。删除算法实际上是通过在有向图中增加附加节点 和相应的弧来实现的。在这篇文章中，计算复杂度为o ( 砌，1 1 ( 玎。为第 一条最短路径上定点的个数) 。在此算法之后，出现了许多从删除算 法上的改进。 l9 90a ze ved o ，m a d eir a 和m a r tir l s 在论文f 9 1 中阐述了基于删 除算法的原理及方法，并指出了解决此类问题的三类算法，对其中册4 除算法以及基于最优化原理( p r in cip1eo fo ptim a lity ) 的算法进 行了实验比较。19 93 年，a zeved o ，m a deir a ，和m a r tin s 1 0 1 对删 除算法作了进一步的优化，将其计算复杂度减少到o ( 七( 门) l o g 聆) 。 在19 9 8 年，e p pstein 设计出一个e a 算法i l ，其原理区别于删 除算法，该算法的计算复杂度为o ( m + n l o g n + k ) 。l9 9 9 年，又个新 的算法由m a r z a l 发明【”】。m a r z a l 提出了新的算法- 递归枚举算法 ( r e a ， re c u r sivee n u m e r a tio na lg o rith m ) 。论文分别对新的算 法和m a r t i l 3 s 的算法以及e p p s t e i n 的算法( e a ) 进行了详细的实验比 较。 第章问题的提h j 1 1 1 1 1 1 皇曼曼曼曼曼。m 2i i 。曼曼皇曼! 曼曼曼! 曼曼曼量曼曼皇! ! 曼! ! 曼 m artir ls 在他l9 9 9 年一篇文章中13 1 对删除算法进行了改进，提 出了m s 算法。与其之前的删除算法相比，新算法实际上除了数据结 构上的变化外，并没有做实质性的改动。但从实际应用的角度出发进 行了优化。与删除算法相比，新算法更加适合在计算机上编程实现。 m artins 随后又在他的一篇论文l 4 】中改进了m s 算法，并依次详细列 举了对早期的删除算法的逐步改进过程。同样，这次改进也是从数据 结构角度来改进算法效率的。 为了解决本文中所提到的算法问题，仅仅有了d ijk st r a 算法和k 条最短路径算法还不能满足我们的要求。因为这两种算法都没有涉及 到装载量的问题。m a r tin s 在l9 8 4 年的论文中l l5 j 第一次提到运输工 具的装载量的问题。这篇论文以运输费用和装载量的比值作为最终的 优化目标。其核心算法是删除算法与帕累托改进( p a r eto - o p tim a l ) 概念配合使用。在不能直接得出全局最优解的前提下，先找出一个可 行解的域，然后再在可行域中进行比较，从而找出全局最优解。 帕累托改进是由帕累托最优( p a r et oo ptii l i a lit y ) 而来。帕累 托最优也称为帕累托效率( p a r e t oe f f 。icie n cy ) 、帕累托改善，是 博弈论中的重要概念，并且在经济学【】，工程学和社会科学中有着 广泛的应用。，帕累托最优是指资源分配的一种理想状态，假定固有的 - 一群人和可分配的资源，从一种分配状态到另一种状态的变化中，在 没有使任何人境况变坏的前提下，使得至少一个人变得更好，这就是 帕累托改进或帕累托最优化。帕累托最优的状态就是不可能在有更多 的帕累托改进的余地：换句话说，帕累托改进是达到帕累托最优的路 径和方法。 运用帕累托改进的概念，我们能够得到目标函数为二维函数甚至 多维函数时，最短路径的最优解算法。典型的例子就是要寻找一条时 间最短，费用最少的最优路径或者是最大化最小化的问题。这种多目 标函数的问题已经被很多人进行过研究。m a r t ins 17 】在其论文中探讨 了双目标函数的求解问题。m o t e 【18 1 等将帕累托改进与线形规划结 1 2 二4 文献综述 i ii i 合，解决双目标函数的最优路径问题。t u ng 19 】将双目标函数的问题 演化为多目标函数的问题，结合a 木算法和帕累托改进的概念。之后又 有人将帕累托改进与遗传算法相结合，求解多目标规划的问题f2 叫。 以上所有的研究，其核心思想为：在不能直接得到全局最优解的 情况下，得到一个帕累托最优，然后在帕累托最优中，寻找全局最优 解。但是，大多数的研究都只是限于一种交通工具的多目标优化。且 没有考虑货物运输时的最优质量问题。 本文所要涉及的问题是多种交通工具考虑最大装载量的最优路径 选择问题。因此，其中还有一个多种交通工具搭配的情况存在。而历 年来的物流研究中，都没有涉及不同交通工具的运输搭配问题。仅有 的几篇涉及多种运输工具的文章，也都只是在v r p l 21 】问题中或集装箱 的船期调度安排的研究【2 2 】中进行了讨论。都没有在寻找最优路径的问 题上进行过讨论。 同时，在许多针对企业实际应用的e r p 系统中，对于物流模块的 程序开发，也没有将in c o t e r m s 考虑进去。从而不能在具体的实际应 用中帮助客户解决寻找最优路径的问题。 在详细介绍算法的数学模型之前，我们在下一章介绍一些算法中 所涉及的物流知识。 第三章物流术语 存本章节中，我们将仑解释一些物流术的语，这些术语将会被融 人算法体系中，从而增强算法的实际使用价值。对于物流知识的介 绍。有助于理解扁文数学模型的建立和其中各种变量的实际意义。在 详细解释术语之前，我们先提出一个例子，然后通过对这个例子的解 释来说明各个物流基础知识。 倒4假发确定质量的棉花要从科特迪瓦的阿比让 ( a b id j a n ) 港口运送到捷克共和国的诺娃帕卡( n o v ap a k a ) 市。 ( 如图2 ) 在表5 中列出所有的我们所需要的物流运输报价单的详细 信启。从图2 和表5 中可吼看出，货物无法直接从阿比让港口直接 到达诺娃帕卡市，需要经过法国的敦妄1 尔克港口( d u n ke r q ue ) 。对 千表中的专、l k 词扩，我们将对其一一进行解释。 图2 ：例4 中物疏运输路线 1 4三1i n c o t e r m s 概念 粤曼曼曼曼曼曼曼粤! 舅曼蔓曼! 曼! 舅皇! 曼曼曼曼曼! ! 曼! 曼曼! 曼! 曼! ! i ii 曼曼曼曼舅 表5 ：例4 中物流运输详细报价 塌人远 报价 报价公司