和随机时间车辆路径问题模型和算法

《和随机时间车辆路径问题模型和算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第29卷第8期2009年8月系统工程理论与实践SystemsEngineering—Theory＆PracticeV01．29，No．8Aug．，2009文章编号：1000-6788(2009)08-0081—10带时间窗和随机时间车辆路径问题：模型和箅法李相勇，田澎(上海交通大学安泰经济与管理学院，上海200052)摘要研究带随机车辆旅行时间、服务时间以及时间窗的车辆路径问题．根据不同的优化目标，首先给出了问题的两种数学模型描述：机会约束规划和带修正的随机规划模型．为了有效地求解该问题，提出了基于禁忌搜索的启发式算法，该算

2、法考虑了问题的随机特性．在实验部分，首先给出了产生测试问题的方法，然后基于产生的测试问题给出了算法的计算结果．关键词车辆路径问题；随机旅行时间；随机服务时间；时间窗；禁忌搜索丰图分类号0221文献标志码AVehicleroutingproblemswithtimewindowsandstochastictimes：Models＆algorithmLIXiang-yong，TIANPeng(AntaiCollegeofEconomics＆Management，ShanghaiJiaotongUniversity,Shanghai200

3、052，China)AbstractThispaperstudiesaversionofthestochasticvehicleroutingproblem，wheretravelandservicetimesarestochastic，andatimewindowisassociatedwitheachcustomer．Thisproblemisoriginallyformulated嬲achanceconstrainedprogrammingandastochasticprogrammingwithrecourseinterms

4、ofdifferentoptimizationobjectives．Toefficientlysolvethesetwomodels，atabusearchheuristicisthenproposed，whichtakesintoaccountthestochasticnatureofthisproblem．Finally,sometestinginstanceswithdifferentpropertiesareestablishedtoinvestigatethealgorithmicperformanceandcomputa

5、tionalresultsarereported．、Keywordsvehicleroutingproblem；stochastictraveltime；stochasticservicetime；timewindows；tabusearch1引言车辆路径问题(Vehicleroutingproblem，VRP)是一个经典的组合优化问题，现在已经成为配送和物流管理领域的核心问题．从图论的角度，车辆路径问题可以定义如下：设G={KE}为一个完备的无向图，其中V={o，1，2，⋯，礼}为节点集，E={(i，歹)，i，J∈Ki≠歹}为边集

6、．v0=y＼{o}表示顾客点集．0代表车场点，一队具有相同装载能力Q的车辆从车场点对顾客点进行配送服务．每个顾客点有一个固定的需求q／和服务时间瓯．每条边(i，J)赋有一个权重，表示旅行距离或者旅行费用q，．通常，我们假设C=如，)满足三角不等式，即q，≤q七+c奄f，l，歹，k∈V．车辆路径问题的优化目标为：确定一个具有最小车辆数和对应的收稿日期：2007-08-09作者简介：李相勇(19rs-)，男，江苏建湖人，博士，研究方向：组合优化和网络流；田澎(1958-)，男，辽宁沈阳人，博士，教授，研究方向：决策科学与优化方法．万方数

7、据82系统工程理论与实践第29卷最小旅行距离或者费用的路线集，其满足下列约束条件：1)每一条车辆路线开始于车场点，并且于车场点结束；2)每个顾客点仅能被一辆车服务一次；3)每一条车辆路线总的顾客点的需求不超过车辆的装载能力Q；4)每一条车辆路线满足一定的边约束，比如持续时间约束和时间窗约束等．自Dantzig和aaInser于1959年首次提出车辆路径问题以来【l】'运筹学文献中已经研究了许多不同类型的变型车辆路径问题．越来越多的边约束添加到基本车辆路径问题中，使得问题越来越接近配送管理的实际，这些扩展问题包括：带时间窗车辆路径问题

8、(VRPwithtimewindows，VRPTW)[21，异型车辆路径问题(HeterogeneousVRPs，HVRP)[引，开放式车辆路径问题(OpenⅥ妒8，OVRP)[41，和带回程车辆路径问题(Ⅵ啦withbackhaul