电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

(完整版)遗传算法求解VRP问题的技术报告VIP免费

(完整版)遗传算法求解VRP问题的技术报告_第1页
1/9
(完整版)遗传算法求解VRP问题的技术报告_第2页
2/9
(完整版)遗传算法求解VRP问题的技术报告_第3页
3/9
Page1of9遗传算法求解VRP问题的技术报告摘要:本文通过遗传算法解决基本的无时限车辆调度问题。采用车辆和客户对应排列编码的遗传算法,通过种群初始化,选择,交叉,变异等操作最终得到车辆配送的最短路径。通过MATLAB仿真结果可知,通过遗传算法配送的路径为61.5000km,比随机配送路径67km缩短了5.5km。此结果表明遗传算法可以有效的求解VRP问题。一、问题描述1.问题描述车辆调度问题(VehicleScheduling/RoutingProblem,VSP/VRP)的一般定义为[1]:对一系列送货点和/或收货点,组织适当的行车路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量,送发货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的目标(如路程最短、费用极小、时间尽量少、使用车辆数尽量少等)。问题描述如下[2]:有一个或几个配送中心),...,1(niDi,每个配送中心有K种不同类型的车型,每种车型有n辆车。有一批配送业务),...,1(niRi,已知每个配送业务需求量),...,1(niqi和位置或要求在一定的时间范围内完成,求在满足不超过配送车辆载重等的约束条件下,安排配送车辆在合适的时间、最优路线使用成本最小。2.数学模型设配送中心有K台车,每台车的载重量为),...,2,1(KkQk,其一次配送的最大行驶距离为kD,需要向L个客户送货,每个客户的货物需求量为),...,2,1(Liqi,客户i到j的运距为ijd,配送中心到各个客户的距离为),...,2,1,(0Ljidj,再设kn为第K台车配送的客户数(kn=0表示未使用第K台车),用集合kR表示第k条路径,其中kir表示客户kir在路径k中的顺序为(不包括配送中心),令0kr表示配送中心,若以配送总里程最短为目标函数,则可建立如下数学模型:?KkkrkrnirrnsignddZkknkkiik101)]([min)1((1)knikiQqrk1(2)kkrkrnirrDnsignddkknkkiik?)(01)1((3)Lnk0(4)Page2of9LnKkk1(5)},...,2,1},,...,2,1{{kkikikniLrrR(6)21,21kkRRkk(7)其他01n1)(kknsign(8)上述模型中,式(1)为目标函数,即要求配送里程最短;式(2)保证每条路径上各个客户的货物需求量之和不超过配送车的载重;式(3)保证每条配送路径的长度不超过配送车的最大行驶距离;式(4)表明每条路径上的客户数不超过总客户数;式(5)表明每个客户都得到配送服务;式(6)表示每条路径的客户组成;式(7)限制每个客户仅能由一台配送车送货;式(8)表示当第k辆车服务的客户数大于等于1时,说明该台车参加了配送,则sign(n)的值取1,否则为0。二、研究现状车辆调度问题在目标和范围方面有很大差别,主要是研究的目标和限定条件不同。在研究目标方面有的是最短路线,有的是最短时间,有的是客户的方便程度等等。在限定条件方面,有配送中心方面的区别,和有单配送中心的,有多配送中心;有配送车辆的数量、种类方面的区别,如车辆数有限、无限、单一车型和多种车型;在业务种类方面,有的是集货任务,有的是送货业务,有的是集送一体化业务,有的是各种业务混合情况。有时间窗的车辆调度问题是最为普通的问题,以成为研究热点。遗传算法在搜索过程中能够自动获取和积累有关搜索空间的知识,并能利用问题固有的知识来缩小搜索空间,自适应地控制搜索过程,动态有效地降低问题的复杂度,从而求得原问题的真正最优解或满意解,因此我来选用遗传算法来求解VSP问题。三、解决方法遗传算法的流程图如下:Page3of9初始化群体个体评价t

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

(完整版)遗传算法求解VRP问题的技术报告

确认删除?
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群