多式联运选择的规划模型

多式联运选择的规划模型

1时效物流与传统运输方式的争优势随着经济贸易一体化，流通中的竞争已经成为原材料竞争的重要组成部分。公司能否快速响应市场，采用zet物流模式，为市场提供必要的质量和廉价产品，是实现竞争优势的关键。时效性物流对物流响应速度具有高度敏感性,运输作为物流重要的一环,运输方式选择在其流通过程占据非常重要的地位。由于各种运输方式的技术经济特点不同,在一定范围内运输成本与运输时间及物流响应速度具有效益背反规律,即满足时效性会导致运输成本增加,减少运输成本的措施可能降低物流响应速度,所以承运人在运输方式选择时必须在运输成本与物流响应速度之间取得平衡,在满足时效要求的约束下通过运输方式的组合优化来降低物流成本。2运输方式选择联合运输是综合运输的主要实现方式,是当前国际研究的热点,它是在环境、能源、交通拥挤的约束下交通运输研究的新领域,目前在许多方面已经形成共识。欧洲运输部长会议(ECMT)将其定义为:装在同样货柜里(如拖车或集装箱)的货物至少经过两种运输方式运送,货物在转运过程中没有经过拼装和卸货,主要的运输行程是通过公路、铁路、航空及河运、海运来完成,实现多种运输方式联合的门到门或点到点运输。运输方式选择是联运研究的重点,学者们对此展开研究,但大部分是以统计资料进行实证分析。Clarke研究说明运输频率或服务频率对运输方式的选择影响最大;Morash对美国货运市场进行研究,结论显示制造产品更多接受驼背及集装箱运输(TOFC-COFC)方式联运;Nierat以运输成本最小确定公路运输及公铁联运的市场范围及其影响因素;张得志、凌春雨建立了带时间窗和能力约束的运输模型;Zlatoper与Austrian研究了在运价和运输质量变化时运输方式选择的敏感性;Harper等研究显示,不同成本/质量是托运人选择运输方式的决定性因素;Haugen与Hervik从拥挤成本的角度出发建立承运人选择运输方式的博弈模型;VAN研究显示,考虑到交通拥堵,大多运输从业者愿意选择联运。纵观这些联运方式选择的研究文献,多从实证或定性的角度出发,缺乏量化的选择方法,而且缺乏对运达准时性的考虑。本文试图从理论上寻找联运的运输方式选择方法,这种运输方式的选择可以满足时效性物流(JIT物流)的要求,对运输速度和物流成本进行优化。为此,本文建立了以物流费用最小化为目标的0-1规划模型,通过模型的求解来寻找满足时效要求的最佳联运方式。3扩展运输选择方式一批货物欲从出发点O运达目的地D(见图1)。途经的物流通道内有m个节点(城市或交通枢纽),每两个节点之间都有n种运输方式可供选择(公路、铁路、航空、水运4种基本运输形式可根据班线扩展运输选择方式。如公路可以选择收费公路,费用高,但速度快;也可以选择不收费公路,费用低,但速度慢;铁路、航空可以选择不同的班次和车等),每个节点都可实现货物在不同运输方式之间的相互转载。由于物品对运输时间的敏感性,不同时间和不同运输方式到达目标市场,其运输及仓储成本不同,过早到达会产生仓储费用,过晚到达会产生惩罚成本(如腐烂、变质、违约赔偿等)。所以承运人就会从不同运输方式中组合优化自己的运输方式,在不同节点之间选择不同的运输方式,达到自身物流费用最小的目标。4模型设计4.1模型假设假设1货物在各个节点最多进行一次转载。假设2两节点之间只能用一种方式运输。4.2第l种运输方式的运输成本xli,i+1li,i+1∈{1,0},1表示节点i和i+1之间利用第l种运输方式,0表示用其他方式;yl,kil,ki∈{1,0},1表示在节点i由第l种运输方式转换到第k种运输方式,0表示不进行转载;cli,i+1li,i+1为在节点i和i+1之间,第l种运输方式的运输成本;el,kil,ki为在节点i由第l种方式转换到k种方式的转载费用,包括装卸、搬运以及与等待时间成正比的仓储费用等;hli,i+1li,i+1为第l种运输方式在节点i和节点i+1之间的运输时间;ol,kil,ki为在节点i从第l运输方式转换到第k种运输方式的转载时间,包括装卸、搬运及等待的时间;wli,i+1li,i+1为在节点i和节点i+1之间第l种运输方式的车辆装载容量;Q为待运输的货物总量;s为单位库存成本;dt为仓储成本;ft为超过合约期限而产生的惩罚成本,f为每单位时间的惩罚值;为合约约定的货物到达期限;t为货物实际运达时间。4.3物流运输成本dtΖ=min(∑i∈m∑l∈nxli,i+1cli,i+1+∑i∈m∑l,k∈nyl,kiel,ki+dt+ft)(1)Z=min(∑i∈m∑l∈nxli,i+1cli,i+1+∑i∈m∑l,k∈nyl,kiel,ki+dt+ft)(1)∑i∈mxli,i+1=1,l∈n(2)∑i∈mxli,i+1=1,l∈n(2)∑l∈n∑k∈nyl,ki=1,i∈m(3)∑i=m(xli,i+1hli,i+1+yl,kiol,ki)=t(4)dt={(a-t)s,t≺a0,t≥a(5)ft={0,t≤b(b-t)f,t≻b(6)Q·xli,i+1≤wli,i+1,i∈m,l∈n(7)xli,i+1,yl,ki∈{1,0},i∈m,l,k∈n(8)hli,i+1,ol,ki,wli,i+1,Q,ci,i+1,el,k,t,s,f,dt,ft≥0(9)目标函数(1)是最小化物流成本,即运输成本、转载成本(装卸、搬运、仓储)、仓储成本及延期运达的惩罚成本之和;(2)式表示货物不能分开运输;(3)式表示在每个节点货物最多只能进行一次转载;(4)式表示运输时间及转载时间之和就是货物的运达时间;(5)式表示仓储成本;(6)式表示惩罚函数;(7)式表示运输工具运量约束;(8)式和(9)式表示变量非负约束。4.4节点之间的运输方式选择模型中所求变量为xli,i+1在i=1,2,…,m-1时取值为1的组合,也就是在各节点间运输方式的组合。由各个节点值为1的运输方式组成的解可以看作是一个向量:X=(x1,2,x2,3,x3,4,…,xm-1,m),其中xm-1,m表示在m-1和m节点之间运输方式选择结果。如X=(2,5,7,…,6)表示在节点1和节点2之间采用第2种运输方式,节点2和节点3之间用第5种方式……,最后两节点之间用第6种运输方式。这样由m个节点n种运输方式组成的物流通道,运输方式选择的组合个数为(m-1)n,也就是模型中解的个数为(m-1)n。该模型属于混合整数规划问题,在规模较小时可以利用分支定界法或者随机搜索的方法求解,但随着规模的扩大,不仅模型解的搜索空间急剧扩大,而且需要两两比较(m-1)n个解的物流成本及运输时间,所以目标函数计算过程也非常复杂。此问题属于NP-complete问题,这类问题有时在目前的计算机上用枚举法很难甚至不可能得到精确最优解,而遗传算法是一种强大的随机搜索方法,是寻求这种满意解的最佳工具之一。5遗传计算方法的模型解5.1节点的运输方式基因根据以上对解结构的分析,模型采用自然数编码,将所有可选运输方式分别用自然数表示,如1表示第一种运输方式,依次类推,在算法设计过程中用数组表示。xit(m-1)={xi(1)t,xi(2)t,xi(3)t,…,xi(m-1)t}表示第t代遗传过程中第i个解(运输方式的第i种组合);xi(j)t表示第t代第i个解中第j个基因的值,也就是节点j与(j+1)之间的运输方式的值;设数组(染色体)的某个元素(基因)xit(k)=xi(j)t=n,也就是用自然数n表示第n种运输方式。这样利用一串自然数可以表示一个解向量,如2,5,4,8,6…表示一个染色体,每个元素的值表示相邻两节点之间的一种运输方式。5.2初始解的个数随机产生k个(m-1)维的数组(染色体),k为初始解的个数。染色体的基因为1～n之间的随机数,由这些k个(m-1)维的数组组成初始种群,k的确定由节点数量与求解精度来确定。5.3模型主要变量由于目标函数比较复杂,在设计算法时需做适当变形,设ψi=∑xi(j)tci(j)t+∑yhexi(j)t,xi(j+1)t+dt+ft+zrU(10)其中,cxi(j)t为相应染色体中各基因相对应的运输成本;yh={1,xi(j)t≠xi(j+1)t0,xi(j)t=xi(j+1)t为转载选择因子;exi(j)t,xi(j+1)t为从运输方式xi(j)t转载到运输方式xi(j+1)t的转载成本;zrU为罚值函数,zr={1‚Q≤wli,i+10,Q≻wi,i+1‚U为一极大值,表示超过约束的惩罚;其余变量的含义与模型相同。由于目标函数是极小值问题,所以利用界限构造法来确定适应度函数。适应度函数表示为fi=C-ψi(11)其中,C为极大的数。如果两节点间没有某种运输方式,或某种运输方式的容量不满足,则赋予其运输费用为一个很大的值。由于适应度函数的计算过程已经包括判断各种运输方式组合的运输、转载、仓储或惩罚等约束条件,所以该函数可以很好的代替各染色体的适应度。5.4蒙特卡罗法采用精英选择策略,将每代群体中的k个染色体按适应度由大到小排列,排在第一位的染色体性能最优,将它直接复制进入下一代,并排在第一位。下一代群体的另(k-1)个个体需要根据前代群体的k个染色体的适应度采用蒙特卡罗法产生。这样的选择方法既可保证最优染色体生存至下一代,又能保证适应度较大的染色体以较大的机会进入下一代。5.5染色体的选取对通过选择操作产生的群体,利用离散重组的方法进行交叉操作。参与交叉的染色体是以交叉概率来选定,并采用单点交叉的方法随机选择一个位置作为交叉点进行配对交叉。如图2所示,两个父染色体通过交换部分基因段生成两个子染色体,子染色体继承了父染色体的部分特征,实现遗传进化的目的。5.6变异算子的个数由于每个基因的取值范围是1～n之间的自然数,所以变异算子xi(j)′t=n,通过随机的方法确定变异值(1～n之间的整数)。一旦变异操作发生,其值只能变异为1～n之间的自然数。6最优运输方式组合的确定一条有10个枢纽点(m=10)的运输通道,每个枢纽节点之间有8种运输方式(n=8)可供选择,货物只可以在枢纽节点进行运输方式之间的转载。已知枢纽节点间(运输段)各种运输方式的运输成本与运输时间、每个节点各种运输方式转载时间与转载成本以及运输起止点各种运输方式的装卸成本及时间,用户约束为:单位仓储成本为3,单位惩罚成本为2,合约货物运达期限为35小时～45小时。利用C语言编程,算法中参数设计为:种群大小k=20,染色体长度G_LENGTH=10-1=9,交叉概率C_RATE=0.7,变异概率M_RATE=0.1,迭代次数为100代,大数C=800,初始种群通过随机方法产生。运行结果显示如图3,算法在第47代循环中已经收敛。适应度变动范围从253到532,该问题的最优运输方式组合为1,1,1,1,1,1,1,1,4,即在前9个节点之间用第1种方式运输,在第9个节点时货物被转载到第4种运输方式,由第4种运输方式送往目的地。这种运输方式组合可使适应度最大,即maxfitness=532;此时物流成本最低,即minZ=268。货物运达时间为45个小时,运输时效符合合约要求,既没有仓储成本,也不产生惩罚成本,达到物流成本的优化。表1显示优化软件在问题规模较小时非常有效,但随着规模的增加软件的计算时间非常