资源描述：
《路径长度受限的随机需求VRP的模型和算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第27卷第3期南京工业大学学报Vol.27No.32005年5月JOURNALOFNANJINGUNIVERSITYOFTECHNOLOGYMay2005路径长度受限的随机需求VRP的模型和算法刘浩,钱小燕(南京工业大学理学院,江苏南京210009)摘要:路径长度受限的随机需求VRP在生产、生活中有着广泛的应用。给出了路径长度受限的随机需求VRP问题的线性整数规划模型,在不允许部分服务和仅能服务失败一次的策略下设计了一个启发式算法。该算法以离散优化中广泛应用的扫描算法为基础生成服务的一个初始可行方案,然后
2、利用模拟退火算法改进得到近似最优解。对需求为二项分布的50个结点、1个服务中心的问题进行了数值试验,数值结果表明该算法对求解路径长度受限的随机需求VRP是有效的。关键词:路径长度受限;随机需求;VRP问题;扫描;模拟退火3中图分类号:O22;U116文献标识码:A文章编号:1671-7643(2005)03-0036-03VehicleRoutingProblem简称VRP,一般译为车务一次且仅一次,求解目标是求出完成服务费用最辆路由问题或车辆调度问题。经典的VRP是由一小的派车方案。这是NP2hard的
3、组合优化问题。其个服务中心(depot)的车辆向n个服务需求点进行中容量和最大行程是广义的,不一定是物理意义上服务,在需求确定的情况下,由中心向各结点派送车的容量和路程。辆,而车辆又受最大行程或容量的限制,要求服务所需费用最少或行程最短。固定需求的VRP已经有1PSVRP的随机线性整数规划模型了很多研究,如文献[1～4]等。随机需求VRP的研究较少,尤其是路径长度受限的随机需求VRP研究为了给出此问题精确的数学描述,引进一些常更少。但日常生活、企业管理、车辆运输有着大量的量和变量建立随机线性整数规划模型。
4、路径长度受限的随机需求VRP,如公交班车路径和常量:K—使用车辆的数量;n—需要服务结点计划、银行运钞、运输公司发送货物等。研究路径长数,以1到n记,结点0,表示服务中心;C—车辆的度受限的随机需求VRP能节约费用、为用户提供优质服务、直接带来经济效益。容量;L—车辆的最大行程;dij—结点i到结点j的最路径长度受限的随机需求VRP(Pathlength短距离。constraintvehicleroutingproblemwithstochasticde2变量:ξi=结点i的需求量,它为一个随机变量,ma
5、nd,简记为PSVRP)叙述为:设有一个中心(depot其分布密度或分布函数为已知;设为结点0)和n个服务结点(costumernodes)。中1,若结点i由车辆k服务心拥有充分多的容量为yik=;C的车辆,它们对应的最大0,否则行程都为L,所有车辆均从中心出发为服务结点提1,若车辆k服务结点i后直接服务结点j供服务然后返回中心。设各结点之间以及结点与中yijk=。0,否则心之间的最短距离为dij(i,j=0,1,2,⋯,n)且满足根据上述常量和变量,得到如下的随机线性规三角不等式,即对任意结点i,j,k
6、有dij+djk≥dik。设划模型:min∑dijxijk(1)已知结点i的需求量ξi(i=1,2,⋯,n)的概率分布,ijk每个结点在车辆容量可以服务该结点时被一辆车服使得3收稿日期:2004-09-30基金项目:航空基础科学基金(97J52091)作者简介:刘浩(1976-),男,江苏沛县人,讲师,博士生,研究方向为数值优化及应用;Email:lhmath@sina.com第3期刘浩等:路径长度受限的随机需求VRP的模型和算法37∑ξiyik≤Ck=1,2,⋯,K(2)路由失败;若问题的可行方案中某一
7、条路线含有ti∑个结点,则显然有m≤t≤2m。设pj表示车辆在第jdijxijk≤Lk=1,2,⋯,K(3)ij个结点发生路由失败的概率,它的数学表达式为:K,i=0j-1j∑yik=(4)k1,i=1,2,⋯,npj=P∑ξi≤C,∑ξi>C(11)i=1i=1yik=0或1i=0,1,⋯,nk=1,2,⋯,K(5)jj-1∑则有pj=P∑ξi>C-P∑ξi>C(12)xijk=yjk,j=0,1,⋯,n,k=1,2,⋯,K(6)i=1i=1ij∑jxijk=yik,i=0,1,⋯,n,k=1,2,⋯,
8、K(7)根据中心极限定律Mj=∑ξi服从正态分布,则i=1∑xijk≤
9、S
10、-1,SA{1,2,⋯,n},路由失败的概率容易计算[7]。ij∈S×S2≤
11、S
12、≤n-1,k=1,2,⋯,K(8)设可行方案中一条有t个结点的路径由以下结xijk=0或1i=0,1,⋯,n,j=0,1,⋯,n,点组成:{i1,i2,⋯,it},并以L…表示该路径的平均路k=1,2,⋯,K(9)径长度,为了保证车辆的行程不大于最大行程,我们该模型中包含
