资源描述：
《基于遗传算法的物流配送车辆调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第34卷第6期数学的实践与认识Vol134No162004年6月MATHEMATICSINPRACTICEANDTHEORYJune,2004基于遗传算法的物流配送车辆调度问题研究1211龚延成,郭晓汾,尤晓铃,赵勇(1.汽车管理学院车管系,安徽蚌埠233011)(2.长安大学汽车学院,陕西西安710064)摘要:研究使用遗传算法求解物流配送组织过程中车辆调度问题.通过把时间窗约束和车辆容量约束转嫁到最小费用目标函数中去,建立适合于遗传算法的车辆调度模型.阐述放回式随机复制算子和适应度函数,设计描述行驶线路的染色体结构、初始群体生成方法、独特的交叉算子和交换变异
2、算子,构造完整的遗传算法.并给出算例,验证调度模型和遗传算法.关键词:物流配送;车辆调度;遗传算法车辆调度是物流组织关键环节,直接影响客户服务水平和配送成本,其任务是根据客户需求分布和车辆相关数据,以总费用最低为目标,选派车辆,确定每辆车的服务对象和行驶线路.由于物流配送车辆调度问题属于异化的多重旅行商难题,受到时间窗和车辆容量等[1—2]约束影响,难以构造出精确算法,国内外专家把主要精力集中在构造启发式算法上.遗传算法具备极强的鲁棒性和内在并行运行机制,本文通过约束转换,建立车辆调度模型,并设计遗传操作方法,构造完整的遗传算法.1物流配送车辆调度模型[3]配送
3、费用由车辆费用、驾驶员补助、等待费用和延迟费用组成.车辆费用由燃料费、折旧费和维修费等变动费用组成,中心根据经营情况可核算出每车公里应摊的车辆费用.驾驶员补助根据途中工作时间计算,若工作时间超过8小时,则超时部分应按加班补助计算.客户通常要求货物在一定时间窗范围内送达,否则中心需支付惩罚费用.若提前到达,支付等待费用;若延迟到达,支付延迟费用.设配送中心向l个客户送货,第i个客户货运量为gi,卸货时间为uti,时间窗为[eti,lti],每小时延迟费用ri;中心与客户、客户与客户两两间的最短运距、平均车速和车辆费用分别为dij、vij和rij(i,j=0,1,2
4、,⋯,l;0表示配送中心);可用m类卡车送货,第p类卡车有np辆,装载容量为vp(p=1,2,⋯,m);每小时等待费用为r,行车补助和加班补助分别为每小时s和es;途中运行到中午12:00和下午6:00时安排30分钟吃饭时间,车辆当天返回物流中心.试确定车辆调度方案,使配送费用Z最低.令车辆pq(第p类车的第q辆)到达客户i时间为ti;弧段(i,j)表示中心与客户或客户与客户之间的最短路,xijpq=1表示车辆pq经过弧段(i,j),xijpq=0表示车辆pq不经过弧段(i,j);yipq=1表示车辆pq给客户i送货,yipq=0表示车辆pq不给客户i送货;wt
5、pq表示车辆pq在8小时内工作时间,ewtpq表示车辆pq加班时间;A是足够大的正数,Z是总配送费收稿日期:200321021894数学的实践与认识34卷用.假定各项费用呈线形变化,则有目标函数:llmnpmnpMinZ=∑∑∑∑dijrijxijpq+∑∑(wtpqõs+ewtpqões)i=0j=0p=1q=1p=1q=1ll+r∑max(eti-ti,0)+∑riõmax(ti-lti,0)i=1i=1mnpl+A∑∑max∑giyipq-vp,0p=1q=1i=1式中,ti=tj+utj+dijövij,j为i前一个站点,若tj<12且ti≥12,或tj
6、<18且ti≥18,则有ti=ti+015;wtpq=min(t00-t0,8),ewtpq=max(t00-t0-8,0),t0为发车时间,t0=eti-d0iöv0i,i是第一个停靠点,t00为收车时间.目标函数前四项是车辆费用、驾驶员补助、等待费用和延迟费用.若客户i不允许车辆延迟到达,则ri取足够大正数.第五项处理车辆容量约束,A是足够大正数,任一车辆超载会引起目标函数值急剧增加,从而保证搜索时舍去不符合容量约束的解.车辆pq行驶线路连通性要求由遗传算法编码来保证.2物流配送车辆调度遗传算法[4]车辆调度问题宜采用自然数编码.染色体“01302450”表
7、示调度方案为:2台车给5个客户送货,车辆11线路是“中心→客户1→客户3→中心”,车辆21是“中心→客户2→客户4→客户5→中心”.这种编码方式能够保证每辆车行驶线路的连通性.染色体长度=车辆总数+客户数+1.车辆总数需要事先试算,一般要求车辆总装载容量是总货物量的1105～113倍.初始群体生成:任意给客户和车辆排序;从左向右累计客户需求量,若第一辆车容量大于前a个且小于前a+1个客户需求量之和,则得第一辆车子串1“12⋯a0”;删去排序中前a个客户,同理可得第二辆车子串2;如此反复,直到车辆和客户被安排完(若车辆安排完而仍有客户没安排,则给客户重新排序后从头
8、操作);把子串顺序连接,
