带时间窗物流配送车辆路径问题..doc

带时间窗物流配送车辆路径问题 摘要 本题是一个带有时间窗的车辆路径安排问题（VRPTW问题）。根据题目条件，本文建立了一个求解最小派送费用的VRPTW优化模型，采用遗传算法，给出了该模型的求解方法。然后，对一个实际问题进行求解，给出了一个比较好的路线安排方式。 模型一（见5.1.2）针对问题一，在需求量、接货时间段、各种费用消耗已知的情况下，决定采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失。 模型一的求解采用遗传算法（见5.1.3），对题目给出的实际问题进行求解，得到3条行车路线，总路线长度为910公里，具体结果如下： 车辆编号 所执行的任务路线 到达各点的时间 路线长度 货运量 1 0-3-1-2-0 0-1.5-3.3-5.6-8.8 75+40+65+60=240 4.5+2+1.5=8 2 0-8-5-7-0 0-1.6-3.9-7.7-13.9 80+75+90+160=405 3+1.5+2.5=7 3 0-6-4-0 0-2-6-10.8 100+75+90=265 4+3=7 考虑在车辆返回时选择最短路线，我们采用Dijkstra算法求出中心仓库到各个客户的最短距离，将结果改进为885公里,具体结果如下： 车辆编号 所执行的任务路线 到达各点的时间 路线长度 货运量 1 0-3-1-2-0 0-1.5-3.3-5.6-8.8 75+40+65+60=240 4.5+2+1.5=8 2 0-8-5-7-2-0 0-1.6-3.9-7.7-13.9 80+75+90+135=380 3+1.5+2.5=7 3 0-6-4-0 0-2-6-10.8 100+75+90=265 4+3=7 模型二考虑需求量随机变化时的安排方案，假设客户需求量遵循正态分布，首先按照需求期望根据模型一得到一个比较好的方案，然后按照这一方案进行送货，在送货过程中，如果出现需求量过大的情况，允许车辆返回仓库进行补充。 模型一的思路清晰，考虑条件全面。但最优解解决起来困难，遗传算法只是一种相对好的解决方法，可以找出最优解的近似解。模型二的想法比较合理，易于实施，但还有待改进。 关键词：规划 时间窗 物流 车辆路径 遗传算法 问题重述 一个中心仓库，拥有一定数量容量为Q的车辆，负责对N个客户进行货物派送工作，客户i的货物需求量为，且，车辆必须在一定的时间范围内到达，早于到达将产生等待损失，迟于到达将处以一定的惩罚，请解决如下问题： （1）给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。并具体求解以下算例： 客户总数N=8,每辆车的容量Q=8（吨/辆）, 各项任务的货运量（单位：吨）、装货（或卸货）时间（单位：小时）以及要求每项任务开始执行的时间范围由附录1给出，车场0与各任务点以及各任务点间的距离（单位：公里）由附件二给出，这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短； （2）进一步请讨论当客户i的货物需求量为随机参数时的数学模型及处理方法。 问题分析 本题主要在种不同情况下，固定时，首先，我们根据题意，取若干辆车进行送货，然后，主要考虑每辆车各负责哪些客户的送货任务，我们可以给出满足题中限制条件的很多参考方案供选用，并考虑以所选行车路径产生的总费用最小为目标的情况下，建立最优化模型确定最佳的车辆派送方案。 进一步讨论，当客户i的货物需求量为随机参数时，我们首先可以简化随机模型，根据客户i的货物需求量的期望与方差，确定每天应该运送给客户i的货物量，即，再根据第一题，确定最佳的车辆派送方案。 但考虑到客户的储存能力有限及货物在客户处的储存费用，客户不需要将一天的货物一次性接收完，只要满足缺货的情况出现的概率很低，客户可以让配送中心一天几次送货，这样可以得到很多满足约束的方案，考虑以单位时间的储存费用最小为目标，建立最优化模型，确定配送中心给每位客户每次的配送量、配送周期与最有车辆行驶路径。 模型假设 每个客户的需求只能由一辆配送车满足； 每辆车送货时行驶的路程不超过它所能行驶的最远路程； 中心仓库的车辆总数大于或等于当派送费用最小时所需的车辆数； 从配送中心到各个用户、各个用户之间的运输距离已知； 配送中心有足够的资源以供配送。 符号说明 ：运货车的容量 ：该配送中心服务的客户总数 : 派送费用最小时所需的车辆数 ：第i位客户所需货物 ：车k由i驶向j ：点i的货运任务友s车完成 ：第i位客户最早允许接货时间 ：第i位客户最晚允许接货