终稿4软时间窗限制的车辆调度物资的配送问题03

1、物资的配送问题摘要本文主要讨论其中的物流配送的路径优化问题，即通过制定合理的配送路径方案，快速而经济地将货物送达用户手中。配送路径选择是否合理，对加快配送速度，提高服务质量，降低配送成本及增加经济效益有极大的影响。作为一个优化类问题，必然包括目标函数、变量和约束条件三要素，我们首先以此为基础，找到本题的约束条件，得出该问题的性质，即有软时间窗约束非满载多车辆的调度问题。经过查阅相关文献后，我们最终决定采用普遍的遗传算法来解决该问题。所谓遗传算法，指的是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，该方法主要采用了改进的交叉算子，

2、可以最大限度的将已经具有双亲优良特性的子串复制到下一代，有效的提高了染色体的质量，增强种群的适应度，另外在种群中各个个体均相同的情况下，也不会影响遗传迭代的进行，摆脱了对种群多样性的要求，有效的提高了对种群的搜索能力。在选择上应用轮盘赌选则法和最佳个体保存策略并行的方法，从而有效的避免了最优个体的中途丢失，并且可以加速算法向最优解的收敛。在解决本问题之前，我们应该指出该问题的一大前提，即：每个客户所需的货物应有且只有一辆车派送，以此来尽可能地将派送车辆的费用大大降低，从而使问题简明化。在解题过程中，根据遗传算法，在所规定的前提下，我们首先对需要的车辆进行估计，依照公式确定车辆数。在确定车辆数后

3、，我们就可以列出简单的目标函数。在这里，我们需要明确几个约束条件：1、约束经过每个客户的车辆有且只有一辆；2、保证每个客户都有车辆运送到所需货物；3、每辆车所载的货物量不超过其车载量；4、使每辆车受到的惩罚费用尽可能地小。有了这些约束条件之后，我们便可以根据所列出的约束式，加上适当的惩罚因子，即引入罚函数，将约束条件加入到简单目标函数中，得到一个优化后的目标函数，使之在同一量纲上。此外，我们就可以利用Matlab软件得到使种群适应度最强的染色体，即最优的配送路径。最终，我们得到的最优配送路径为：派送3辆车，车辆1的行使路线为物流中心客户8客户5客户7物流中心，行驶时间为11.9h，装载量为7t

4、，运送里程为405；车辆2的行驶路线为物流中心客户3客户1客户2物流中心，行驶时间为8.8h，装载量为8t,运送里程为240,；车辆3的行使路线为物流中心客户6客户4物流中心，行驶时间为10.8h，装载量为7t，运送里程为265.该方案总配送时间为31.5h，装载量为22t，运送里程为910，达到了满意的优化结果。最后，我们又对所得出的方案进行了分析，找出其优缺点，提出了我们的一些改进意见，希望能够得到更加完善的方案。 关键词：路径优化 遗传算法 约束条件 适应度 罚函数 Matlab软件一、 问题重述1.1 问题背景车辆调度问题（Vehicle Routing Problem,简称VRP）问

5、题最早是由Dantzig和Ramser于1959年提出的。VRP问题的解法丰富，基本可以分为精确算法和启发式算法两大类。由于VRP属于强NP问题，运用精确算法求解计算量会随着问题规模的增大而呈现指数增加，因此，实际中其应用范围比较有限。实际应用中多采用启发式计算法，其种类也很多，常用的有：Clarke和Wright提出的CW节约启发式，Gillett和Miller提出的Sweep算法等。但这些算法也存在一定的问题，节约法虽然运算速度快，但是组合点零乱、边缘点难以组合，往往在客户数目较多、问题规模增大时，可行解的空间也相应增大，节约算法的优化效果也相应的下降；而扫描法为非渐进优化。随着科学的发展

6、，不断有新的算法引入到VRP的求解中来，例如，模拟退火算法，遗传算法，神经网络算法等。针对本题，我们主要采用了遗传算法。在此问题中，我们考虑到一个软硬时间窗的问题，关于这个问题，我们以题中实例来说。所谓软时间窗即配送车辆在运送过程中因到达时间不在规定范围内而产生的一些成本费用，这些费用在加上一个惩罚因子后可估计该损失。至于硬时间窗，在本题中指的是因车辆载重超重而产生的成本费用，由于车辆载重关乎安全等问题，所产生的损失较大，亦可使用惩罚因子来进行实际评估。软时间窗与硬时间窗的最根本区别在于，硬时间窗较软时间窗产生更巨大的损失。1.2 问题提出某物流中心拥有一支货运车队，为若干个客户配送物资，物流

