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

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

1、第２２卷第６期运筹与管理Ｖｏｌ．２２，Ｎｏ．６２０１３年１２月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＤｅｃ．２０１３一类最小-最大车辆路线问题的启发式算法研究１１２王晓博，　任春玉，　元野（１．黑龙江大学信息管理学院，黑龙江哈尔滨１５００８０；２．哈尔滨工业大学管理学院，黑龙江哈尔滨）摘要：针对个性化和多样性的需求，建立以缩短最长子线路为目标的最小-最大车辆路径问题模型，并提出启发式算法求解。首先，采用自然数编码，使问题变得更简洁；用最佳保留选择法，以保证群体的多样性；引入爬山算法，加强局部搜索能力；其次，对遗传算法求得

2、的精英种群再进行禁忌搜索，保证算法能够收敛到全局最优。最后，通过实例的计算，表明本算法均优于遗传算法和禁忌搜索算法，并为大规模解决实际问题提供思路。关键词：运筹学与控制论；最小-最大的车辆路径问题；遗传算法；禁忌搜索算法；启发式算法中图分类号：Ｆ２２４．３１　　　文章标识码：Ａ文章编号：１００７-３２２１（２０１３）０６-００２６-０８HeuristicAlgorithmforMin-MaxVehicleRoutingProblem１１２ＷＡＮＧＸｉａｏ-ｂｏ，ＲＥＮＣｈｕｎ-ｙｕ，ＹＵＡＮＹｅ（１．SchoolofInformationManagement

3、，HeilongjiangUniversity，Harbin１５００８０，China；２．SchoolofManage-ment，HarbinInstituteofTechnology，Harbin１５０００１，China）Abstract：Ｉｎｏｒｄｅｒｔｏｓａｔｉｓｆｙｔｈｅｉｎｄｉｖｉｄｕａｌａｎｄｖａｒｉｏｕｓｄｅｍａｎｄｓ，ｔｈｉｓｐａｐｅｒｅｓｔａｂｌｉｓｈｅｓｍｉｎ-ｍａｘｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍｆｏｒｓｈｏｒｔｅｎｉｎｇｔｈｅｌｏｎｇｅｓｔｓｕｂ-ｌｉｎｅｓ，ａｎｄｔｈｅｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｉｓｕｓｅｄｔｏｇ

4、ｅｔｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｓｏｌｕｔｉｏｎ．Ｆｉｒｓｔ，ａｎａｔｕｒａｌｎｕｍｂｅｒｃｏｄｉｎｇｉｓｕｓｅｄｓｏａｓｔｏｓｉｍｐｌｉｆｙｔｈｅｐｒｏｂｌｅｍ，ａｎｄｔｈｅｂｅｓｔｒｅｔｅｎｔｉｏｎｓｅｌｅｃｔｉｏｎｍｅｔｈｏｄｉｓｕｓｅｄｓｏａｓｔｏｍａｋｅｔｈｅｄｉｖｅｒｓｉｔｙｏｆｇｒｏｕｐ．Ｔｈｅｓｔｕｄｙａｄｏｐｔｓｔｈｅｈｉｌｌ-ｃｌｉｍｂｉｎｇａｌｇｏｒｉｔｈｍｔｏｓｔｒｅｎｇｔｈｅｎｔｈｅｐａｒｔｉａｌｓｅａｒｃｈｉｎｇａｂｉｌｉｔｙ．Ｓｅｃｏｎｄｌｙ，ｔｈｅｓｔｏｃｋｅｌｉｔｅｇｒｏｕｐｏｂｔａｉｎｅｄｂｙｇｅｎｅｔｉｃａｌｇｏｒｉｔ

5、ｈｍｉｓｓｅａｒｃｈｅｄａｇａｉｎｗｉｔｈｔａｂｕｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍｉｎｏｒｄｅｒｔｏｇｕａｒａｎｔｅｅｔｈｅａｌｇｏｒｉｔｈｍｃｏｎｖｅｒｇｉｎｇｔｏｔｈｅｇｌｏｂａｌｏｐｔｉｍｉｚａｔｉｏｎ．Ｆｉｎａｌｌｙ，ｔｈｅｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｉｓｂｅｔｔｅｒｔｈａｎｂｏｔｈｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄｔａｂｕｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｐｒｏｖｉｄｅｓｔｈｅｔｈｏｕｇｈｔｔｏｓｅｔｔｌｅｔｈｅｌａｒｇｅｓｃａｌｅｐｒａｃｔｉｃａｌｐｒｏｂｌｅｍ．Key

6、words：ｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈａｎｄｃｙｂｅｒｎｅｔｉｃｓ；ｍｉｎ-ｍａｘｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｔａｂｕｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍ；ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ０　引言ＶＲＰ（ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍ，简称ＶＲＰ）问题是物流配送中的一项重要研究内容。近年来，随着现代物流的发展，ＶＲＰ问题引起广泛重视。对其进行优化，可以提高物流经济效益；满足客户多样化、个性化的需求；从而实现物流的科学化、服务水平的现代化。在实际情况中，存在这样的一类车辆路径问题，其目

7、标不是要求整个行车路线的路程最短或费用最少，而是要求整个线路中行程最长的子线路距离最短或时间最短，这类问题称为最小-最大车辆路径问题［１］（Ｍｉｎ-ＭａｘＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍ，ＭＭＶＲＰ）。例如：巡逻车队的巡逻线路制定，紧急情况下空投物资［２］［３］的运送线路安排，邮递员投送报纸线路安排，出于社会因素考虑的校车行车线路制定。收稿日期：２０１２-１０-２７基金项目：国家社会科学基金项目资助（电子商务物流配送体系优化研究１０ＣＧＬ０７６）；教育部人文社会科学研究项目资助（非常规突发事件下应急物流网络优化及快速反应机制研究１２ＹＪＣ６３０１６

8、０）作者简介：王晓博（１９７３-），男，黑龙江省哈尔