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

18
带时间窗物流配送车辆路径问题
摘要
本题是一个带有时间窗的车辆路径安排问题（VRPTW问题）。根据题目条件，本文建立了一个求解最小派送费用的VRPTW优化模型，采用遗传算法，给出了该模型的求解方法。然后，对一个实际问题进它所能行驶的最远路程；
中心仓库的车辆总数大于或等于当派送费用最小时所需的车辆数；
从配送中心到各个用户、各个用户之间的运输距离已知；
配送中心有足够的资源以供配送。
符号说明
：运货车的容量
：该配送中心服务的客户总数
: 派送费用最小时所需的车辆数
：第i位客户所需货物
：车k由i驶向j
：点i的货运任务友s车完成
：第i位客户最早允许接货时间
：第i位客户最晚允许接货时间
：车辆在第i位客户处等待时间
:车辆在第i位客户处迟到时间
：第i位客户处车辆到达时间
：从第i位客户到第j位客户所需时间
：第i位客户处装货（或卸货）所需时间
：第i位客户与第j位客户之间的距离
：车辆行驶单位距离的运输成本
：车辆早到单位时间产生的等待损失
：车辆迟到单位时间应承担的惩罚
：派送货物产生的总损失
A：运输成本
B：车辆早到所产生总的等待损失
C：车辆迟到所受的总惩罚
模型的建立和求解
问题一模型的建立及求解：

中心仓库为了给N个客户派送货物，供发出m辆车，为了派货的节约和方便，每辆车载着适量的货物出发，可以给某一片的若干个满足约束条件的客户派送货物，见图一：
3
图一 中心仓库派送货物图
中心仓如上图库派送货物时，必须满足约束条件：
各个客户群的总需求小于或等于运输车的装载量；
每个客户都必须且只能由一辆运输车运输所需货物；
运输车为每位客户开始服务的时间必须尽可能在时间窗内。
根据如上的约束条件，我们可以得到很多可行解，但考虑到以所选行车路径产生的总费用最小为目标的情况下，我们可以建立最优化模型确定最佳的车辆派送方案，最优路径产生图如下：
4
图二 最优路径产生图
模型的建立
（1）中心仓库使用车辆数量的确定
设配送中心需要向N个客户送货，每个客户的货物需求量是gi（i＝1，2，…..N），每辆配送车的载重量是Q，且gi<Q。首先为了安排路线需要对要使用的车辆数有一个估计。在现实情况中，货物装（卸）车越复杂，约束条件越多，一辆车的实际载货量就越小。在本文中使用文献[1]的公式来确定需要的车辆数m：
[ ]表示取整，a为参数，0<a<1。约束条件越多，货物装（卸） 越复杂，a值越小。参考文献[2]，。
（2）引入0—1变量：
1)表示车辆是否从客户行驶到客户。定义其为0—1变量，则

2)表示客户的任务由车辆完成。同样定义其为0—1变量，则
5

（3） 非线性规划模型的建立：
a．目标函数的确定。
题目要求所选行车路径产生的总费用最小，我们确定总费用为目标函数，记为。
总费用由运输成本A、等待损失B和迟到所收惩罚C组成，根据题意有：
所以，总费用Z最小化为：
b．约束条件的确定。
约束1：
车辆的运送总重量应不超过车辆的最大载重，即车辆有一定的运送能力，则可引入约束条件，
()
约束2：
每个客户只能由一辆车来配送，则可引入约束条件，

约束3：
保证到达一个客户的车辆也离开该客户，则可引入约束条件，
()
6
()
c．变量之间关系的确定
由上可确定等待时间，超时时间为：

车辆从客户到客户需经过两段时间为：

设车辆为客户运送完货物后即为客户运送，则到达客户处时间和到达客户处时间之间的关系为：

d．此非线性规划模型为：






8


我们采用遗传算法解决上面的问题：
1．编码
采用自然数编码，即序数编码。货物运输路线可以编成长度为N+m的染色体，其中，表示第项任务。0表示车场，m表示完成任务所需的车辆数。