一类最小-最大车辆路线问题的启发式算法研究.pdf

《一类最小-最大车辆路线问题的启发式算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第22卷第6期运筹与管理Vo1．22．No．62013年l2月OPERATIONSRESEARCHANDMANAGEMENTSCIENCEDec．2013一类最小．最大车辆路线问题的启发式算法研究王晓博，任春玉，元野(1．黑龙江大学信息管理学院，黑龙江哈尔滨150080；2．哈尔滨工业大学管理学院，黑龙江哈尔滨)摘要：针对个性化和多样性的需求．建立以缩短最长子线路为目标的最小一最大车辆路径问题模型，并提出启发式算法求解。首先．采用自然数编码，使问题变得更简洁；用最佳保留选择法，以保证群体的多样性；引入爬山算法，加强局部搜索能力；其次，

2、对遗传算法求得的精英种群再进行禁忌搜索，保证算法能够收敛到全局最优。最后，通过实例的计算，表明本算法均优于遗传算法和禁忌搜索算法，并为大规模解决实际问题提供思路。关键词：运筹学与控制论；最小一最大的车辆路径问题；遗传算法；禁忌搜索算法；启发式算法中图分类号：F224．31文章标识码：A文章编号：1007—3221(2013)06．0026．08HeuristicAlgorithmforMin—MaxVehicleRoutingProblemWANGXiao—bo。，RENChun—yu。，YUANYe(1．SchoolofInform

3、ationManagement，HeilongjiangUniversity，Harbin150080，China；2．SchoolofManage—ment，HarbinInstituteofTechnology，Harbin150001，China)Abstract：Inordertosatisfytheindividualandvariousdemands，thispaperestablishesmin—maxvehicleroutingproblemforshorteningthelongestsub—lines，andthe

4、heuristicalgorithmisusedtogettheoptimizationsolution．First，anaturalnumbercodingisusedSOastosimplifytheproblem，andthebestretentionselectionmethodisusedsoastomakethediversityofgroup．Thestudyadoptsthehill—climbingalgorithmtostrengthenthepartialsearchingability．Secondly，the

5、stockelitegroupobtainedbygeneticalgorithmissearchedagainwithtabusearchingalgorithminordertoguaranteethealgorithmconvergingtotheglobaloptimization．Finally，theresultsdemonstratethatthealgorithmisbetterthanbothgeneticalgorithmandtabusearchingalgorithm．Thisalgorithmprovides

6、thethoughttosettlethelargescalepracticalproblem．Keywords：operationsresearchandcybernetics；min—maxvehicleroutingproblem；geneticalgorithm；tabusearchingalgorithm；heuristicalgorithm0引言VRP(VehicleRoutingProblem，简称VRP)问题是物流配送中的一项重要研究内容。近年来，随着现代物流的发展，VRP问题引起广泛重视。对其进行优化，可以提高物流经

7、济效益；满足客户多样化、个性化的需求；从而实现物流的科学化、服务水平的现代化。在实际情况中，存在这样的一类车辆路径问题，其目标不是要求整个行车路线的路程最短或费用最少，而是要求整个线路中行程最长的子线路距离最短或时间最短，这类问题称为最小一最大车辆路径问题(Min—MaxVehicleRoutingProblem，MMVRP)。例如：巡逻车队的巡逻线路制定⋯，紧急情况下空投物资的运送线路安排，邮递员投送报纸线路安排，出于社会因素考虑的校车行车线路制定。收稿日期：2012-10-27基金项目：国家社会科学基金项目资助(电子商务物流配送体

8、系优化研究10CGL076)；教育部人文社会科学研究项目资助(非常规突发事件下应急物流网络优化及快速反应机制研究l2YJC630I60)作者简介：王晓博(1973一)，男，黑龙江省哈尔滨人，博士，副教授，硕士生孚师，研究