基于网络单纯形法的海运集装箱空箱调运研究＊

黄纯辉 张庆年 周兴建 刘春玲

（武汉理工大学交通学院1） 武汉 430063） （武汉纺织大学供应链系统研究中心2） 武汉 430073）

集装箱空箱运输产生的本质是由于货物运输的不平衡，所以，不同的港口对于集装箱空箱的需求量就不一样，集装箱空箱的存在，不仅有运输成本问题，而且还存在港口库存问题，所以，对于集装箱班轮公司而言，海运集装箱的合理调配既是满足公司正常运输生产的需要，也是在集装箱班轮运输市场上同竞争对手竞争的需要［1］.

本文结合海运集装箱调运的现状，以集装箱空箱运输成本最低的思想，建立相应的模型，对目前海运集装箱空箱调运过程中成本居高不下的实际问题进行理论上的探索.

1 国内外相关研究

1.1 国内关于集装箱空箱调运的研究

施欣［2］结合对集装箱海运空箱调运过程的剖析，建立了相应的系统优化模型，进行了系统仿真.刘恒江等［3］以航线经营人为主体，对集装箱空箱调运系统（CAE－CS）进行了分析，构建空箱调运的Petri网模型，然后利用EXSPECT仿真软件进行模拟仿真，证明利用Petri网分析和解决空箱调运问题的有效性.周红梅等［4］借鉴了铁路空车调度优化模型的研究，建立了海运集装箱空箱调运优化模型.刘大镕等［5］构造了基于机会约束规划的陆上空箱调运模型，把需求分为确定性需求和随机性需求，从而考虑了需求的不确定性，并提出了在单箱情况下处理不确定数据的有效方法，但该文把空箱供给看作一个已知量，从而消除了空箱供给的不确定性.

1.2 国外关于集装箱空箱调运的研究

Cranic等［6］描述了这类问题的基本结构和主要特点；接着提出了2个单箱种和多箱种的动态确定性模型，为这类问题提供了一般的建模框架；最后在此基础上提出了单箱种情况下处理供给和需求不确定性的数学模型.White［7］首先利用运输规划理论开展空载运输工具优化调配研究.他们通过构造一个空间时间模型来描述现实中的集装箱空箱调运问题，并给出了诱导式网络流算法及相应的计算例子，对时间段内的空箱调运方案进行优化，其时间间隔是不确定的，研究的结论是非常可取的.

2 基本模型

2.1 模型的构建

令O（k），k∈K代表起运地的集装箱空箱k，其中K为不同类型的集装箱空箱；D（k），k∈K为目的地的集装箱空箱k；T（k），k∈K为转运地集装箱空箱k，i∈O（k），k∈K，集装箱码头i对集装箱空箱k供应量，i∈D（k），表示集装箱码头i对集装箱空箱k的需求量；uij，（i，j）∈A为弧（i，j）的容量（即弧（i，j）能承担的最大运量），（i，j）∈A为在弧（i，j）集装箱空箱k的最大运量；变量，（i，j）∈A，k∈K为集装箱空箱k在弧（i，j）的运量；），（i，j）∈A，k∈K为弧（i，j）运输单位流量集装箱空箱k的成本.

多种集装箱空箱最小成本的模型

目标函数（1）是总的费用，约束条件（2）是对集装箱码头i∈V和每一类货物k∈K的运量限制.约束条件（3）表示每一类货物k∈K通过每一条弧（i，j）的流量不超过容量.约束条件（4）（流量约束），表示对于每一条弧（i，j）∈A，通过弧（i，j）的总运量不大于运量.

对于任意的，k∈K，i∈O（k）和，满足下面的条件

否则问题是行不通的.

虽然集装箱有不同的类别，但是班轮公司使用的集装箱大部分仍然是普通集装箱，又称干货集装箱（dry container）以装运件杂货为主，通常用来装运文化用品、日用百货、医药、纺织品、工艺品、化工制品、五金交电、电子机械、仪器及机器零件等.这种集装箱占集装箱总数的80%以上［8］.鉴于此，在实际应用中，构建单集装箱空箱线性最小成本流模型.根据上述多种集装箱空箱线性最小成本流的原理，构建下面单集装箱空箱线性最小成本流问题模型，同时，为了便于后面相关算例的验证，模型必须满足如下假设.