7、中心与客户以及客户与客户之间的公路里程(千米)为已知。每天，各客户所需物资的重量(吨)均已知，并且每个客户所需物资的重量都小于一台货运车辆的载重量，所有送货车辆都从物流中心出发，最后回到物流中心。物流中心每天的配送方案应当包括：当天出动多少台车？行驶路径如何？由此形成的当天总运行里程是多少？一个合格的配送方案要求送货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到达将予以一定的惩罚。要求： 1. 建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。2. 对于载重量为 吨，平均速度为50千米/小时的送货车辆从物流中心()出发，为编号是=1,2,8的8个客户配送物资。某日

8、，第个客户所需物资的重量为吨，在第个客户处卸货时间为小时，第个客户要求送货车辆到达的时间范围由表1给出。物流中心与各客户以及各客户间的公路里程(单位:千米)由表2给出。问当日如何安排送货车辆(包括出动车辆的台数以及每一台车辆的具体行驶路径)才能使总运行里程最短。二、模型假设1、每个客户的货物有且只有由一辆货车运送。2、针对到达时间存在一个与成本相关的惩罚因子，而这个惩罚因子必然存在且为正解。3、对于车载量问题，我们制定一个超载系数，该超载系数与惩罚因子相似，但比惩罚因子要大得多，以严格控制安全和成本。4、不考虑在该问题中的一些意外事故问题，如车祸、红绿灯等。5、从配送中心出发的时间为0时。三、

9、符号说明为运货车辆数表示第辆车，是对装载车以及卸载车的复杂程度及约束多少的估计是指车辆的载重量客户及物流中心客户及物流中心客户及物流中心之和为车辆从客户行驶到客户的时间表示客户的运货任务开始时间为完成该任务的所需时间（本题主要指卸货）为任务允许最早开始时间为任务允许最迟开始的时间表示各项系数的值为第个染色体的适应度为当前染色体对应的运输路径四、问题一模型的建立与分析4.1 简单一般模型的建立本题针对的是物资配送中的路径优化问题，题意要求我们建立该类问题的一般数学模型。我们根据题中所给出的条件，分析得该问题可知，该问题的类型为有时间窗的非满载车辆调度问题。为了方便求解，将问题简化为某一个配送中心

10、对一定范围内的客户进行物流配送服务。配送中心根据不同的客户需求点安排路线执行配送任务，且各配送点所需货物量不超过运货车的车载量。根据题意，各需求点到配送中心的距离已知，客户规定配送车辆送货到达和完成的时间已知，由于题意中的配送车辆数未知，我们需要预先对需要的车辆进行评估。经过查阅文献资料，我们可按照下式确定车辆数： （1）式中，表示不大于括号数字的最大整数；，是对装载车以及卸载车的复杂程度及约束多少的估计，越复杂越小。在本题中，限制条件仅有时间，卸载车辆并不复杂，再根据所查阅的资料，将的值取为0.95。我们在此采用客户之间的距离，目标为使车辆总距离最短。我们将物流中心编号为0，客户及物流中心以

11、点来表示。设为车辆从点行驶到点的时间，用表示客户的运货任务开始时间， 为完成该任务的所需时间（本题主要指卸货）。设任务的开始时间需要在一定的时间范围内，其中为任务允许最早开始时间，为任务允许最迟开始的时间。如果车辆早于，则要加乘惩罚因子（对于此类问题，一般取2），如果车辆到达时间晚于，则要加乘惩罚因子（根据实际情况，一般取3）。如果车辆载重超过规定数，则要加乘超载惩罚因子（为严格满足容量约束，应取，但为了计算机的实现，在此取）。现定义变量如下： 车辆由点驶向点 否则 点的货运任务由车辆完成否则 则得到数学模型如下：目标函数： （1） 约束条件： （2） （3） （4） （5） （6） （7）

12、（8）在上述式子中，（1）式表示路程极小时的目标；（2）式表示运货车辆在客户规定的时间段内到达；（3）式表示点的货运任务只由一辆车完成；（4）式（5）式表示两个变量之间的关系（6）式和（7）式表示路线的可行性。为了使目标函数和约束条件处于同一量纲，我们引入了罚函数，即在加入惩罚因子的前提下，将约束条件融入目标函数中，最终得到了如下目标函数： 4.2 遗传算法的设计从建立的模型中，我们可以看到，求解车辆路径问题的关键是合理确定车辆和客户的关系，在满足约束条件的前提下，使总运距最小。由此我们借鉴一些遗传算法的例子构建了如下遗传算法。4.2.1 遗传算法的原理我们首先基于染色体结构对该问题进行分析。

