（交通运输规划与管理专业论文）集装箱支线运输班轮航线规划与配船问题研究.pdf

t h e a n a l y s i so fs h i pr o u t i n ga n da s s i g n m e n tp r o b l e m si n c o n t a i n e rf e e d e rl i n e r at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h e d e g r e eo f m a s t e r z h a n gl e i ( t r a n s p o r t a t i o np l a n n i n ga n dm a n a g e m e n t ) t h e s i ss u p e r v i s o r ：p r o f e s s o rj i n z h i h o n g j u l y2 0 1 1 咖8 川5舢859删8iiii-m y 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成博 硕士学位论文除论文中已经注明弓 用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论 文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明 的法律责任由本人承担。 学位论文作者签名：盟 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文的规 定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本 学位论文收录到中国优秀博硕士学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂 志社) 、中国学位论文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出 版物形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密彤( 请在以上方框内打“”) 一：张穆名：罾、2 么 日期：弘怍月动日 中文摘要 摘要 上世纪九十年代开始，世界经济的蓬勃发展带来了国际贸易量不断增加，这 使得集装箱班轮运输业务迅猛发展，给航运界带来了勃勃生机。据资料显示国际 货物的8 0 左右是通过海运方式来完成的。经济形势大好时，各大航运公司为扩 大企业规模、增加企业盈利，不断订造新船或租赁船舶、增设航线、吸纳货源， 这使得船舶数量大幅度上升。而2 0 0 8 年下半年爆发的全球经济危机使得国际贸 易受到重创，导致航运业低迷，很多船公司吸纳不到足够的货物，这就会发生运 力过剩的情况，而且加上航运业的退出机制比较缓慢，这就可能会给船公司带来 不小的风险。而航线规划与配船关系到船队运输经济效益、船队整体结构优化， 进而影响企业竞争能力，因此合理的进行航线规划与配船对于船公司显得尤为重 要。各大型船公司无不面对现实而涉足于这项研究。船公司要全面地、深入地对 船舶组织的合理性作系统的分析研究，使船舶最大限度地发挥其效用。 在陆上车辆调度问题( v e h i c l er o u t i n gp r o b l e m ) 理论的基础上，本文建立 了集装箱支线班轮运输问题( f e e d e rl i n e rc o n t a i n e rs h i p p i n gp r o b l e m ) 航线规划与 航线配船的非线性规划模型。现有的航线规划或配船模型都是相互独立的线性规 划问题或整数规划问题，只能局限于某个单一问题求最优解，无法使整个系统达 到最优。与v r p 问题及其变型相比，集装箱支线班轮船舶调度问题有很大不同。 它需要设计一个周期服务的模式来满足服务频率的要求和计划周期内的运输需 求，而且需同时考虑航线设计和不同船型的航线配备。集装箱支线运输挂靠港口 众多，航线分布密集，船型多样，对于此n p 完全问题，本文设计了组合遗传算 法，并对实例进行了求解，计算结果证明了模型及算法对于节约船舶资本成本和 经营成本具有一定的有效性和可行性。 关键词：集装箱支线；班轮；航线规划与配船；遗传算法 英文摘要 a b s t r a c t f r o mn i n e t i e so ft h el a s tc e n t u r y , t h ew o r l d sb o o m i n ge c o n o m yh a sb r o u g h t e v e r - i n c r e a s i n gi n t e r n a t i o n a lt r a d e ，w h i c hm a k e st h er a p i dd e v e l o p m e n to fc o n t a i n e r l i n e rb u s i n e s sa n dh a sb r o u g h tv i t a l i t yt ot h es h i p p i n gi n d u s t r y a c c o r d i n gt os t a t i s t i c s ， a b o u t8 0 o fi n t e r n a t i o n a lc a r g oi st r a n s p o r tb ys e aw a y i nt h ee x c e l l e n te c o n o m i c s i t u a t i o n ，i no r d e rt oe x p a n dt h ee n t e r p r i s es c a l ea n di n c r e a s ec o r p o r a t ep r o f i t s ，t h e s h i p p i n gc o m p a n i e sb e s t e l l e nn e wv e s s e l so rl e a s ev e s s e l s ，i n c r e a s er o u t e sa n da b s o r b s u p p l y , w h i c hm a k e sas i g n i f i c a n ti n c r e a s ei nn u m b e ro fs h i p s i nt h es e c o n dh a l fo f 2 0 0 8 ，t h eo u t b r e a ko ft h eg l o b a le c o n o m i cc r i s i sh a sr e s u l t e di nt h ed e p r e s s i o no f i n t e r n a t i o n a lt r a d ea n dt h es h i p p i n gi n d u s t r yd o w n t u r n m a n ys h i p p i n gc o m p a n i e sc a n n o ta b s o r be n o u g hg o o d s c o u p l e dw i t ht h es h i p p i n gi n d u s t r ye x i tm e c h a n i s mi s r e l a t i v e l ys l o w , t h i ss i t u a t i o nm a yb r i n g ss h i p p i n gc o m p a n i e sr i s k t h es h i p sr o n t i n g a n da s s i g n m e n tp r o b l e mr e l a t e st ot h ee c o n o m i cb e n e f i t sa n dt h eo v e r a l ls t r u c t u r eo f t h ef l e e t ，t h e r e b ya f f e c t i n gt h ec o m p e t i t i v e n e s so fc o m p a n i e s s o ，b er e a s o n a b l e 、) l ，i t l l s h i p sr o u t i n ga n da s s i g n m e n tf o rt h es h i p p i n gc o m p a n y ss u r v i v a la n dd e v e l o p m e n ti s p a r t i c u l a r l yi m p o r t a n t t h em a j o rs h i p p i n gc o m p a n i e sa r ea l lt of a c er e a l i t yi n v o l v e d i nt h es t u d y t h es h i p p i n gc o m p a n i e sh a v et om a k eac o m p r e h e n s i v ea n dd e 印 r e s e a r c ho nt h eo r g a n i z a t i o no fs h i p st om a x i m i z ei t se f f e c t i v e n e s s b a s e do nt h ev e h i c l er o u t i n gp r o b l e m ，t h i sp a p e rp r e s e n t sac o m b i n e d o p t i m i z a t i o ni pm o d e lo fs h i pr o u t i n ga n da s s i g n m e n t i nf e e d e rl i n e rc o n t a i n e r s h i p p i n gp r o b l e m ( f l c s p ) e x i s t i n gf o r m u l a t i o n so fs h i pr o u t i n go rs h i pa s s i g n m e n t a r ei n d e p e n d e n tl po ri p , w h i c hc a l ln o ts a t i s f yt h eo p t i m i z a t i o no ft h ew h o l es y s t e m w h i l ec o m p a r e dt ov l 冲o ri t sv a r i a t i o n s ，f e e d e rl i n e rc o n t a i n e rs h i p p i n gp r o b l e mi s q u i t ed i f f e r e n t ，f o rt h a tf l c s ph a st od e s i g nap e r i o d i cs e r v i c ep a t t e mi no r d e rt o m a i n t a i nt h em i n i m u ms e r v i c ef r e q u e n c ya n ds a t i s f yt h ec o n t a i n e rt r a n s p o r t a t i o n d e m a n di nt h ep l a n n i n gh o r i z o n , a n dn e e dc o n s i d e r i n gs i m u l t a n e o u s l yb o t l lt h e a s s i g n m e n to fd i f f e r e n tt y p e so fs h i p sa n dt h ed e t e r m i n a t i o no f r o u t e s ac o m b i n e d 英文摘要 g e n e t i ca l g o r i t h mi sp r o p o s e da sf l c s p b e l o n g st on p h a r dp r o b l e m s t h er e s u l t so f t h ep r a c t i c a le x p e r i m e n t si n d i c a t et h a tt h ef o r m u l a t i o na n da l g o r i t h ma r ee f f i c i e n ta n d 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 k e yw o r d s ：c o n t a i n e rf e e d e r ；l i n e r ；s h i p sr o u t i n ga n da s s i g n m e n t ；g e n e t i c a l g o r i t n m 目录 目录 第1 章绪论一l 1 1 论文背景- 卜 1 1 1 集装箱运输量的迅速增长- 1 - 1 1 2 集装箱支线运输的发展现状一2 - 1 1 3 集装箱大型化对支线运输的需要3 1 2 国内外研究现状综述一5 - 1 2 1 航线规划- 6 - 1 2 2 航线配船一6 - 1 3 本文研究的主要内容及研究思路一7 1 4 本文的创新点- 8 一 第2 章集装箱班轮航线规划及配船理论一9 2 1 集装箱班轮运输概述9 2 1 1 集装箱班轮运输的特点9 2 1 2 集装箱班轮航线的营运方式一l 0 2 2 航次规划的相关理论概述：1 2 2 2 1 航线的布局方式一1 2 2 2 2 班轮挂靠港口的选择13 2 2 3 班轮航次组织的经济比较1 4 2 2 4 班轮船期表的编制1 5 2 2 5 航线班期方案的拟定- 1 6 2 3 航线配船的相关理论概述一1 7 2 3 1 配船方法一1 7 2 3 2 航线配船方案的选择问题一1 7 2 3 3 集装箱班轮航线配船的特征18 2 3 4 航线配船的相关特性分析1 9 2 3 5 航线配船经济效益分析2 1 - 第3 章遗传算法简介2 5 3 1 遗传算法概述一2 5 - 3 2 遗传算法流程一2 6 一 第4 章集装箱支线班轮航线规划和配船问题的联合优化一2 9 4 1 问题的描述- 2 9 4 2 建立模型3 0 4 2 1 符号和假设一3 0 目录 4 2 2 混合整数规划模型一3l 一 4 3 模型求解- 3 2 - 4 3 1 组合遗传算法一3 2 - 4 3 2 航线规划决策的遗传算法求解一3 3 - 4 3 3 航线配船决策的遗传算法求解- 3 3 - 4 4 算例分析- 3 4 一 第5 章结论- 3 6 - 5 1 本文结论一3 6 5 2 今后的研究方向- 3 6 - 参考文献- 3 7 一 致谢- 4 0 - 集装箱支线运输班轮航线规划与配船问题研究 第1 章绪论 1 1 论文背景 随着世界经济全球化趋势的发展，以及我国国民经济的不断完善，我国对外 贸易量一直保持着强劲的增长势头，而海上运输作为国际贸易运输的主要方式得 到了迅速的发展，集装箱运输由于具有适用性广泛、作业效率高以及能够大幅降 低减低货损成本和便于管理等优势，在全球的物流业中取得了迅猛的发展。随着 发达国家集装箱现代化水平的越来越高，发展中国家集装箱水平也在不断提高， 这几年来，随着我国经济逐渐成为世界工厂，物流业迅速发展，中国已经成为世 界集装箱运输发展最快的地区之一。2 0 0 3 年我国港口集装箱吞吐量达到4 8 0 0 万 t e u t l l ，首次超过美国跃居世界第一位；2 0 0 7 年超过了1 亿箱，具有了划时代的 意义；2 0 0 8 年，虽然全球遭遇了金融危机和海啸，但是我国集装箱吞吐量仍然 达到了1 1 4 0 0 万t e u 。我国集装箱吞吐量已经占到了世界的2 0 以上。 由于集装箱数量的迅猛增长和受高利润的趋使，吸引了国内外众多船公司投 身到这个行业中来【2 】，使得集装箱市场的运力远远大于它的需求量，竞争越来越 激烈和白日化，同时人们对于集装箱货物运输的要求也越来越高，不仅要“门到 门的高质量服务水平，而且也要保证货物的安全和准时到达等等，这就要求船 公司不仅要合理地对航线进行规划和对集装箱船舶进行分配，从而保证服务质 量，打败竞争对手，获得最大利润。 不同于大的船公司，小规模的公司一般经营的航线相对来说比较单一，所以 几乎很少涉及到航线规划和配船的问题，只需要在更换船舶或者是发展新航线时 考虑怎样选择适合的船型就行，相反，对于有实力的大公司来说，自身会拥有大 规模的船队，经营的航线很多，在不同航线上运营的不同船舶的效益是不一样的， 即使是一条航线上，不同船型的船舶的运营收益也是不同的，所以就要考虑如何 进行航线规划并且将不同类型的船舶分配在不同的航线上运营，在运力与运量相 符的约束条件下，可以获得更多的利益。 1 1 1 集装箱运输量的迅速增长 随着经济全球化趋势的发展和我国市场经济的不断完善，我国对外贸易迅猛 发展，而对外贸易的9 0 是通过海运方式来实现的，集装箱运输在各种海运方式 第1 章绪论 中发展最具活力，这无疑会给我国集装箱运输业带来新的发展机遇，提供充足的 发展空间。近十几年来，在外贸新一轮高速增长、集装箱化率提高和集装箱码头 建设加速三大因素的推动下，中国集装箱市场空前繁荣。2 0 1 0 年，世界码头集 装箱吞吐量达到4 亿多t e u ，其中亚洲地区码头集装箱吞吐量占全球市场份额 由2 0 0 0 年的4 7 5 上升至6 0 ，而中国是主要业务增长点和最大的集装箱货源 生产地。 随着我国对外贸易的持续增长，集装箱运输量保持着较高的增长速度，2 0 0 0 年我国集装箱吞吐量为2 3 5 0 万t e u ，而到2 0 0 8 年1 至1 1 月，全国主要码头累 计完成国际标准集装箱吞吐量1 1 5 7 8 1 6 万t e u ，增长了近6 倍。此外，根据韩 国贸易协会最新公布的“2 0 1 0 年世界十大集装箱堆场吞吐量 数据显示，得益 于欧美经济复苏和国际海运中心建成，上海的吞吐量同比激增1 6 3 。而新加坡 所依赖的中转货增幅下降，吞吐量仅增加9 9 。上海港国际标准集装箱吞吐量 2 0 1 0 年已达2 9 0 7 万t e u ( 国际标准箱单位) ，超过新加坡港，成为世界第一。2 0 1 0 年世界十大集装箱码头中中国占6 个，除上海港外，香港2 3 6 3 万t e u 位列第3 位，深圳2 2 5 1 万t e u 位列第4 位，宁波舟山1 3 1 4 万t e u 位列第6 位，广州 1 2 1 2 万t e u 位列第7 位，青岛1 2 0 1 万t e u 位列第8 位。报道称，2 0 1 1 年，上 海和新加坡的集装箱吞吐量有望再创新高，突破3 0 0 0 万t e u 。而深圳很可能取 代香港，成为世界第三，天津则有望跻身前十。 1 1 2 集装箱支线运输的发展现状 随着世界经济的一体化，世界航运界的大型集装箱船舶发展迅速，集装箱运 输船舶愈来愈趋于大型化或超大型化，如巴拿马船；同时，人们对现代物流业的 要求越来越高，“门到门 服务的需求也越来越强烈，但是大型的干线集装箱船 舶只能靠泊大型码头，一些小的港口就无法停靠，然而支线船舶却可以停靠一些 零散和小型的码头，故此可以将很多分散在小码头的货物也链接进来，起到了衔 接支线码头和干线码头两个端点的作用，如此“门对门”的运输方式不仅充分满 足了货源的广泛性，而且保证了现代物流与供应链的需要。因此集装箱支线运输 因此取得了蓬勃的发展 3 i 。 与此同时，在船舶空箱调运中，支线运输也具有不可替代的地位和优势。因 为干线船舶的航线设置没有支线船灵活多样，对局部地区的航线规划劣于支线船 2 集装箱支线运输班轮航线规划与配船问题研究 舶，故此在某些指定航线的空箱调运中，支线运输就以其业务集中，工作范围相 对较小的优势获胜，另外，支线船因为其营运方式相对灵活，航线本身较多较短， 使其在舱位的分配上具有更大的灵活性，而不是像其他大型集装箱船舶由于停靠 的码头相对固定，船舶在舱位分配上往往有较固定的方法，如配载空箱，会很大 程度上限制重箱的配载【4 】。 支线运输不光在枢纽港和广阔的腹地之前的货物流通，也体现在枢纽港和喂 给港之间的货物运输，从而帮助干线船舶较高的箱位利用率和大量的货源，提高 了干线船舶的经济效益。 再者，支线船具有的船型吃水浅，而且对码头的装卸设备要求也相对较低， 这使得支线船不仅能在内陆的众多河道中被充分利用，而且也使支线船在内陆码 头的装卸作业变得更灵活更具有适应性。 最后，支线小型船舶具有灵活的航班，可以为大型枢纽港船舶保证准确的船 期。 综上所述，集装箱支线运输在整个航运中起到了不可替代的作用，有着相当 不错的发展前景。 集装箱支线运输的竞争性越来越强烈，如果政府能有一个专门的组织机构来 对这些船公司之间进行统一的管理和协调，那么将很大程度上将防止恶性竞争。 这个组织机构还能够对船公司及货主和港口企业还有一些陆岸单位之间进行统 一的协调管理，加强它们之间的合作，明确自己的分工，在经济效益的划分上达 到共识，同时，对港口的建设、船公司的航线规划还有一些地方企业的管理都能 提出一些意见，能够有效促进集装箱运输的发展。 1 1 3 集装箱大型化对支线运输的需要 随着集装箱运输量的增加，全球投入运营的超大型集装箱船舶日益增加，使 得集装箱船舶大型化趋势日益明显【5 1 。 航交公报统计资料显示，从1 9 5 6 年第一艘改装集装箱船到今天的万箱集装 箱船出现，仅仅用了半个世纪的时间，航运业就完成了历史性的突破，集装箱运 输工具实现了质的跨越发展。到上个世纪7 0 年代，统一的集装箱规格标准出台 以后，集装箱班轮运输行业的发展更是如日中生，集装箱船舶大型化速度更是令 第l 章绪论 人叹为观止。 上世纪6 0 年代中期建造的集装箱船，最大载箱量均不到1 0 0 0 聊；7 0 年代， 航运公司开始建造第二代集装箱船，在1 0 0 0 t e u 以上；8 0 年代初期，又建造了 3 0 0 0 t e u 的集装箱船舶，为适应环球航线之需，充分利用巴拿马运河的通航能 力，将船宽为3 2 2 米的船型定位巴拿马型集装箱船；8 0 年代末期，4 3 4 0 t e u 型 “杜鲁门总统 号超巴拿马型船舶也被建造出来；9 0 年代中期，集装箱载箱量 已经可以达到5 0 0 0 , , 6 0 0 0 t e u ；2 0 0 0 年以后，又出现了6 6 7 4 t e u 型“南安普敦 号和7 6 6 0 t e u 型“马土基君主号集装箱船，在新世纪的头1 0 年时间里，从 8 0 0 0 t e u 到1 2 万t e u ，再到今天的1 8 万t e u ，集装箱船载箱量更以惊人的速 度增加。 集装箱船大型化会带来一些的问题，所以大型化对支线运输的需要主要体现 在以下几个方面： ( 1 ) 完整庞大的物流运输体系对支线运输的需求 随着国际贸易的发展，人们对于服务水平要求的越来越高，船公司要提供“点 到点 的货物运输，才能从更大程度上满足货主的要求。然而大型集装箱船舶一 般都在干线上运输，而且只能靠泊大型的集装箱码头，对码头的装卸作业水平要 求也较高，国内一些小型码头的设施还不够现代化和大型化，不能停靠大型集装 箱船，所以很难将货物运送到“家门口，这个时候，支线运输就起到了不可替 代的作用【6 】，支线船舶不仅吃水相对较浅，而且对码头的靠泊水平和装卸作业要 求也较低，更适合在国内广泛的河道中运输货物，所以支线船能够将大型深水码 头和国内一些小型零散的码头链接起来，干线船和支线船的结合，形成了一个完 整且庞大的物流运输体系，真正实现“f - j n f - 1 的货物运输。 ( 2 ) 集装箱箱位利用率对支线运输的需求 随着集装箱船舶的越来越大型化，一艘大型集装箱船舶能够承运的集装箱数 量也增多，如何能使这些集装箱都能装入货物，避免空载的情况发生，提高集装 箱率将是个迫切需要解决的问题。提高集装箱箱位利用率就是要有大量的货源， 大型集装箱码头只靠泊几个大型港口，虽然港口有广阔的腹地，但是没有支线船 的运输，也无法将腹地的货物运送到干线港口【7 1 。不形成一个广阔的物流运输网 络，将无法保证货源的充足，这些都是仅仅依靠干线船无法做到的事情，可见， 集装箱支线运输班轮航线规划与配船问题研究 支线运输在保证干线船舶箱位利用率上起到了重要作用，是枢纽港和喂给港，干 线港与支线港之间的纽带。 ( 3 ) 准班率对支线运输的需求 衡量船公司集装箱班轮运输是否可靠的一个重要标志就是准班率是否高【g 】， 就是能否严格按照船期表所公布的时间进行运输，否则，班轮如果经常误航，则 很容易导致货主的反感从而选择其它船公司。但是由于船舶越大型，往往更难于 驾驶，更难以保证准确的船期，这个时候支线船就发挥了重要的所用。当干线船 在靠泊深水码头时误了点时间，就可以灵活调动支线船，让支线船提前进入营运 状态或者加快航速，这样既保证了准班率又节约了成本，更重要的是，保持住了 公司良好的形象，为以后获得更多的货主的信赖打下了坚实的基础。 ( 4 ) 空箱调运业务对支线运输的需求 随着船公司拥有的大型集装箱船舶越来越多，所拥有的空箱也越来越大，越 来越多，空箱会占用很大的空间面积，而且频繁地对大型空箱进行调运也会增加 班轮公司的成本。支线船舶能够挂靠的港口多 9 1 ，航线多而且灵活，能够帮助干 线船进行空箱的运输工作。同时由于集装箱班轮行驶在固定的航线，靠泊固定的 港口所以船上箱位都是根据港口装卸作业情况设置的，不具有灵活性，如果配载 空箱，将会限制重箱的配载，从而影响箱位利用率，而支线船舶由于靠泊港口较 多，所以箱位的分配也比较灵活，能够提高箱位利用率。同时当境外船舶靠泊国 内港口的时候，如果由国内支线船进行空箱的调运，就能够省去很繁琐的手续问 题，如此看来，支线船在国内空箱调运中具有不可替代的地位，是干线船所做不 p 到的【1 0 1 。 1 2 国内外研究现状综述 从上个世纪六十年代起，许多专家和学者就开始对国际集装箱班轮航线规划 及配船【l l 】进行研究，最初是在参照油轮和散货船的模型的基础上进行研究的，但 是并不能反映全部集装箱班轮运输的特点，不过到目前为止，集装箱班轮航线规 划及配船的研究已经一步步走向了成熟。 很多学者对航线规划和航线配船问题进行了研究，因为这个问题不仅在很大 程度上影响了集装箱班轮公司的竞争水平，而且也关系到了集装箱班轮公司和港 第1 章绪论 口管理单位等各方的成本与经济效益问题。对于航运公司来说，如何有效规划航 线，并合理配船是研究工作的重中之重【1 2 1 。 1 2 1 航线规划 对于班轮航线规划问题，c h o 和p e r a k i s ( 1 9 9 6 ) 1 1 3 】针对船公司的船队规模和 班轮航线优化提出了一个线性规划模型。b e n d a u 和s t e n t ( 2 0 0 1 ) t 1 4 】针对某一集装 箱支线运输的实际配送任务，设计了一个混合整数模型，目标函数是所用船舶数 量最少，利润最大。p e r a k i s 等人1 5 】也对航线规划进行了研究，所使用的方法是 线性规划和混合整数规划方法等。靳志宏等( 2 0 0 5 ) 【1 6 1 建立了一个集装箱支线 船路线优化问题的混合整数规划模型，并设计了近邻搜索和禁忌启发式算法求解 模型。针对上述问题，孙晓娜和李娜( 2 0 0 6 ) 1 7 】设计了一个新的免疫遗传算法。 1 2 2 航线配船 对于班轮航线配船问题，p o w e l l 和p e r a k i s ( 1 9 9 7 ) t 1 羽在给定路线、服务频率 和船期表的前提下，建立了整数规划模型优化配置现有船队。m o u r a o 等( 2 0 0 2 ) t 1 9 】 针对支线运输，在已知航次上的配船问题建立了整数线性规划模型，用m s e x c e l s o l v e r 进行求解。 苏绍娟( 2 0 0 7 ) 【2 0 】运用粒子群算法，避免了粒子群算法出现的早熟情况，建立 了不确定性的航线配船模型。苏绍娟( 2 0 0 8 ) 【2 1 】结合了实际航运市场的现状，利用 不确定性规划求解的方法，对动态船舶运输进行了规划。 杨秋平等人( 2 0 0 9 ) 瞄1 运用线性规划方法，建立了航线配船的目标函数，以追 求利润最大化为目的，改变了以往函数模型的实用性较低的问题，该模型根据船 公司所经营的航线上的运量，选取船队的某一时间点作为起始点，预测这个船队 在一段时间内的船队规划和配船问题，利用v b 和f o r t r a n 语言进行编程求解， 得到了较好的运算结果。 谢新连教授【冽全面地介绍了船舶运输管理与经营基础知识，建立了混合整 数和连续变量的两种线性模型，将线性规划和非线性规划结合起来，在确定的航 线和已知运量的前提下，考虑了船队新老交替即旧船淘汰和购入新船等改变船队 结构的情况下，建立了以船队总成本最低的目标函数的线性规划模型。本模型改 变了以往用手工计算的局限性，改用计算机进行计算，但是由于当时计算机应用 集装箱支线运输班轮航线规划与配船问题研究 水平并不高，所以还是无法应用到实践中。虽然这些研究在理论上都是成功的， 但是由于其复杂性都很难应用到实际的生活工作中，而且不是专业人员很难学习 和理解，更别提应用到实践中了。 因此，本文针对传统航线配船和船队规划方法难以应用于实践中的问题，引 入遗传算法，建立了航线配船与船队规划数学模型，旨在推动该领域研究的实用 性。 1 3 本文研究的主要内容及研究思路 本文是以集装箱支线班轮航线规划与配船问题为研究目标，对集装箱支线班 轮航线规划与配船问题进行了比较分析，在现实约束条件以及一定的假设条件下 进行建立了非线性规划模型，并利用组合遗传算法进行求解，最后通过实例进行 验证计算，并通过与禁忌搜索法进行比较，得出比禁忌搜索法效率略高的结果。 第1 章为绪论主要介绍本文的研究背景，国内外研究现状以及本文的主要研 究内容。 第2 章主要介绍了集装箱支线运输和班轮运输的概述，介绍了集装箱班轮运 输的特点、营运方式。再介绍了集装箱班轮运输航线规划的一些基础理论，包括 航线的布局形式、班轮挂靠港的确定、航次组织的经济比较、班轮船期表的编制、 航线班期方案的拟定。最后介绍了集装箱班轮航线配船的一些理论知识，包括配 船方法、航线配船方案的选择问题、集装箱班轮航线配船的特征、航线配船的相 关特性分析。 第3 章详细介绍了本文用到的算法即遗传算法的一些基础理论知识和方法。 第4 章建立了集装箱支线班轮航线设计与配船的联合优化混合整数规划模 型。并设计了组合遗传算法。以中国华南地区和珠江三角洲集装箱支线运输的一 个实际案例作为算例验证模型和算法的有效性。 第5 章为本文的结论，并对下一步工作进行了展望。 本文的研究思路如下所示： 第1 章绪论 1 4 本文的创新点 在以往的文献中，航线优化和航线配船问题都分别被探讨，两个问题都是处 于独立的状态，但是本文将航线优化和配船问题联合起来一起进行优化和求解， 使航线方面的研究更符合实际情况，也更能为船公司提供解决此关键问题的方 法。 集装箱支线运输班轮航线规划与配船问题研究 第2 章集装箱班轮航线规划及配船理论 2 1 集装箱班轮运输概述 在国际上，船舶的运营方式有两种，一种是集装箱班轮运输，又被称为定期 船运输，另一种就是租船运输，也称为不定期船运输。 班轮运输是指船舶在固定的时间，按照对外公布的船期表，停靠固定的码头， 按照固定的航线进行船舶运输，一般以运输集装箱杂货和客运较多。但是正是由 于班轮运输的准班准点性，所以即使在低载货率的情况下，即船舶没有装满货物 或者人的情况下，也要按照既定的时间出发，如果在遭遇大风、大雾等特殊天气 情况下，要提前及时地通知货主或者旅客，做好延班停航的工作。 班轮船舶多为杂货船、多用途船、集装箱船和客滚船，以集装箱船、多用途 船和普通杂货船为主，杂货船只承担一些近海少量的运输任务，大部分的任务都 是由集装箱船完成，客滚船一般承担短距离海上客运运输，例如大连烟台，大 连威海，大连一天津航线。 ： 2 1 1 集装箱班轮运输的特点 ( 1 ) 班期的准确性 由于班轮运输的船期表都是对外公布的，而且，班轮不可能只运送一位货主 的货物，它是为众多货主提供服务的，所以必须按照船期表定时开航，因为对于 班轮公司，决定其信誉的好坏的一个最重要因素就是班期的准确性，班轮船舶要 按照船期表，定时开航，定时靠航，即使出现特殊情况不得不延航或者停航的情 况，必要时要事先跟货主进行沟通协调，不能擅自做决定。所以对于班轮公司， 班期时候准确将决定了一个公司的竞争水平【2 4 】。 ( 2 ) 以航线为基准，从事船舶管理工作 因为班轮都是在固定航线上行驶，故每个航线之间产生的影响比较少，因为 每个航线都有自己的特点，船公司会根据此航线的具体情况如水文，航距，载货 情况来安排船舶，以取得经济效益的最大化，在正常情况下不会轻易改变航线和 船队，以免使经济效益造成损失。一些大的班轮公司虽然一般经营不止一条航线， 但是各航线之间都是独立的，所以对这些航线的船舶的管理可以是独立的【2 5 】。 ( 3 ) 运输费用相对固定 第2 章集装箱班轮航线规划及配船理论 因为航线一旦确定，航距和港口都会随之确定，故产生的燃油费、港口使费 等等差不多都是固定的数据幽，只有那些随着载货量不同而产生一些不同的费 用。所以每个航次的费用基本上都是固定的，没什么变化，所以公司的收入主要 由运价来决定，即所有货主所支付的费用的总和。 ( 4 ) 船公司一般具有较强的经济实力 船公司因为在固定航线上进行船舶运输，因此不仅要在此航线上分配一些船 舶，而且要严格按照船期表进行开航，为了揽货，也应该保持一定的发船频率， 而且要与始发港、途径港和目的港的港口公司做好协调，对相应的码头费用要进 行约定，故此在此航线上的投入就比较大【2 7 1 。而且随着班轮公司竞争日趋白日 化，班轮运输又有强烈的排外性，所以当货源不充足的时候，要么在竞争中对此 航线达到垄断，统一价格，要么就是互相恶性竞争，互相压价，最终的结果只能 是大幅度降低船公司的经济效益。 ( 5 ) 高度要求组织运作的协调性 集装箱船舶不同于一般的杂货船或者客滚船，它对组织运作提出了较高的要 求，比如，干线与支线、船舶靠泊时与码头之间的协调，码头与岸桥、岸桥与堆 场之间、海上与陆上的协调等等都会很大程度上影响到集装箱运输的效率，如果 其中有一项流转不通畅，都可能无法达到货主要求的收货时间。 ( 6 ) 营运期限长，基本没有可能退出营运 班轮公司一般拥有一些固定的货主，而且这些货主都是通过船公司长期的努 力争取来的，所以班轮公司想要在某条航线上形成竞争优势，是一件很不容易的 事情，所以为了保住这块金字招牌，船公司必须按照船期表定时开船，并且保证 服务质量，既使是货不满舱，经济效益不好，也不能在航线上退出，只能通过各 种手段多揽货，多增加竞争实力来挽回损失。 ( 7 ) 船公司管理人员众多 班轮公司因为拥有的船舶数量大，航线固定，所以需要揽货、管理的人员就 很多，通常班轮公司会在始发港、途径港口和目的港都设置办事处，以方便进行 本公司的业务操作，所以相应的费用支出也比较多。 2 1 2 集装箱班轮航线的营运方式 航运公司通过整合调配集装箱船舶，从而达到航线运营的目的，这种方式方 集装箱支线运输班轮航线规划与配船问题研究 法就是集装箱航线的运营方式，国际集装箱航线的运营方式是按照舱位经营权和 船舶投入方的组成来划分的【2 8 】，有以下三类：独立运营、联合运营以及战略联 盟 ( 1 ) 独立运营，顾名思义就是指只有一家船公司投船经营某一条航线的方式， 一般是超大型的航运企业，因为自身资金雄厚、规模庞大，只靠自身的能力就可 以进行市场营销从而保证船舶的装载率，这样可以保证该船公司的航线独享优 势，比如说交货期和挂靠港的灵活性等，但是在降低风险方面，要弱于其他两种 运营方式。 ( 2 ) 联合运营，就是指有大于一家的船公司一起来经营某一天航线，它在现 实中是最常见的，集装箱运输行业的风险非常大，如果仅仅靠一家船公司的力量 与市场走势抗衡的话，是很艰难的，而联合经营可以降低网络铺设成本，增大航 线覆盖面以及扩大服务频率，所以大部分的集装箱航线都是这种联合经营的。共 同派船、舱位购买以及舱位互换等形式是联合经营的内容，每种形式各有优缺点， 但是在降低成本和增加收益上却都是很有效的，下面对这三种形式做一下简要介 绍： 共同派船例，就是指每个船公司都派出一艘船航行在某一条航线上，运 营的时候，即可以是每家公司各自经营自己的船舶也可以是由其中较有实力和经 验的船公司统一负责经营。很多船公司都想进入某一航线市场进行营运，但是一 般都因为自身的运力而受到显著，不能一下投入所有的船舶，那样风险会很大， 而各家船公司一起合作，联合经营某一条航线的话，那么每一家公司的投入较少 但是却拥有了整条完整的航线，但是其中也有不足，就是各家的船舶型号不一致， 所以每周的舱位量会有较大的变动，另外，每家公司挂靠的码头也可能不一样， 从而阻碍了中转货物的安排设置，最后，如果有突发事故，比如海损、船舶脱班 或是突发淡季，某一家船公司就会自己临时调整航路或挂靠港的顺序，这样对双 方的合作会产生一定的影响。 舱位互换，是在各公司独立投船经营航线的前提下，为了达到航线覆盖 面积的增大，航线服务频率的增密，按照一定的舱位成本比例，互相交换一部分 的舱位，当在航线货物流向比较散的时候，效果会很显著。一般航线上的港口较 多，不可能挂靠到航线上的所以港口，一般是船公司会挂靠自己有优势的港口， 第2 章集装箱班轮航线规划及配船理论 再通过舱位互换的方法把其他挂靠港给其他船公司来挂靠，不足的地方是，和互 换舱位的船公司其实也是竞争对手，因为和自己互换的船公司也会在自己的直航 港口进行服务。 舱位购买，是指船公司本身不投入船舶运营，而是通过向其他有船的公 司购买舱位，来达到运营的目的，采取这种形式的船公司一般是新进入某一航线， 不熟悉市场而采取的试探阶段，或者是公司在这条航线的经营遇到很大的困境， 而将自有船舶撤出，或是该公司被限制进入某一条航线，由于政治或是码头自身 的因素。如果航运市场比较火爆，船公司很少会把舱位卖给对竞争手，如果是运 输量很少的淡季，短期的舱位买卖才会成为可能。 ( 3 ) 战略联盟，是指大于一家的船公司一起经营航线，并且使区域拓展和运 价政策要统一，它的基本特点是，若想独立运营某一指定航线，需要经过同盟委 员会批准，但是与委员会会员以外的船公司合作运营，需要经得委员们的许可， 在新开设的航线运营时，只限会员与会员间的合作。 2 2 航次规划的相关理论概述 2 2 1 航线的布局方式 集装箱班轮运输的航线有很多种布局方式：即传统多港口挂靠航线；干线配 支线船航线；多角航线；单向环球航线；小陆桥航线及大陆桥航线等。 ( 1 ) 多港口挂靠航线方式多用于传统的杂货散货船，它的意思就是一艘船舶 在一次航行中多次挂靠不同的港口，不过现在集装箱班轮挂靠港口的数量明显比 以前的少了，跟集装箱船舶大型化和支线运输的迅速发展有直接的关系。 ( 2 ) 干线配支线船航线方式是指干线船舶只挂靠几个大型的枢纽港口，而小 型的港口就由支线船舶来靠泊，这样干线船和支线船舶相结合起来，就形成了完 整的船舶运输网络。干线船通常因为体积大，吃水深，在港口停泊时收取的停泊 费用也高，同时因为箱位多而且大，所以对港口的装卸水平要求也高，所以为了 减