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