结点站间集装箱班列开行方案的优化模型及算法

结点站间集装箱班列开行方案的优化模型及算法

第29卷,第1期　　　　　　　　　中国铁道科学2008年1月　　　　　　　　　CHINARAILWAYSCIENCE

文章编号:100124632(2008)0120097205

Vol129No11　

January,2008　

结点站间集装箱班列开行方案的优化模型及算法

闫海峰1,彭其渊1,谭云江2

(1.西南交通大学交通运输学院,四川成都　610031,2.西南交通大学图书馆,四川成都　610031)

　　摘　要:基于一定的边际假定、定义及其定理,将铁路结点站间集装箱班列开行方案(BCTFP)箱小时消耗最少的优化目标描述为线性阶跃函数,得到BCTFP的优化模型。在模型中,每支非零箱流均对应1个线性等式约束,且每个约束条件之间没有任何交叉。将该模型改造为不含约束条件的0-1二层线性规划模型:上层规划的目标为箱小时节省最大,下层规划的目标为在给定决策变量条件下的沿途改编箱小时消耗最小。按照适应性遗传算法的思想确定遗传策略,采用协同多群体遗传算法,以有效地克服由于问题本身具有强基因关联和超多峰性质而带来的模式欺骗问题,设计相应的遗传算法。通过对算法每个环节计算复杂度的分析,得到该算法βn2),说明该算法是收敛于全局最优的有效算法。的整体复杂度为O(αn3ln

　　关键词:集装箱班列;列车编组计划;结点站;箱小时;方案优化;优化模型;遗传算法　　中图分类号:U292136　　文献标识码:A

　　铁路货物列车编组计划(TrainFormationPlan,TFP)问题属于非线性离散规划问题,是NP完全的[1]。,{ρij,且ij。

3)的维数灾难(BlockCon2tainerTrainsFormationPlan,BCTFP)优化问题是TFP问题的1个子类,本文研究BCTFP的相关模型,设计出有效的算法,快速准确地筛选出满意的BCTFP。

1　边际假定及相关定义

111　边际假定

(1)综合性假设:把结点站视为“黑箱”系

统[2],只考虑几个重要参数。考虑的参数有:aij为结点站i产生的、到结点站j(i≠j)消失的1昼夜的箱流量;Tij为结点站i发往结点站j的集装箱班列(BlookContainerTrains,BCT)每昼夜消耗的集结箱小时;ti为任意直达箱流无改编通过结点站i时平均每箱节省的时间[3]。

(2)确定性假设:某任意aij所对应的径路ρij是唯一确定,所有结点站都处于整个径路集R=

　收稿日期:2005212230;修订日期:2007209203

　基金项目:铁道部科技研究开发计划项目(2002X0192B)

),男,山西定襄人,副教授。　作者简介:闫海峰(1974—

。

,将非结点站的分界点省略得到节点集VJ;将任意相邻结点站间的径路简化为1对反向平行弧而得到有向弧集EJ,由此路网可被抽象描述为GJ={VJ,EJ}。112　相关定义及其定理

定义1　设有集合A,对于作用在集合A上的二元关系:。若①A中元素个数不少于2个;②Πx∈A,Πy∈A]x≠y;③Πx∈A,Πy∈A,x≠y]x:y或y:x有且只有1个成立;④A中元素的个数不少于3个,Πx,y,z∈A且x:y,y:z,x:z均成立,则称集合A为简单有序集,简称有序集[4]。

ρ定理1　ij可以唯一地表示为1个有序集Vij,

Vij中的元素即为ρij中所包含的作业站(aij的始发、终到及可能的中转结点站),其上的序为aij经由各个作业站的先后顺序,即径路方向(证明[4]略)。并将Vij去掉其第1个和最后1个元素的集合,记为V′ij。

定义2　对于有序集Vij,另一有序集A若满足①A<Vij,②

iA∩

jA,则称A为Vij的大

结点站间集装箱班列开行方案的优化模型及算法

98中　国　铁　道　科　学　　　　　　　　　　　　　　　　　　第29卷

子集。

jk

定义3　直达变量yij、1站中转改编变量yij和

ij

