求解VRP-SDPTW的改进差分进化算法研究.doc
6页
求解VRP・SDPTW的改进差分进化算法研究关键词:摘要：旨在有效整合前向物流与逆向物流，首次提出具有时间窗的同时送货和取货的车辆路径问题 (VRP-SDPTW)的混合整数规划数学模型，通过对参数的设定，可以将其转换为其它经典的车辆路径 问题首次提出改进的差分进化算法(IDE)求解该问题，算法采用新颖的序数编码方法，并刈•不可 行解设计惩罚机制，当染色体值超过规定的范围时，设计基于整数序规范的辅助算子解决变异问题, 差分进化的交叉率随进化代数自动更新数值实验表明，改进的差分进化算法能快速、有效地求解 车辆路径问题，且计算性能优于遗传算法逆向物流；车辆路径问题；差分进化算法；整数规划；优化Research on Improved Differential Evolution Algorithm for SolvingVRP-SDPTWAbstract: The vehicle routing problem with simultaneous deliveries and pickups and time windows (VRP-SDPTW) is the problem of optimally integrating forward (goods distribution) and reverse logistics (returning materials) for cost saving and environmental protection. We constructed a general mixed integer programming model of VRP-SDPTW. The model contained some classical vehicle routing problems as special cases. We proposed an improved differential evolution algorithm (IDE) for solving this problem. In the algorithm, we firstly adopted the novel ordinal number coding to construct an initial population, and introduced a penalty mechanism to punish the infeasible solution, then used some improved differential evolution operators unlike existing algorithm, in mutation operation, we use an integer order criterion based on ordinal number coding method. In addition, in the crossover operation, we designed a self-adapting crossover probability that varied with iteration. We did some numerical experiments and compared the performance of the proposed algorithm with genetic algorithm (GA), the results showed that the performance of the proposed method outperformed GA.Keywords: reverse logistics; vehicle routing problem; improved differential evolution (IDE); integer programming; optimization 1 •引言“逆向物流”是物流过程的相反活动，美国物流管理协会对逆向物流的定义为：“计划、实施和 控制原材料、中间库存、终产品从制造、分销或使用点到恢复点或适当处置点的过程” [1]。
为了节 约成本和保护环境，与逆向物流相关的经典路径问题，如旅行商问题和车辆路径问题必须同时考虑 运送货和回收货物两个过程具有时间窗的同时送货和取货车辆路径问题(Vehicle Routing Problem with Simultaneous Delivery and Pick-up and Time Windows, VRP-SDPTW)有效整合了 前向物流和逆向 物流，是经典车辆路径问题的有效扩展，是NP难组合优化问题在VRP-SDPTW问题中，所有送货任 务都由车场开始，服务结束时所有的取货量被带冋车场，该问题的一个显著特征时在不违背车辆容 量、时间窗口等约束的条件下，每个顾客都同时存在送货和取货服务逆向物流是该问题出现的一 个重要领域，许多国家跟环境保护相关的法律要求公司对其产品的使用和冋收负责，另外公司为了 提高售后服务和降低成本也乐意对英产品进行跟踪服务和回收利用；退货所形成的车辆路径问题也 是VRP-SDPTW问题的一种形式，VRP-SDPTW在实际配送中时常出现，有着广阔的理论和应用前景， 由于求解该问题本身的难度和关注的不足，目前对该问题的研允十分有限目前，国内外关于VRP的研究很多，但对于与逆向物流相关的车辆路径问题的研究还刚刚起步, VRP-SDP问题由Min H.[2]于1989年提出，随后近10年国内外没有见到有关VRP-SDP的报道，直 到逆向物流逐渐被人们认可和重视后，国外才有这方面的报道13-5]o由于VRP问题是NP・难题， VRP-SDP又是VRP的一个变形，同样也是NP・难题，从而VRP-SDPTW问题也是NP・难题。
考虑到 VRP-SDP问题的特殊性和求解难度，求解方法大都与VRP问题的已有算法相结合近年来，在进化计算领域，差分进化算法作为一种性能卓越的优化算法正受到日益关注，其应用领域也越来越广 ［6-7］,与遗传算法［8-10］相比，差分进化算法最大的特点就是在每个新个体的生成过程中用到了父 代多个个体的线性组合，而不是遗传算法传统单一的父代染色体交叉技术但国内外还没有出现运 用差分进化算法对车辆路径问题的研究本文首次提出了具有时间窗的同时取送货车辆路径问题（VRP-SDPTW）的通用数学模型，首次运 用差分进化算法求解车辆路径问题，通过分析各主要变量之间的关系，采用序数编码和辅助算子，有 效解决了变异问题，然后设计一种交叉率随进化代数自动更新的交叉算子，构造了求解VRP-SDPTW 的差分进化算法，在进化的初始阶段，能提高算法的全局搜索能力，在进化的后期，能提高算法的 局部搜索能力2问题描述及数学模型VRP-SDPTW可以描述为：给定一个配送中心，拥有确定数量的具有相同容量的车辆，车辆从配 送中心出发对具有确定数量的客户集进行服务，完成服务后开回配送中心每个客户具有确定的位 置，车辆在配送中心装好客户需要的货物，在客户允许的时间窗口内将客户需要的货物送达，同时 从客户手中回收配送中心的収货要求，车辆离开配送中心的初始装载量和返回配送中心的最终取货 量的都不能超过车辆容量，每个客户的服务只能由一辆车一次完成，使运输总成本最小。
为了表达 方便，我们有如下的符号体系：V为客户集合，客户数量为n=|V|； 0为配送中心；^ = Vu{0}； d..为客户i和间的距离;匕为客户丿•的取货量，d/为客户丿的送货量，j = l,Q为车辆容为配送中心最大车辆数目；兀〃=1,车辆£从客户2•直接达到客月0,车辆Q殳有从客户7直接达到客Pj；儿•为途经弧（门）的iZ前（包含i）的客户取货总量；z”•为途经弧（ij）的iZ后的客户送货总量;s从为车辆R对客户i的开始服务时间；①为从客户i到客户丿•的行驶时间（正比于从客户i到客户丿•的欧氏距离给）；心为 顾客7的服务时间；顾客i的时间窗为区间［%,仇］,顾客j的服务必须在该区间内开始，配送中心的 时间窗口［勺，％］说明所有车辆都在d（）之前不能离开配送中心，并且必须在％之前返回配送中心, 其作用相当于给每辆车加上了一个最大行驶距离约束或最长工作时间约束经过上面的描述，VRP-SDPTW的混合整数规划数学模型可以表示为：k n “価冷 （1）£=］ /=0 7=0n KS. t・工工切=1,丿=1,…(2)MO /t=l工切-工XjiR =0,丿= 0,1,•••”£ = 0,1,…,Z; (3)z=0 i=()工 Xo孙 5 1， k = \，…，艮 (4)7=1为儿-为y厂巴，巧"； ⑸;=0 ;=0“ nDij-Zzji=dj, V/^0; ⑹i=0 /=0y.. + z.. < Q^xijk, f 0,1,…” (7)Ar=lsik + fi (! - xijk)- sjk，，J = 0,l, •••/?; k = 0,l,…,Z; (8)< sik
该模型的通用性很强，通过参数的不同设定可以转换为其它经典的车辆路径优化数学模型若 设％二0, b尸g,则可以把时间约束（8）和（9）去掉，该模型就变成了普通的VRP-SDP模型；若 任意的p} =0,则该模型就变成了 VRPTW模型；若从某客户开始前面的客户只有送货要求（卩严）, 而后面的客户只有取货要求（乙二0）,再去掉时间窗口，则该模型为VRP-B问题；若某些客户只有 送货或者取货要求（p丿和心至少一个为零），再去掉时窗，则该模型为VRP-PD问题；若取货点和 送货点成队出现，再去掉吋窗，则该模型与m-Dial-a-Ride问题类似；若只有一辆车进行服务，则该 模型就变成了 TSP的相关问题3.编码在此问题中，我们采用比较直观的序数编码，用矢量（人，l2...,ln）表示染色体G其中元素（基 因）厶为[1, n]Z间的一个互不重复的自然数，随机产生一组染色体（h=l,2,...,WP ）其中WP为 每一代种群中的个体数冃，即为种群规模，G〃各不相同，它为第一代种群首先根据经验对完成配 送任务可能需要的车辆数目进行设定，设为加，对于某个个体，设其对应的配送路径方案的配送路径 条数与加之差为丿，若配送路径条数不超过加，则取丿二0,表示该个体对应一个可行解;然后将加的 取值逐一减小，直到减小观后不能得到满足所有约束的可行解；此时加即为最小的车辆数目；若配 送路径条数大于加，则丿＞0,表示该个体对应一个不可行解）。
若设定的加只有不可行解，将加的取 值逐一增大，直到增大加后能得到满足所有约束的可行解设个体的目标函数值为Z”，将丿看成该 个体对应的配送路径方案的不可行路径条数，并对每条不可行路径的惩罚权重为久•（该权重可根据 目标函数的取值范。