13、采用自然编码，VSP的一条可行路线可以编成长度为的染色体，其中表示第辆车到第个客户，这样的染色体结构可以理解为车辆从物流中心出发，经过客户后回到物流中心，形成子路径1；而第二辆车也是从物流中心出发，经过后，返回物流中心0，从而形成了子路径2，如此反复，直到所有客户被访问到。这样，使染色体具有了子路径内部有序，而各个子路径之间无序的特征。通过Rnd子函数随机产生初始种群，然后在轮盘赌选择法的基础上，采用最佳个体保留选择策略，按照适应度的高低来选择双亲。再通过基因重组和染色体变异，产生子代。然后用子代代替父代，执行新一轮的进化，直到满足停止条件，产生最优个体，获得最优解。 遗传算法的步骤 Step

14、1 设置算法参数 种群数量eranum=200（代数取100-1000(默认200)）种群规模 popsize=100（种群规模取50-200(默认100)）交叉概率 pcross=0.8 (一般取0.5-0.85之间较好(默认0.8)初始变异概率pmutation=0.1 （一般取0.05-0.2之间较好(默认0.1)）Step2 产生初始种群Step3 计算种群中染色体的目标函数和适应度目标函数： 适应度：Step4 根据适应度选择双亲Step5 进行交叉遗传和变异遗传Step6 判断是否满足进化代数200代，如果进化代数满足200代，程序算法终止；若不满足，返回step34.3 一般求解

15、方法 对于此类问题，将实际问题具体给出的客户数量，货车最大载重量和车速，每个客户所需货物重量，在每个客户处的卸货时间，每个客户要求到达的规定时间范围以及客户与物流中心、客户与客户之间的距离代入以上数学模型，按照算法计算。在matlab上运行该遗传算法程序，得出近似最优解。五、问题二模型的建立与分析5.1 模型的建立根据问题一中所建立的一般数学模型，我们将题中所给的数据代入，就可以得到本题所需的模型。目标函数： 约束条件： 5.2 模型的求解在遗传算法的基础上，我们根据目标函数和约束条件通过matlab运行遗传算法程序，得出程序运行结果：g =0   &#

16、160; 6     4     0     8     5     7     0     3     1     2 

17、0;   0 fvalue =9105.3 优化模型的最终方案根据处理后的数据，我们得出了一个针对本题的使总运行里程最短的相对优化的路径最优方案：表一：配送最优方案配送车辆配送路线配送时间（h）车载量(t)运输里程(km)总惩罚时间(h)车辆1物流中心客户8客户5客户7物流中心11.974050车辆2物流中心客户3客户1客户2物流中心8.882400车辆3物流中心客户6客户4物流中心10.872650根据表一，我们得到最优方案为：出动车辆数为3辆 总行驶时间:31.5h 总车载量：22t 无惩罚时间 总运输里程最小为：910km其图形可以表示为：图二 最

18、优化配送路径六、模型评价与推广改进6.1 模型的评价优点：1、与问题领域无关切快速随机的搜索能力。2、搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较。3、搜索使用评价函数启发，过程简单。4、使用概率机制进行迭代，具有随机性。5、具有可拓展性，容易与其他算法结合。缺点：1、遗传算法的编程实现比较复杂，首先需要对问题进行编码，找到最优解之后还需要对问题进行解码。 2、另外三个算子的实现也有许多参数，如交叉率和变异率，并且这些参数的选择严重影响解的品质，而且这些参数的选择大部分是依靠经验。 3、没有能够及时利用网络的反馈信息，故算法的搜索速度比较慢，要得到较精确的解需要较多的训练时间。 4、算法对初始种群的选择有一定依赖性，能够结合一些启发算法进行改进。 5、算法的并行机制潜在能力没有得到充分的利用，这也是当前遗传算法的一个研究热点方向。在现在的工作中，遗传算法（1972年提出）已经不能很好的解决大规模计算量问题，它很容易陷入“早熟”。 采用何种选择方法既要使优良个体得以保留，又要维持群体的多样性，一直是遗传算法中较难解决的问题。6.2 模型的推广改进遗传算法不仅仅可以解决本题中1个物流中心与8个客户