多站中转改编变量yAij为3组0-1决策变量。含义分别为

1　(aij由i站无中转改编直达

模型[M1]的约束条件非常简单,每支箱流均只对应1个等式约束,且每个约束之间没有交叉,但由于目标函数中含阶跃函数,不存在分解形式,目前还没有十分成熟的算法。

j

　　yij=

　　输送至j站)

0　(否则)

1　(aij在且只在沿途k结点站　　中转改编后输送至j站)0　(否则)

1　(aij在且只在集合Aij中包含的

3　BCTFP问题的0-1BLP模型转换

　　遗传算法(GeniticAlgorithm,GA)在最坏情形下的时间复杂度为O(O(f)nlnn)[5,6],O(f)表示依赖于可行域的适应值函数的复杂度。可以看出,对于某类组合优化问题,只要能构造出相应的多项式时间复杂度O(f),就可以利用GA得到1个多项式时间算法,且在采用一定的选择策略情况下,完全收敛于最优解。由此,也可以看到GA解决该类问题的明显优势。

但是,模型[M1]由于变量个数多和目标函数复杂的特点,在采用GA求解时,会带来染色体。为避免这,[进行一定的转,通过将背包问题构造为二层线性规划(BilevelLinearProgramming,BLP),从而证明了BLP是一类NPC问题[7],同时间接地证明了BCTFP问题也完全可以构造为BLP。利用直达去向数远远小于箱流改编方案数的特点,将模型[M1]改造为0-1BLP模型[M2]。其形式如下:

i

j

ij

k

k

k

　　yij=

　　各站中转改编后输送至j站)

0　(否则)

　　(i∈VJ,j∈VJ,

k∈V′ij,i≠j≠k,Aij为Vij的大子集)

ij

　　yA=ij

2　BCTFP问题的阶跃模型建立

(1)以所消耗的箱小时最少为优化目标构造目

标函数。,如果aij,它可能与任何同时经由i,j两结点站的长途箱流合并,所包含的最大可能的箱流量记为naij,所对应的集结消耗可以表示为Tij

naM

,M>naij且M∈Z。[ ]为一元运

算,其运算法则为[x]=

y　(x∈R,y∈Z,x+1>

y≥x)。aij对应的目标函数为　　Zij=Tij

k1

maxZ=

i

a∑t∑∑

j

ij

-

naM

k

BLPU　　BLP∑∑T

i

xij-F

+

Aij

k2

xij∈{0,1}

(i≠j且i,j∈VJ;k∈V′ij)

j

ij

k

k

(4)

　　　　aij

k1

j

　　yij+

∑∑y

k1

ij

yij1tk1+

Aij

Aijij

yijij

A

∑

tk2

(1)

(2)对每支箱流aij构造唯一性约束

+y∑

=1

minF=

a∑t∑∑

BLPLxij∈{0,1}

(i≠j且i,j∈VJ;k∈l(xij))

(2)　　　(k1∈V′ij,k2∈Aij)

(3)把所有单支箱流的目标函数和约束条件构造出来,然后将各支箱流合并起来便可以得到整个路网情形下的BCTFP阶跃函数模型[M1]。

i

j

ij

　　Z=z∑∑

|y∈(3)

式中:y表示所有决策变量组成的向量;Ω为

[M1]的解空间。

式中:决策变量xij表示从结点站i到j是否开行直达班列,如果开行则构造有向弧Eij,并添加到路网GJ中,这样可以得到从i到j的物理径路相同而有向弧序列或结点序列不同的多条指定径路;l(xij)表示与从i到j的指定径路所对应的不同结点序列集合。

[M2]的上层规划BLPU目标为箱小时节省最大;下层规划BLPL目标为在给定决策变量xij条

结点站间集装箱班列开行方案的优化模型及算法

第1期　　　　　　　　　　　　　　结点站间集装箱班列开行方案的优化模型及算法99

件下求沿途改编箱小时消耗最小。该模型不含其他复杂约束,非常适宜采用GA求解。

4　模型的GA设计

411　遗传策略、参数的选择 …… 此处隐藏：7717字，全部文档内容请下载后查看。喜欢就下载吧 ……