假设1 相同航线上几家独立的集装箱班轮公司，在航线和航期表固定、一定计划周期内所有航班都正好完成1次运输、每航次的货船容量（即重箱运输量）已知的情形下，开展单箱种（20ft）空箱的调运.

假设2 计划期开始时各港口空箱的供给量和需求量已知，且据此可确定本期的供给港和需求港.

假设3 当客户对空箱的需求仅仅依靠调运已不能满足时，班轮公司将从集装箱租赁公司租用空箱，这些空箱在任何时间、任何港口都没有数量限制，并且能够即刻得到.

假设4 班轮公司在各航线上的空箱运输费率、在各港口的租箱费等成本参数已知.所假设公司各方面情况接近且计划期长度有限.因此认为在特定港口的同一计划期内租箱费用相同、恒定.

集装箱空箱线性最小成本流问题模型，可以通过网络单纯形算法或其它的线性规划算法来求解.

2.2 网络单纯形法算法步骤

步骤1找到一个初始的基本合适的结果x（0）.设h＝0.

步骤2确定与x（h）相关的减少成本cr（h）.

步骤3如果≥0，（i，j）∈A，停止运算，x（h）就是最优的结果；否则，选择变量xvw使xr（h）vw＜0.

步骤4从基础变量中选择一个变量xpq，是xpq作为替代xvw的中间变量；令h＝h＋1，返回步骤2.

3 算 例

某公司是一多试联运承运人，当客户将货物从起运地运至目的地时，该公司提供一个或多个空集装箱来装货.一旦到达目的地，货物卸下，空箱运至新接货点的客户.该公司的管理只需要周期性的重新分配空集装箱（实际中是1周1次）.空箱的运输费用是很高的（是总的运作费用的35%）.几十个空的20ft的标箱需要在港口1、港口2、港口3、港口4、港口5、港口6、港口7进行调运.各个码头的空集装箱的数量和需要的数量和运费，见图1.

图1 空箱问题的代表图

图2 某公司空箱分配问题的最优解

基于运用网络单纯形法的理论，结合lingo数据包的计算，最优的结果可以在图2中获得，图中虚线部分表示没有集装箱空箱运输，实线部分表示有空箱运输.具体的空箱流见表1.可以明晰的看出各种港口之间集装箱空箱的流量.根据各港口之间的空箱流，可以得出最优解是3 900，即最小运输成本是3 900.

表1 某公司集装箱空箱分配问题的求解值TEU

4 结束语

基于网络线性规划的海运集装箱空箱调运优化模型，解决了集装箱班轮运输公司在不同的时期内，在不同的港口之间集装箱空箱的调运成本最低的问题，所以其也是基于时间延迟的动态模型，本文建立了多种集装箱空箱的调运成本最低的模型，所列举的算例验证了同一种集装箱空箱调运成本最低的优化模型，虽然做了一定的简化处理，但是仍能证明海运集装箱空箱调运优化定量分析的可操作性.

［1］Crainic T G.Long－haul freight transportation，In：hall，R.W（Ed.）［M］.Handbook of Transportation Science，Kluwer Academic Publishers，Norwell，MA，2003.

［2］施 欣.集装箱海运空箱调运优化分析［J］.系统工程理论与实践，2003，23（4）：70－89.

［3］刘恒江，施 欣.基于Petri网的集装箱空箱调运仿真分析［J］.交通运输工程学报，2002，2（3）：97－102.

［4］周红梅，方 芳.航运集装箱空箱调运优化模型的研究［J］.武汉理工大学学报：交通科学与工程版，2003，27（3）：384－387.

［5］刘大镕，贺 斌，蒋良奎，等.随机（单箱种）陆上空箱调运模型［J］.上海海运学报，2000（3）：8－18.

［6］Cranic T G，Gendreau M，Dejax P.Dynamic and stochastic models for the allocation of empty container［J］.Operations Research，1993，41（1）：102－126.

［7］White W W，Bomberawlt A M A.Network algorithm for empty freight car allocation［J］.IBM System Journal，1969，15（2）：147－16.

［8］史艳秋.迅速发展的中国集装箱工业［J］.铁道货运，2005（11）：11－14.