资源描述：
《具有模糊预约时间的vrp混合遗传算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第8卷第3期管 理 科 学 学 报Vol.8No.32005年6月JOURNALOFMANAGEMENTSCIENCESINCHINAJun.2005①具有模糊预约时间的VRP混合遗传算法123张建勇,李 军,郭耀煌(11南开大学国际商学院,天津300071;21天津职业大学经济管理学院,天津300402;31西南交通大学经济管理学院,成都610031)摘要:在对具有模糊预约时间的多对多货物收发情况下的车辆路径问题进行简单描述的基础上,构建了该问题的多目标数学规划模型,提出了解决该问题的一种基于插入启发式算法、并用修正的推—碰—掷过程进行改进的混合遗传算法,最后,给出了该问题的一个计算实例,并
2、与改进的Solomon插入启发式算法进行了比较.关键词:模糊预约时间;车辆路径问题;混合遗传算法中图分类号:U116.2 文献标识码:A 文章编号:1007-9807(2005)03-0064-08[11]0 引 言况下,Cheng和Gen提出用模糊预约时间(fuzzyduetime)的概念来代替时间窗的概念,并研究了车辆路径问题(vehicleroutingproblem,VRP)单收或单发的情况下的具有模糊预约时间的车辆是指为服务于已知的一组顾客的一个车队,设计路径优化问题.本文在对模糊预约时间的概念进一组开始和结束于一个中心出发点的最小费用路行简单介绍的基础上,进一步研究具有模糊
3、预约径.每个顾客只能被服务一次,而且,一个车辆服时间的多对多货物收发情况下的车辆路径问题,务的顾客数不能超过它的能力[1].并提出解决该问题的一种混合遗传算法.带有时间窗的车辆路径问题(vehicleroutingproblemwithtimewindows,VRPTW)是车辆路径问1 问题描述题的一类重要拓展.在VRPTW中,对每项任务的服务都必须在一定的时间范围内开始,如车辆到1.1 模糊预约时间达时间早于该任务可以开始的最早时刻,则车辆模糊预约时间是一种反映顾客偏好的时间必须在该任务处等待;车辆到达时间晚于任务可窗,它可以表示为关于时间t的凸模糊数,顾客的以开始的最晚时间,则任务必须被推
4、迟进行或被满意度函数由该模糊数的隶属度函数μi(ti)表拒绝.示,如图1所示.模糊预约时间应包含可容忍的时在过去的几十年中,各国学者对带有时间窗间范围[ETi,LTi]和期望服务时间DTi两部分.当的车辆路径优化问题进行了大量研究,提出了解顾客在期望服务时间DTi被服务时,顾客满意度[2～10]决该问题的大量启发式、亚启发式算法.但最大(满意度μ设为1);否则,顾客满意度随着服是,在许多实际的应用中,时间窗并不能真正反映务时间与期望时间之间的差距的增大而降低.若顾客的时间偏好.顾客可能更偏好于服务在时间服务时间落在可容忍时间范围之外(ti5、i>LTi),则顾客不满意(μ=0).于该时点(段),顾客的满意度都会降低.在这种情①收稿日期:2003-05-26;修订日期:2005-03-24.基金项目:国家自然科学基金资助项目(70071028);南开大学科研启动经费资助项目.作者简介:张建勇(1975—),男,山西和顺人,博士.第3期 张建勇等:具有模糊预约时间的VRP混合遗传算法—65—距离;wi(ti)———当车辆在顾客i处的开始服务时间为ti时,车辆在该顾客处的等待时间;μi(ti)———当车辆在顾客i处的开始服务时间为ti时,顾客i的满意度.②变量图1 模糊预约时间Fig.1Fuzzyduetimeti——
6、—顾客i的开始服务时间;1.2具有模糊预约时间的多对多货物收发情况1 点i的由车辆k服务уik=下的VRP描述0 否则具有模糊预约时间的多对多货物收发情况下1 车辆k从点i直接行驶到点jxijk=的VRP一般可描述为:设有m项货物运输任务,0 否则3)目标分别用编号1,2,⋯,m表示,任务i(i=1,2,⋯,在综合考虑企业运输成本最小化和顾客满意m)要求从始点(发点)ui运送数量gi的货物到终度最大化两方面因素的基础上,具有模糊预约时点(收点)vi,始点和终点的模糊预约时间分别为间的车辆路径问题的优化目标定为以下4个Si和Di,任务由车场(用编号0表示)发出的车辆方面:来完成.已知车辆的运输能
7、力为q,且q≥gi.求2mn满足一定目标的车辆行驶路径计划.①最小化车辆使用数min∑∑x0jkj=1k=11.3 模型建立n2m2m1)基本思路②最小化总行驶距离min∑∑∑dijxijkk=1i=1j=12m为解决问题方便起见,本文将每一任务i的1③最小化平均等待时间min∑wi(ti)发点和收点作为两个顾客来处理,其编号分别为2mi=1i和m+i,两顾客的需求量分别为gi和-gi,每一设某一
