188宝金博页面版

2008年1月系统工程理论与实践第1期文章编号：1000．6788(2008)01-0132．09带车辆行程约束的VRPSPD问题的改进蚁群算法张涛1，田文馨2，张珥杰3，刘士新4( 1．上海财经大学信息管理与工程学院，上海200433；2．上海金融学院现代188宝金博页面版中心信息化办公室，上海201209；3．复旦大学计算机科学与工程系，上海市智能信息处理重点实验室，上海200433；4．东北大学信息科学与工程学院，流程工业综合自动化188宝金博页面版部重点实验室，沈阳110004)摘要：研究一个仓库下，同质车队具有最大负载能力限制，客户同时具有送货与取货需求，产品以原有形态回收的逆向物流车辆路径问题，建立了带车辆最大行程约束的VRI) sPD问题的混合整数规划模型；在蚁群系统算法的基础上，采用了基于排序的蚂蚁系统和最大最小蚂蚁系统算法的信息素更新策略，针对VRPSPD问题车辆负载量不断波动的复杂特性，设计了考虑车辆负载使用率的启发式因子；考虑车辆出仓载货量的初始化与剩余客户的送取货需求量相关，并在一定范围内随机取值．实例运算的结果表明，该算法对于求解带车辆最大行程约束的VRPSPD问题，可以有效提高车辆的负载率，避免因负载波动和最大负载能力约束而增加车辆总行程，在可接受的计算时间内收敛到满意解．关键词：系统工程；逆向物流；同时送取货的车辆路径问题；蚁群系统；混合整数规划中图分类号：0223文献标志码：AThei m provedantcol ony al gori thmfor the VRPSPD w i th m axi m umdi stance constrai ntZH AN GTa01，TIAN W en．xi n2，ZH AN G Yue一，．n．_l i e5LIUShixi(1．SchoolofInform ati onM anagem emand Engi neeri ng，ShanghaiU ni versi tyof Fi nance and Econom i cs，Shanghai 200433，Chi na；2．Inform afi zati on O ffi cei n CenterofM odernEducati on Technol ogyofShanghaiFi nance U ni versi ty，Shanghai201209，Chi na；3．D epartm entof Com puter Sci ence andEngi neeri ng。SbenghniShanghai 200433，Chi na；4．School of Inform ati onSci ence& Engi neeri ng，N ortheastern U ni versi ty，Key Laboratory of IntegratedAutom ati onKeyLaboratory of Intel l i gentInform ati onProcessi ng，Fudan U ni versi ty，of Procefl 6Industry，M i ni stryofEducati on。Shenyangl10004，Chi na)Abstract：Thi spaper studi es thereve嘲l ogi sti cs vehi cl e m uti ngprobl emof si m ul taneous di stri buti on of conanodi ti esand col l ecti on of reusabl e ones the 88．nl e si ze a8 tIl e i ni ti al state w i th asi ngl e depot andahom ogeneous fl eet of vehi desw i th l i m i tedcapaci ti esand m axi m umdi stance。and constructs量m i xedi nteg盱program m i ngm odel ．To sol ve thi sprobl em ，anAntCol ony System ( ACS) approach com bi ni ngw i th thepherom one updati ngstrategy of ASRank( Rank·based Versi on of Ant System ) and M M AS( M AX- M INAntSystem ) i s prepoⅫ1．Anew heuri sti c factor i s desi gnedi m pm vethe vehi cl el oadi ng abi l i ty聃w el l 鹏thevehi cl e di stance．and the i ni ti al vehi cl e l oad i sdesi gnedrandomval ue correl ated to thedel i very andpi ck—updem and of the rest custom ers on thepath．Theexperi m ental nayi ndi cates that theapproachcoul di m prevethe vehi cl e l oad rate andgetri d of theaddi ti onal total di stance causedbythefl uctuati ngvehi cl el oad and the l i m i tedcapaci ty．Itcoul d obtai n the sati sfi ed sol uti on w i thhi 【sh convergence speedi ntoto be atheacceptabl eti m e．Key w ords：systemengi neeri ng；Ieverl Be l ogi sti c；VRPSPD ；ant col ony system ( ACS) ：m i xed i nteger pm 乒anuni ng1引言．逆向物流车辆路径问题，包括先送货后取货的车辆路径问题VRPB( Vehi cl e Routi ng Probl emw i th收稿日期：2006．10-18资助项目：国家自然科学基金(70501018，60773124)作者简介：张涛(1970一)，男。河南鹤壁人，副教授，博士，从事物流建模与优化、生产计划与调度、智能优化算法的研究；田文馨(1981一)，女，山西朔州人，硕士，从事供应链与物流、智能优化算法的研究；张碉杰(1973一)，通讯作者，女，辽宁抚顺人，副教授，博士，从事智能优化算法、机器学习的研究；刘士新(1968一)，男，辽宁调兵山人，教授，博士，从事生产计划与调度、物流建模与优化、智能优化算法的研究． 万方数据