（交通运输规划与管理专业论文）VRP在支线船舶调度中的扩展应用研究.pdf

摘要 伴随全球物流一体化的进程的加快和船舶大型化的迅猛发展，支线运输网络 必将蓬勃发展。在支线船舶运输中，船舶的调配和航线的设计是影响航运企业效 益的重要因素，也是节约社会物流成本的关键途径。然而，迄今为止，这类工作 一般都是靠投资经营者的个人经验和主观判断力去完成，现有的为数不多的优化 模型，在支线运输巾港l _ | 数目达到几十个时，其实际应用性也14 分有限。 本文在研究车辆调度问题( v r p ) 的基本理论和研究方法的基础上，根据船 舶支线运输调度的实际情况，设计了支线船舶调度问题( f s r p ) 的混合整数规划 模型。本文所研究设计的支线船舶调度问题模型与传统的v r p 、v r p b 、v r p p d 以及v 砌，t 都有所不同。在支线船舶运输中，既有送货又有取货，且二者有时 同时进行；不存在v r p b 中关于送货优先的约束，也没有类似v r p p d 中对于装卸 顺序的约束，因为在喂给港所装上的货物都要送回枢纽港，船舶在出发和返回枢 纽港时一般均为重载。传统的v r p t w 中，时间窗的约束仅仅针对于顾客而言， 配送中心不存在时间窗约束，但在f s r p 模型中，由于配送中一1 5 , 是干线运输的挂靠 港口，因此对枢纽港的时间窗也是有要求的。 由于支线船舶凋度问题属于n p 一难题，本文在遗传算法的基础卜，结合启发 式算法和免疫遗传算法的思想，设汁了一个新的免疫遗传算法。文章的最后使用 v b 程序对所提出的算法进行了编程计算，通过试验数据的计算，并与文献中其他 算法结果的比较，进一步证明了本文所提出的模型和算法的可行性和高效率性， 对合理设计支线运输航线和调配船舶、节约支线船舶运营成本具有重要重要意义。 关键词：车辆调度；支线船舶调度；免疫遗传算法 t h es h i pr o u t i n gp r o b l e m ：f o r m u l a t i o na n d a l g o r i t h m s b a s e do nv r p s a b s t r a c t w i t ht h ea c c e l e r a t i o no ft h ei n c o r p o r a t i o np r o c e s so f g l o b a ll o g i s t i c sa n dt h es h i p m a c r o s c a l ed e v e l o p i n gt r e n d f e e d e r - l i n en e t w o r k sm u s td e v e l o pl a r g e l yn o wa n di nt h e f u t u r e i nt h ef e e d e r l i n es h i p p i n go p e r a t i o n s ，s h i pr o u t i n gp r o b l e m sh a sp l a y e da n i m p o r t a n tp a r ti nt h ep r o f i to fs h i p p i n gc o m p a n y , a n di st h ec r u c i a lf a c t o ro fs a v i n g l o g i s t i c sc o s to ft h es o c i e t y h o w e v e r , u n t i ln o w , t h i sk i n do fw o r ki sd e c i d e db yt h e e x p e r i e n c ea n dp e r s o n a lj u d g m e n to fa d m i n i s t r a t o r s w h e nt h en u m b e ro ff e e d e rp o r t s m o u n t su p ，t h ee x i t e df o r m u l a t i o na n da l g o r i t h mw o u l ds h o wt h e i rl i m i t a t i o n s b a s e do nt h es t u d yo fc l a s s i c a lv r p sa n dt h ep r a c t i c a li n s t a n c e so ff e e d e r - l i n e r s h i p p i n gr o u g i n gp r o b l e m ，t h e d i s s e r t a t i o n p r o p o s e s an e wm i x e d i n t e g e r p r o g r a m m i n gm o d e l - w h i c hi sd i f f e r e n tf r o mv r p s t h ef s r pi sd i f f e r e n tf r o mt h e v r pw i t hb a c k h a u l s h o w e v e r , t h ev r p bi st r a d i t i o n a l l ya s s u m e dt h a to ne a c hr o u t ea l l d e l i v e r i e sh a v et ob em a d eb e f o r ea n yc a r g oc a nb ep i c k e du pt oa v o i dr e a r r a n g i n gt h e l p a d so nt h ev e h i c l e s u c ha1 i m i t a t i o nc a nb er e l a x e df o rt i l ef s r p t h ef s r pi sa l s o d i f f e r e n tf r o mt h ev r pw i t hp i c k u pa n dd e l i v e r yf v r p p d ) b o t ht h ec o u p l i n ga n d p r e c e d e n c ec o n s t r a i n t s ，f o rt h ev r p p d ，b e t w e e nt h ep i c k u pa n dd e l i v e r ys t o p sc a nb e r e l a x e df o rt h ef s r p , s i n c ei t sp i c k u pc a r g o e si na l lf e e d e rp o r t sm u s tb et a k e nb a c kt o t h eh u b t h ed i f f e r e n c eb e t w e e nt h ef s r pa n dt h ev r p t wi st h a t ，f o rt h ef s p r ，t h e h u bp o r ta l s oh a st i m ew i n d o wc o n s t r a i n tb e s i d e sa l lt h ef e e d e r p o r t s t h ef s r pb e l o n g st on p - h a r dp r o b l e m s t h ed i s s e r t a t i o nd e v e l o p san e wi m m u n e g e n e t i ca l g o r i t h m n u m e r i c a le x p e r i m e n t si n d i c a t et h ep r o p o s e dm e t h o d sa r em o r e e f f e c t i v ei nr e d u c i n gt h et o t a ls h i p p i n gc o s t ，c o m p a r e dt oo t h e rf a m o u sa l g o r i t h m s k e yw o r d s ：v r p ；f s r p ；i m m u n eg e n e t i ca l g o r i t h m i i 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文 ：y 壁里查塞绫丛舶逦廑主笪芷壁廛用婴庭：。除论文中已 经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发 表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名 钿衅弓月舳 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和瓤：编学位论文。 不保密函( 请在以上方框内打“”) ：撕? 够颓 日期：o6 年；月，g 内 第一章绪论 1 1 选题背景和意义 在经济n 益仝球化的今天，节约物流成本越来越成为企业除“劳动力”、“自 然资源”之外的“第i 利润源泉”，是企业生产的前提和保证。伴随着全球性的企 业并购浪潮和世界经济一体化进程的加快，跨国物流配送飞速发展。而海洋船舶 运输在跨围物流配送系统中所承载的货量达8 0 以上1 1 j ，是运用最为广泛的一种， 凶此，研究船舶调度对于推进整个社会物流的现代化具有重要的意义。 2 0 0 4 年1 2 月1 4 日，交通部以交水发 2 0 0 4 1 7 2 9 号文件下发了关于促进国际 集装箱内支线运输发展的若干意见，这一文件对放宽市场准入，推动内外贸集装 箱同船运输，优化内支线航线布局，允许外资在内陆设分公司等给予了明确规定， 对提高内支线船公司与港口的资源利用效率，促进我国集装箱枢纽港的形成和发 展具有重要意义。劳埃德船级社业务部经理戴维托兹指出，集装箱船舶的型号向 特大型方向的持续发展，使得每个国际运输航次的运量获得显著的提高，从而必 然需要更多的集装箱货物供应量，这种氛同必然刺激集装箱沿海运输和短距离支 线运输的发展【2 j 。 从航运企业的层面上看，船舶调度、航线配船是关系到船队运输经济效益， 进而影响企业竞争能力和生存、发展的大问题。例如对于收入占整个航运业5 0 以卜的班轮运输来说，班轮航线具有很强的稳定性，一旦开辟，在相当长的时i u j 内很难变更。这就要求做到不仅在航线开辟之初，必须进行全面的、系统的、科 学的分析论证，而且随着货运任务的变化、航线条件的变化，慎重地选择适当的 时机重新进行船舶配置。然而，迄今为止，这一类工作一般都是靠投资经营者的 个人经验和主观判断力去完成，尤其是发展中国家的航运企业更是如此。已经开 发的为数不多的优化模型，其实际应用性也十分有限。 为了满足船舶营运的需要，港口的规模和数量逐年提高，尤其在喂给航线中， 喂给港的数量通常有几十个，船舶优化调度的问题逐步上升为n p h a r d 问题，以 前惯用的线性规划、动态规划等方法已经无法利用现有的计算机条件求出最优解， 不适于船舶配送模型。支线船舶调度的实际操作中调度员往往凭借经验主观判断， 然而其中蕴含着巨大的利润空间，调配得好会为船公司缩减船队规模，极大地降 低成本。 基于陆地配送的车辆调度问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 在困内外 近2 0 年来研究得比较多，可利用禁忌搜索、遗传算法等启发式算法在较短的时i h j 内求得最优解。其问题的基本模型经过变形后可以应用到支线船舶调度的优化中， 基于此，本文试图将v r p 问题的研究方法进一步扩展，以求在支线船舶调度优化 方面有所突破。 1 2 已有文献综述 v r p 问题，伞称v e h i c l er o u t i n gp r o b l e m ，也有些文献称之为v e h i c l es c h e d u l i n g p r o b l e m ，问题的实质是对于一个确定的顾客集合，在确定的需求下，如何安排车 辆行驶路线和时间，使得总的行使里程数最小。 国际上研究此类v r p 问题比较多，逐渐发展日趋完善。由于v r p 问题的求解 属于n p - - 难，很多学者不断提出了求解问题的启发式算法和亚启发式算法，还综 合应用了遗传算法、神经网络、禁忌搜索、模拟退火等，以及基于这些算法的改 进算法。 国内研究此类v r p 问题在近2 0 年来逐渐增多，西南交通大学的李军、郭耀 煌等人对满载运输、非满载运输以及送货( 或取货) 、送货取货一体化等问题进行 了分类研究，提出了相关模型和基本解法。 对于船舶调度的研究，目前国内主要集中于干线航线的设计，一般足建立线 性规划模型，用单纯形法求出最优解。对于喂给航线的规划，通常也是同样的做 法。但由于喂给港数量较多，直接求解往往使得问题的复杂程度呈指数增长。靳 志宏教授等人对此类问题做过一些研究，提出了集装箱船舶调度问题( c s r p ) 的 混合整数规划模型，并应用禁忌搜索法和临近搜索法进行求解。 国夕卜对支线船舶调度问题的研究也很少，c h r i s t i a n s e n 和n y g r e e n p l 以及 f a g e r h o l t m 等人都是将v r p p d 问题的扩展到散货船船舶干线运输，分别提出了集 货送货一体化的软时间窗多型船船舶调度模型( m p d p s t w ) 。对喂给航线船舶 调度问题的深入研究非常少。 2 1 3 本文的研究方法和结构 本文将车辆调度问题( v i 心) 的系统研究方法扩展到船舶支线调度中，建立 了混合整数规划模型，用改进的免疫遗传算法求得了满意解，对标杆数据的计算 结果表明了本算法的可行性和高效性。 鲈论_ _ 图1 i 论文结构围 f i g 1 1t h es t r u c t u r eo f t h ed i s s e r t a t i o n 本文的主要工作如图1 1 所示，具体如下： 本文的第一章全面而又概况地介绍了课题提出的背景和意义、现有文献综述 以及研究的思路和方法，为整篇论文的展开埋下伏笔。 第二章系统地介绍了目前旅行商问题( t s p ) 和车辆调度问题( v r p ) 的研究 方法和算法，为将其向船舶调度问题中扩展做好铺挚。 第三章研究了支线船舶调度的运营分析。支线船舶运输是本篇论文的研究对 象，因此重点分析了支线船舶运输的现状和发展前景以及我国国内支线运输的概 况，接着对航运企业目前在船舶调度方面的现状和问题进# 2 t 分析。 第四章是本文的重点，建立了支线船舶调度问题的混合整数规划模型，应用 免疫遗传算法对模型进行求解，试验数据结果验证了模型和算法的可行性和高效 性。 文章的最后对全文的工作做出了总结，同时也提 了研究中存在的一些需要 进一步讨论、修改并加以完善的问题和不足之处。 4 第二章v r p 一基本理论 物流配送车辆调度问题( v e h i c l er o u t i n gp r o b l e m ，简称冲) ，最早是由 d a n t z i g 和r a m s e r 亍1 9 5 9 年首次提出的，自此很快引起运筹学、应用数学、组合 数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者 和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。旅行 商问题( t r a v e l i n gs a l e s m a np r o b l e m 简记t s p ) 是v r p 的基本问题，是运筹学、 圈论阱及组台优化中的著名难趣，由于其有广泛的应川背景，引起j ，人们的极大 兴趣。t s p 除了可以解决类似最优巡回线路的问题之外，还可以用于解决生产运 作系统中的装配线进度问题、数控机场的运行问题等等。本章首先对t s p 问题做 一些研究，然后再深入研究v r p 问题和其几种变化形式。 2 1 旅行商问题( t s p ) ， 旅行商问题( t s p )般描述为：某旅行商要6 往若f 二城市，从城市0 出发， 经过其余各城市次且仅仪一次，然后同到m 发点，求其晟短行程，即寻找一条 巡回路径丁= 0 ，t 2 ，。) ，使得下列目标函数最小： ，p ) = d ( ，。t + ) + d “，r d ) ，；0 上式中f ，为城市号。取值在0 到l 之间的自然数，d ( t t ) 表示城市i 和城市j 之问的距离。 2 】1 旅行商问题( t s p ) 的数学模型 一般t s p 足指一个旅行商访问所有城市。用图论的语言捕述为：在一个加权 刚中，找出一个最小权的啥密顿圈。 令g = ( 矿，a ，c ) 为加权网络图； v = f 0 12 ， 为顶点集，表示旅行商需要经过的地点，其中点0 为源点； a = 0 ，j ) j ，= 0 ，1 ，i 力为弧集，、表示旅行商口j 能走过的线路段集合； f = 扛。l ( i ) e 4 为费用矩阵，白表示旅行商经过对应弧段o ) 所花的费用， c = 缸。i ( i ，) e 爿 为费用矩阵，勺表示旅行商经过对应弧段o ) 所花的费用， 第二章v r p 一基本理论 物流配送车辆调度问题( v e h i c l er o u t i n gp r o b l e m ，简称冲) ，最早是由 d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出的，自此很快引起运筹学、应用数学、组合 数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者 和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。旅行 商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简记t s p ) 是v r p 的基本问题，是运筹学、 罔论阻及组合优化中的著名难题，由于其有广泛的应用背景，引起了人们的极大 兴趣。t s p 除了可以解决类似最优巡回线路的问题之外，还可以用于解决生产运 作系统中的装配线进度问题、数控机场的运行问题等等。本章首先对t s p 问题做 一些研究。然后再深入研究v r p 问题和其几种变化形式。 2 1 旅行商问题( t s p ) 旅行商问题( t s p ) 般描述为：某旅行商要前往若十城市，从城市0 出发， 经过其余各城市饮且仅仅一次，然后回到出发点，求其最短行程，即寻找一条 巡回路径丁= o 。，f ：，。) ，使得下列目标函数最小： ，口) = 4 t t + ) + d ( f 。t ) i = 0 上式中f ，为城市号，取值在0 到l 之间的自然数，d ( t ，f ，) 表示城市i 和城市j 之间的距离。 2 1 1 旅行商问题( t s p ) 的数学模型 一般t s p 是指一个旅行商访问所有城市。用图论的语言描述为：在一个加权 图中，找出一个最小权的哈密顿圈。 令g = ( y ，a ，c ) 为加权网络图； v = f o 12 ， 为顶点集，表示旅行商需要经过的地点，其中点0 为源点； a = 缸，) f ，= 0 , 1 ，i ， 为弧集，表示旅行商可能走过的线路段集合； c = 。i ( 1 ，) 爿 为费用矩阵，白表示旅行商经过对应弧段( f ，_ ，) 所花的费用， 如时间、距离、纯费等。 定义变量如下： f 1边( f ，) 在最优线路上 2 1 0否则 则t s p 的数学模型可以写成如下的混合整数规划形式： m i n z = 白 = 1 j = 0 , 1 ，一， = 1i = 0 “1 ? l s - 1 s v l ，l e s x 0 o ，1 f ，矿 其中，c 。= m ( i = 1 ，) s 为支路消去约束( s u b t o u r - - b r e a k i n g ) ，即消去构 成不完整线路的解。s 有多种表示方法，本模型中i s l 为集合s 中所含图g 的顶 点个数。前面两个约束意味着对每个顶点而言，仅有一条边进和一条边出，后一 条约束则保证了没有任何予刚路解的产生。于是，满足上述约束条件的解构成了 一条遍历所有顶点的哈密顿回路。 2 1 2 求解旅行商问题( t s p ) 的启发式算法 一般，应用启发式算法求解旅行商问题时，先用线路构造法得到初始解，再 用线路改进法对初始解进行改进。 2 1 2 1 。线路构造法 线路构造法有很多种，如节约算法、最邻近法、几何启发式算法、最小生成 树算法、最近插入算法等。其中最经典的、应用的最多的足由c l a r k e 和w r i g h t 于 1 9 6 4 年提出的节约算法，又称c w 算法。 它的基本思想是首先把各点单独与源点o 相连，构成1 条仅含一个点的线路。 总费用为 三= + ， 6 一 b ，脚 然后计算将点，和j 连接在一条线路上费用的“节约值”： s ( f ，) = c 。，+ c ，。+ c 。，+ c ，。一( c 。，+ c ，+ c j o ) 三c ，。+ c 。，一c ， s ( j ，f ) = q 。+ c 。，一 s ( i 1 越大，说明把f 和j 连接在一起时总路程减少越多。构造线路时，根据 s p ，) 从大到小的顺序进行，实现时可在表上操作，具体步骤如下： s t e p l ：计算节约值s ( f ，j ) ，并排列成表格形式； s t e p 2 ：在表格中选择最大元素s ( f ，a s t e p 3 ：考察s ( i ，) 对应的点f 和点j ，检查是否满足下列条件： 若点i 和点，均不存己构成的线路上，则可连接点，和点j ，得到线路段 0 一i 斗j 0 ，转步骤s t e p 4 ； 若点i 或点，在已构成的线路上，但不是线路的内点( 即不与源点0 直接相 连) ，则可以连接，连接后得到线路段0 寸i 一，斗o 或0 斗i 叶- ，斗0 ，转步 骤s t e p 4 ： 若点f 和点j 位于已构成的不同线路上，且均不是内点，则连接后得到线路 段o _ 一i 斗j - 9 , 呻0 ，转步骤s t e p 4 ； 若点衍日点i ，在已构成的| 司一条线路上，则不能再进行连接，转步骤s t e p 4 。 s t e p 4 ：划去第f 行和第j 列，即i 不能再到其他点，而点也4 i 能由其他点到 达； s t e p 5 ：若所有元素均被划去，则已得到完整线路，算法终止；否则，在未被 划去的元素中选择最大元素，转步骤s t e p 3 。 2 1 2 2 线路改进法 应用局部搜索的概念，通过对边( 或弧) 进行交换，在初始可行解的邻域中 对和始解进行调整，每次调整使可行解得到改进，直至解在邻域内不能改进为止。 常用的改进方法有2 一交换、3 一交换、o r - - 交换等。下面以2 一交换和o r 一交换为 例说明线路改进法的应用。 ( 1 ) 2 一交换 以( f ，j ) 、( + 1 ，j + 1 ) 代替( f ，i + 1 ) 、( ，j + 1 ) ，交换后线路中的路径( + 1 ，j ) 被 反向，如图2 1 所示。 一叫d 书、一叫0 _ 卜叫生! 夕、 ，、 一：! h ! 卜 圈2 12 一交换示意罔 f i g 2 1 2 - o p t 当交换后线路长度缩短，即满足以下条件时 c ，+ c ，+ 1 ，+ l f ：) ； 反向定位：把路段向前定位( ， f ) 。 在实际实现定位时，采用字典式搜索方式。 正向o r 一交换的字典式搜索：在目前线路上选择路径( f 1 ，i ：) ，从 f ：+ 1 ，i ：+ 2 ) 开始，选择边d ，- ，+ 1 是 f ：+ 1 ，i 2 + 2 、 f ：+ 2 ，i ：+ 3 ) 、如一1 ，n ，即边口，j + l 正向走过线路。 反向o r 一交换的字典式搜索：在目前线路上选择路径( j l ，一，i ：) ，从 f 1 2 ，i 。一1 ) 开始，选择边d + i ) 是 f l 一2 ，i ，l 、 f 。一3 ，一2 ) 、 0 ，1 ) ，即边d + l 反向 走过线路。 当所得到的线路无法再改进时，即得到了此算法下的最优解。 2 1 3 多重旅行商问题 多重旅行商问题( m t s p ) 是一般旅行商问题的推广和深化，也称为无容量约 束的v r p 问题。m t s p 指m 个旅行商访问所有城市，要求每个城市至少访问一次， 应如何安排旅行路线，使m 个旅行商的总旅行费用最少。 符号说明如前节，以点0 表示旅行商的出发城市，称为源点，点1 ，表示m 个旅行商需访问的城市。 定义变量 f 1旅行商k 通过弧( f ，) 2 1 0 否则 f 1旅行商k 访问城市i y 沪1 0 否则 则得到以下模型： ，fm m i n z = 铲叶 9 姒芝地= 抒 = 11 1 x g k = 蜘 f = 0 i = 1 - 2 f _ ，= 0 ，1 ，- 一，；k = 1 , 2 ，m x 啦= y 目 i = o ，1 ，z ；k = 1 ，2 ，m j = 0 x ，i s | 一1s o _ 1 ，2 ，一，z ，j e s t 。= 0 或1 其中，式表示除源点0 被访问m 次之外，其余城市均被访问一次且仅一次； 式表示每个城市只有一条边进和只有一条边出；式保证了没有子回路产生。 2 2 车辆调度问题( v r p ) v r p 问题一般描述为：有一个车场，拥有容量为q 的车辆，现在有，项货物运 输任务需要完成，以1 ，表示，已知任务f 的货运量为g ，( f = 1 ，) ，且g ， q ， 求满足货运需求的费用最小的车辆行驶线路。经典的v r p 问题中，只有一个配送 中心( 中心仓库) ，车队的车型都是相同的，所有的车辆都是从配送中心出发，最 后回到配送中心，图2 _ 3 表示了v r p 问题的两种情况，一种是把配送中心仓库的 货物送到卸货点( d e l i v e r i e s ) ，另一种是把装货点的货物运到仓库( p i c k u p s ) 。 o 卸货点取货点。配送中心 图2 3v r p 问题车辆行驶示意图 f i g 2 3v e h i c l er o u t i n gp r o b l e m 0 2 2 1 车辆调度问题( v r p ) 的一般模型 将车场编号为0 ，任务编号为1 , - - - , z ，任务及车场均以点i ( i = 0 , 1 ，7 ) 来表示。 定义变量如下： f 1点i 的任务由车辆k 完成 y k , 2 1 0否则 i1车辆i 从点i 行驶到点， 嘞2 1 0否j i l | j 则可得到车辆优化调度数学模型如下： m i n z = q j j k f 邑y 。q v k l = 1 i = l ， i e x 叶= y h j = 0 , 1 ，l ；v k s t = _ y h 江0 , 1 ，l ；v k l x = ( x o k ) s 1 = o 或1 i ，j = o ， ，l ；v k i y b = o 或1 i = 0 , 1 ，l ；v k 【 模型中，目标函数中c 。表示为从点f 到点j 的运输成本，它的含义可以是距离、 费用、时间等。第一个约束表示每辆车所载货物不超过车辆的容量q ：第二个约束 表示每一任务都有且仅有一辆车来服务：第三个约束和第四个约束表示每辆车行 驶过程中，如果经过某一任务点，则只经过一次；第五个约束是支路消去约束： 最后两个约束是对变量的取值约束。 2 2 2 车辆调度问题( v r p ) 的几种变形 带时间窗约束的v r p 问题( v r p t w ) 有时间窗的车辆优化调度问题描述如下：设完成任务i 需要的时间( 装货或卸 货) 表示为f ，又设任务j 的开始时间需在一定的时间范围陋互，三f 】内，其中e i 为 任务f 的允许最早开始时间，z 为任务f 的允许最迟开始时间。如果车辆到达f 的 时间早于e f ，则车辆需在f 处等待，如果车辆到达时间晚于上r ，任务i 要延迟进 行。求满足货运需求的费用最少的车辆行驶线路。 带时间窗约束的v r p 问题在实际生活中应用很多，如牛奶配送服务，往往要 求在早晨的某个时间段送到；再如物流服务中的门到门运输，越来越对时间有更 高的要求。 时问窗的约束分为硬时间窗和软时i 脚窗。所谓硬时间窗是指每项任务必须在 要求的时间范围内完成。以s 。表示车辆到达点i 的时间，则有e z s ，l t , ，如果 不满足此式，则得到的解为不可行解。软时间窗足指如果某项任务不能在要求的 时问范围内完成，则给予一定的惩罚。若车辆在e z 之前到达点i ，则车辆在此等 待，发生了机会成本损失。若车辆在三r 之后到达点i ，则服务被延迟，须支付一 定的罚金。 用数学公式表示如一卜： 车辆等待的时问：归= m a x e t 。一：0 l 服务被延迟的时间：d t , = m a ) 【扛，一z ，0 目标函数相应地，变为r a i nz = 口勺工社+ ，啊+ c d z ，其中 |lk 。 】1 口，y ，o - 是权重系数，由问题的实际情况而定。 带回程配货的v r p 问题( v r p b ) 在v e h i c l e r o u t i n g p r o b l e m w i t h b a c k h a u l s ( 简称v r p b ) 中，顾客群被分成两 个集合，是顺程运输集，一是回程运输集。般情况下，车辆在配送中一心装载 货物后，将货物运送到顾客( 顺程) ：然后，又装上一些新的货物，将其运同配送 中心( 回程) 。如果所有的顾客都是顺程( 或回程) ，那么v r p b 问题即简化为v r p 问题。 生活中这样的例子很多，如空车配货公司，就是为了满足回程空载的需求应 运而生的：又如某些电器公司的配送服务，把顾客需要的产品送到顾客的家中， 把某返修的产品从顾客家中运回仓库，等等。 严格地说，v r p b 问题也是安排车辆路线的问题，可以详细地描述如下： i ) 每一车辆有一条行驶路线； i i ) 在每条路线上的任何时候装载量都不超过车辆的总载重； i i i ) 在每条线路上，取货点总是在卸货之后到达； i v ) 总的行驶里程最小。 其中，第i i i ) 条中的顺序约束是因为，在实践中，卸货的顾客一般总是比取 货的顾客优先；而且在顾客处，由于缺少必要的装卸设备，运载车辆很难进行倒 货，有时甚至是不可能的。如图3 2 所示。 o 送货点取货点 图2 4 - v r p b 示意图 f i g 2 4 v r pw i t hb a c k h a u l 在进行算法设计时，由于第i i i ) 条约束，若卸货顾客i 不在已构成的线路上， 顾客i 必须被插入两个卸货点之间或最后一个卸货点和第一个装货点之问；同样， 若装货顾客i 不在已构成的线路上，顾客f 必须被插入两个装货点之间或最后一个 卸货电和第一个装货点之间。 如果每一个送货或取货的顾客都有一个时间段的服务约束，那么v r p b 问题 就演变为v r p b t w 。 既有送货又有取货的车辆调度问题( v r p p d ) 在v e h i c l er o u t i n gp r o b l e mw i t hp i c k u pa n dd e l i v e r y 问题中，通常是多车场多 车型的问题。每项任务有自己的取货点和相应的卸货点，需要在两点之间进行必 要的运输。此问题可以描述如下：已知任务f 要求在集货点“，装货，然后运至送货 点u 卸货，货运量为曼。这些任务由车场发出的车辆来完成，车辆容量为q ，已 知g ， q ，如何确定车辆行驶线路，使总费用最少。 对于v r p p d 的数学模型，除了车辆容量和时间窗的约束外，还有货物装卸顺 序的约束。在实践中，为了防止因倒货而发生货损引起纠纷，货主一般拒绝为了 方便其他货主而对自己的货物卸下后再装车。这样，一票货物装车后，只能在其 他晚装车的货物卸完后才能卸车。实质上是卸车的顺序与装车的顺序相反f ”。 1 如果大部分货运任务有妄q 受 g ，各项任务难于组合。这时，一辆车执行完 z 一项任务后，由该项任务的送货点窄驶向下一任务的集货点。对于每项货运任务 而言，由其集货点至送货点为重车行驶，且必须完成，故不妨将这一运输任务看 成一个点，为了区别超见，称之为重载点：重载点内为重车行驶，其行驶线路可 以按任意两点对间的最短路方法确定。在满足一定约束条件下，车辆交替重驶和 空驶，形成车辆行驶线路。 若各项任务无时间要求，由于重载点的引入，同经典的v r p 问题无本质区别。 当各任务有时间要求时，其实质为有时间窗的t s p 问题，可用c w 肩发式算法 求解。 1 如果大部分货运任务有o 氍 去g ，一辆丰可以在几个集货点装货，然后再到 z 几个送货点卸货。一般，儿项任务的集货点和( 或) 送货点比较接近时，组合用 一辆车运输比较经济，这样的一些任务称为一组任务。一辆车完成一组内的所有 任务后，在满足总行驶里程约束的前提下，可再考虑完成其他组的任务，即组与 组之间进行一定的连接。这类问题的解法一般是先分组，再连接，即组合启发式 算法。 2 2 3 求解车辆调度问题( v r p ) 的常用启发式算法 求解v r p 问题的常用启发式算法有c w 节约启发式算法、分派启发式算法 等，本节对c w 节约启发式算法进行了研究。 对旅行商问题的c w 算法进行修正，用来求解单车场、单车型的车辆优化 调度( v r p ) 问题。 符号说明同前，以表示车辆从点缉亍驶到点- ，的费用，由c w 算法，得到 点i 和点_ ，连接在一条线路上的费用节约值 s ( f ，力= c ，o + c o ，一 与c w 算法类似，只是在连接点对时，需考虑车辆的容量约束，即一条线 路上各任务的货运量之和应不大于车辆的容量。具体的步骤如下： s t e p l ：计z 4 i ，) ，令m = ( f ，淞( f ，j p o ； s t e p 2 ：在m 内按j ( ，) 从大到小的顺序排列： s t e p 3 ：若m = ，则终止，否则对第一项4 i ，) ，考察对应的( f ，j ) ，若满足下 列条件之一： 点i 和点，均不在己构成的线路上； 点f 或点在已构成的线路上，但不是线路的内点( 即不与车场相连) ： 点i 和点位于已构成的线路上，均4 i 是内点，且一个是起点，一个是终点。 则转下步，否则转s t e p 6 。 s t e p 4 ：考察点i 和点，连接后的线路上总货运量q ，若q q ，则转下步，否 则转s t e p 6 。 s t e p 5 ：连接点i 和点- ，转s t e p 6 ； s t e p 6 ：令m = m s ( f ，) ，转s t e p 3 。 对于有硬时间窗约束的问题( v r p t w ) ，即各项任务要求在一定的时间范围 内完成，按费用节约值s ( f ，) 连接点弭口点- ，时，可能会使j 后面的任务的执行不满 足时间要求。当连接点i 和点，所在线路时，若车辆到达，点的时问比原线路上，点 任务的开始时间提前，则车辆在点后面的任务处有可能需要等待：若连接后，到 达，点的时间比原线路上，点的任务的开始时间推迟，则，点后面的任务在执行时 口 能会发生延迟。 以e f f 表示连接点f 和点j 所在的线路后，车辆到达j 点的时间比原线路上车 辆到达j 点时间的推迟( 或提前量) ，则弘可如下得到： e f i = s l + t l + tu sj 其中j ，和5 ，分别表示连接点f 和点- ，之前，车辆到达f 点和i ，点的时间，一表示 在f 点的作业时间( 如装卸、理货等) ，f 。表示从点涯0 点，行驶时问。 显然，e c 0 时，到达时间推迟。 为说明问题方便，定义参数如下： i 当车辆在线路上，点后面的各任务处均不需要等待时，j 点的到达时 间的最大可以提前量： 十当线路上，点后面的各任务不违反时间窗约束时，点的到达时间的 最大允许推迟量。 ：和：可分别按下式计算： j2 巧紫，一e 0 j 。卿扯一s ， ，其中e t 和l r 分别表示r 点任务的允许最早开始时间和 允许最晚开始时间。 当考虑连接点i 和点，所在的线路时，需检查是否违反时问窗约束。 当晖 o 时，若有e ，则_ ，后面的任务的执行不会延迟，否则，要 延迟进行。 对于软时间窗约束的问题，可按照前面2 2 ，2 节( 1 ) 中软时间窗问题f 1 标函 6 数的变化来进行修正。 由于时间约束的引入，在对称的费用情况下，连接点- ，和点i 与连接点i 和点 不再相同。 7 第三章支线船舶调度的运营分析 本章的目的是分析本论文的研究对象支线船舶运输，第一节分析了船舶配送 的种类，从丽引出支线运输；第二节分析了支线船舶运输的发展前景，说明进行 支线船舶调度的研究是有重要意义的，同时简述了我国国内支线运输的概况：第 三节介绍了我国航运企业在船舶调度方面的现状。 3 1 船舶配送的种类 船舶配送按照不同的分类方法，有很多种。 按照船舶的经营方式的不同，船舶配送可以分为班轮运输和租船运输。 班轮运输又称定期船运输，是指船舶按照固定的船期表、沿着固定的航线和 港口来配送，并按照相对固定的费率收取费用。定期船的船型主要是集装箱船、 传统杂货船、液装船、载驳船和多用途船。而货物多为普通杂货、集装箱货、散 杂货等，人多是工业成品和半成品、高价商品。租船运输又称为不定期船运输， 与班轮运输的方式不同，没有固定的船期表，船舶经由的航线和停靠的港r 也不 固定，需要按租船合i 司来安排，有关船舶的航线和停靠的港口、运输货物的种类 以及航行时间等，都按照承租人的要求，由船舶所有人确定，运费或者租金也由 双方根据租船市场行市在租船合同中加以约定。 按照挂靠港口的不同，船舶配送又可以分为干线运输和支线运输。 干线是指货运量大而集中的主干航线或航线组，如北美至欧洲、北美至东蹶 等航线。干线运输是指船舶在主干航线上航行；干线运输船舶的船型通常较大、 吃水较深、航速较快，所挂靠的港口一般为深水良港，是沿海经济贸易中心。支 线即分支航线，又称补给线( f e e d e rl i n e ) ，是指干线外的其他航线，也是大港与小 港之间形成的货物集散、喂给航线。在支线运输的船舶船型一般不大，吃水较浅， 通常船舶往返或巡回于喂给港和枢纽港之间，将货物从喂给港运送到枢纽港，或 从枢纽港运送到喂给港。 集装箱船的运营一般是在主要贸易港口问进行，其他港口到主要港口间的运 输，则以支线运输方式进行。 8 3 2 支线船舶运输概述 3 2 1 支线船舶运输的地位和发展前景 当前，船舶大型化的发展趋势必然会促进支线网络的建设和多式联运以及全 球物流一体化的进程。基于营运成本、港口航道、泊位、货量等因素的考虑，船 公司在一个地区只会有一个枢纽港。航运公司一旦选择了超大型船舶，十线船舶 挂靠港口的布局将更加趋于合理，而经贸发展的变化和船公司经营战略的转变将 使目前许多挂靠的干线港变为支线港。支线运输和下线运输都是远洋运输链中的 一个环节，只是负责的区段、距离不同而已。受港口条件限制和对运输成本、时 间成本、人力资源成本的考虑，支线运输有其存在的必然性和必要性，也有其发 展宅间。正如劳埃德船级社戴维托兹指出，“集装箱船舶的型号向特大型方向的持 续发展，使得每个国际运输航次的运量获得显著的提高，从而必然需要更多的集 装箱货物供应量，这种氛围必然刺激集装箱沿海运输和短距离支线运输的发展”。 在欧洲贸易航线上，f e e d e d i n ks h i p p i n g & t r a d i n gb v 公司管理董事h a r r y k l e i p a s 认为，不管远洋班轮运输如何增长，支线运输业务将迅速增长，如果大型 船舶限制其挂靠港，则对支线贸易运输将产生巨大的促进作用，将使支线运输增 长6 以上，同时支线运输的船舶会向规模化、专业化的方向发展。据c o n o s h i p 国际公司市场部s a n d e rs e h a k e l a a r 称，挂靠外国港u 的快速、高效和可靠的支线运 输船舶的需求正同益增长。 以我国为例。从1 9 9 9 至2 0 0 4 年，我国内支线运输住外贸集装箱运输1 s 速发 展的带动下，整体增长势头迅猛。1 9 9 9 年，我国主要港口内支线运输吞吐量1 4 7 7 万t e u ( 见图2 1 ) ，到2 0 0 4 年增长至4 3 7 3 万t e u ；全国开展内支线业务的挂靠 港口数也从2 0 多个发展到5 0 多个，形成了内支线运输三大区域港u 。第一是以 上海为中心的长江干线和三角地区港口，第二是以大连、天津、青岛为中心的渤 海湾地区港口，第三是以深圳为中心的珠江三角洲地区港口。2 0 0 4 年，上海港、 青岛港、大连港内支线吞吐量比上年增长分别高达4 4 6 、2 7 6 、1 6 1 7 ，深 圳港内支线比上年增长1 2 1 倍。中心港口内支线航班密集，服务更趋专业化、规 模化1 1 1 17 1 。 9 港口总吞吐磬0 0 ( f y t e u ) 4 0 0 3 0 0 2 0 0 1 0 0 0 - -