考虑均衡性的不确定时间车辆调度问题研究

《考虑均衡性的不确定时间车辆调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２２卷第２期运筹与管理Ｖｏｌ．２２，Ｎｏ．２２０１３年４月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＡｐｒ．２０１３考虑均衡性的不确定时间车辆调度问题研究１１２１任锡德，朱建明，王晶，黄钧（１．中国科学院大学，北京１０００４９；２．北京工商大学商学院，北京１０００４８）摘要：本文针对车辆调度实际运行过程中时间的不确定性问题，提出了包含时间窗口、车辆容量约束的配送服务线路随机规划模型，以最小化调用的车辆数目和运行距离，降低顾客的不满意度并且尽可能保证每条路线的均衡性。结合

2、模型，给出了基于禁忌搜索的混合启发式算法，并且生成多个算例，依据算例结果说明模型和算法优越性，同时说明可以在不降低顾客满意度和不提高总运输成本的基础上，降低各条线路之间的时间差异。关键词：运筹学；时间窗口；随机规划；路线时间方差；禁忌搜索；不确定时间；车辆路线中图分类号：Ｏ２２４，Ｃ９３１文章标识码：Ａ文章编号：１００７-３２２１（２０１３）０２-００８６-０６ResearchonLoad-balancingVehicleRoutingProblemwithUncertainTravelTime１１２１Ｒ

3、ＥＮＸｉ-ｄｅ，ＺＨＵＪｉａｎ-ｍｉｎｇ，ＷＡＮＧＪｉｎｇ，ＨＵＡＮＧＪｕｎ（１．UniversityofChineseAcademyofSciences，Beijing１０００４９，China；２．SchoolofBusiness，BeijingTechnologyandBusinessUniversity，Beijing１０００４８，China）Abstract：Ｔｈｅｔｒａｖｅｌｔｉｍｅｏｆｖｅｈｉｃｌｅｓｉｓａｌｗａｙｓｓｔｏｃｈａｓｔｉｃ．Ｉｎｖｉｅｗｏｆｔｈｉｓ，ａｓｔｏｃｈａｓｔｉｃｐｒｏｇ

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

5、ｅｌ，ａｎｄｓｅｖｅｒａｌｃａｓｅｓａｒｅｇｅｎｅｒａｔｅｄｔｏｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ａｎｄｔｈｅｃｏｍｐｕｔａｔｉｏｎｒｅｓｕｌｔｓｈｏｗｓｔｈａｔｔｈｅｔｉｍｅ-ｖａｒｉａｎｃｅｏｆｄｉｆｆｅｒｅｎｔｒｏｕｔｅｓｃａｎｂｅｏｐｔｉｍｉｚｅｄｗｉｔｈｏｕｔｉｎｃｒｅａｓｉｎｇｔｈｅｃｏｓｔｏｒｄｅｃｒｅａｓｉｎｇｔｈｅｓｅｒｖｉｃｅｑｕａｌｉｔｙｏｆｃｏｓｔｕｍｅｒｓ．Keywords：ｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈ；ｔｉｍｅ-ｗｉｎｄｏｗｓ；ｓｔｏｃｈ

6、ａｓｔｉｃｐｒｏｇｒａｍｍｉｎｇ；ｔａｂｕ-ｓｅａｒｃｈ；ｕｎｃｅｒｔａｉｎｔｒａｖｅｌ-ｔｉｍｅ；ｌｏａｄｂａｌａｎｃｉｎｇ；ＶＲＰ０引言在企业物流部门或者第三方物流运作过程中，有很多不确定性的因素，客户需求数量的不确定、车辆［１，２］运行时间的不确定性等，这些不确定性因素给决策部门增加了不少困难。已有的ＶＲＰ文献中，关于随机需求的文章很多，而运行时间不确定的研究文章相对少，并且多数关于运行时间不确定的研究文章给出［３］的解决方式都是再规划方法，实时的对调运计划进行调整，例如Ｈｕｅｙ-ＫｕｏＣｈｅｎ给出

7、了不确定时间下，［４］基于现实运行时间的一系列整数规划，不断对路线决策进行更新，Ｊｅａｎ-ＹｖｅｓＰｏｔｖｉｎａ考虑不确定时间下车辆未按计划到达和出现新顾客需求两种情况下的路线再规划问题。时间窗口增加了问题的难度，同时［５］却非常具有实际意义，因而包含时间窗口约束的研究有很多，例如Ｃｈａｕｇ-ＩｎｇＨｓｕ等描述了带时间窗口［６］约束易腐食品的ＶＲＰ问题，给出模型以及相应的求解方法；Ｐ．Ｐ．Ｒｅｐｏｕｓｓｉｓ等描述了带车辆返回和时间［７］窗口约束的ＶＲＰ模型，重点给出了基于自适应编程下的几种算法，并给出算例

8、；ＲｏｂｅｒｔｏＣｏｒｄｏｎ则在文中重点研究了带时间窗口约束的启发式算法；但是将不确定运行时间和时间窗口结合的文章就更少了，Ｌｉ收稿日期：２０１１-０９-２３基金项目：国家自然科学基金“非常规突发事件应急管理研究”重大研究计划培育项目（９０９２４００８），国家自然科学基金青年基金项目（７１００１０９９）；中国科学院研究生院院长基金第２期任锡德，等：考虑均衡性的不确定时间车辆调度问题研究８７［８］Ｘｉａｎｇｙｏｎｇ给出了随机通行