约束条件越多，货物装（卸）越复杂，a值越小。
参考文献[2]，取a为0.85。
（2）引入0—1变量：
1）表示车辆是否从客户行驶到客户。
定义其为0—1变量，则
2）表示客户的任务由车辆完成。
同样定义其为0—1变量，则
（3）非线性规划模型的建立：
a．目标函数的确定。
题目要求所选行车路径产生的总费用最小，我们确定总费用为目标函数，记为。
总费用由运输成本A、等待损失B和迟到所收惩罚C组成，根据题意有：
所以，总费用Z最小化为：
b．约束条件的确定。
约束1：
车辆的运送总重量应不超过车辆的最大载重，即车辆有一定的运送能力，则可引入约束条件，
（）
约束2：
每个客户只能由一辆车来配送，则可引入约束条件，
约束3：
保证到达一个客户的车辆也离开该客户，则可引入约束条件，
（）
（）
c．变量之间关系的确定
由上可确定等待时间，超时时间为：
车辆从客户到客户需经过两段时间为：
设车辆为客户运送完货物后即为客户运送，则到达客户处时间和到达客户处时间之间的关系为：
d．此非线性规划模型为：
5.1.3模型的求解
我们采用遗传算法解决上面的问题：
1．编码
采用自然数编码，即序数编码。
货物运输路线可以编成长度为N+m的染色体，其中，表示第项任务。
0表示车场，m表示完成任务所需的车辆数。
2.出生初始群体
初始群体随机产生，即产生项货物运输任务点的全排列，如，如果，且，将s至N的数向后移动一位，将0插入第s位。
接着，继续上述操作，直到m个0全部插入为止。
这样就构成了一条初始染色体。
用这种方法构造一个群体的染色体。
如：
，该编码插零之后变成。
它代表着需要三辆车运输货物。
其中，第1辆车行走路线为，即从仓库出发到依次到8、2、5商店再回到仓库。
第2辆车行走路线为，第3辆车行走路线为。
3.适应度函数
适应度函数取，其中为染色体的适应度，b为常数，为初始种群中最好的染色体的运输成本，为染色体对应的运输成本。
4.遗传算子
选取最佳保留的轮盘赌复制法进行染色体的复制。
变异算子采用反转变异。
交叉算子用最大保留交叉，其操作过程为：
a）若染色体交叉点处的两个基因都为0，则直接进行顺序交叉运算；
b）若染色体交叉点处的基因不全为0，则将交叉点左移（右移），直到左右两个交叉处的基因都为0，再进行顺序交叉运算。
5.算法的实现步骤
Step1：
采用自然数编码的方式，构造表示可行车路线的染色体；
Step2：
设置控制参数，包括交叉率、变异率、群体规模；
Step3：
初始化，令，随机产生初始群体，群体中包括个染色体，每个染色体代表一条行车线路；
Step4：
令；
Step5：
将群体中的第个染色体译为线路长度；
Step6：
计算适应度；
Step7：
若满足算法终止条件，则停止，否则继续；
Step8：
；
Step9：
若，回到step5，否则，转step10；
Step11：
进行最大保留交叉、基于位的变异和倒位操作；
Step12:
；
Step13：
若满足算法终止条件，则停止，否则转step4。
运用matlab软件编写程序得到在车辆总行程最短的条件小的派送方案为：
车辆编号
所执行的任务路线
到达各点的时间
路线长度
货运量
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
从上表可以看出，按照上表的行车路线，总路线长度为910公里。
5.1.4结果分析
从上面解出的派送方案可以看出，上面的每条路线在车辆送完货物后，直接从最后一个客户处返回中心仓库，我们通过求中心仓库到各个客户的最短路径可以发现，上面的返回路线不是最优的，返回路线可以经过某些客户使得所走路线最短。
我们用Dijkstra算法求出中心仓库到各个客户的最短路径如下：
编号
0
1
2
3
4
5
6
7
8
最短距离
0
40
60
75
90
90
100
135
80
根据上表，我们对5.1.2所求的结果进行改进，得到下表：
车辆编号
所执行的任务路线
到达各点的时间
路线长度
货运量
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
根据上表计算结果，我们在不改变原路线的情况下，使总路线减小为885公里。
5.2问题二模型的建立及求解：
5.2.1问题的分析与假设
在问题一中，根据已知的各个商店的需求分布，根据遗传算法求解，预先确定一条总费用最小的路径（或者虽不是最优路径，但是此结果能够接受的）。
车辆沿该路径服务商店，因此服务商店的顺序固定不变。
而问题二中，在车辆服务商店的过程中，事先并不知道商店的需求量。
而这个不确定信息要随着车辆的服务逐步确定，商店具体的需求只有车辆到达用户后才确定。
这样第一问的求解方法得到的路径并不适用于第二问的求解。
假设：
（1）商店的需求变化符合正态分布，第个商店的需求量的期望和方差分别为和。
（2）商店的供货可以分为多次补充但在每次供货中最大程度满足用户需求，即只有出现当前车载余量小于用户需求量时才出现下一次的供货。
5.2.2模型的建立
基于第一问解决了在已知用户需求概率情况下，确定一个服务方案，满足所有n个商店的需求并且使车辆期望行程费用最小这个问题。
我们由假设可知，第个商店的需求量的期望为，则由需求量的期望得到一个使车辆期望行程费用最小的服务方案，称该方案为。
当用户的需求未知（当车辆服务商店时需求变成已知量）时，由于用户的需求量在区间的概率是96%，而在区间外的事件可以看成小概率事件，由小概率事件定理可知，在一次试验中，小概率事件可以看成不可能事件。
由此可知，用户需求量就在区间里。
用户需求在区间里，而需求决定服务方案。
由上面可知，服务方案在A方案附近变化，而变化的幅度由方差决定。
当越小时（说明需求量接近一个常数期望），最优方案（或满意方案）与方案越接近（即在方案上面稍作改动即可）。
反之，方案需作较大的方案。
由假设
（2）知，车辆只要满足当前用户部分需求，就服务该用户，用户未满足的部分以后再服务。
在服务用户后，车辆根据当前的位置信息、车载余量以及需要服务用户的信息，决定下一个服务用户（包括当前还未满足需求的用户）或回库房装载货物。
先按方案进行分配车辆路线（若增加车辆数目虽可以更好满足条件，但会增加多于开支）。
假设辆车都从仓库出发，按方案中的预定路线进行服务，当服务完第一个商店时，再判断剩余的货物量。
此时货物量为（其中为货车满载量，为车辆到达商店时确定了个商店的需求量）。
然后判断该剩余量是否在大于下一个商店需求量，若大于则进行下一个商店服务，若小于则判断下个商店是否满足大于这个条件，若满足，则对其进行服务，否则继续下个判断，直至其所有负责区域遍历完一遍。
当判断其负责区域所有的商店不满足条件时再判断该剩余量是否大于下一个商店需求量，若大于则进行下一个商店服务，若小于则判断下个商店是否满足大于这个条件，若满足，则对其进行服务，否则继续下个判断，直至其所有负责区域遍历完一遍。
若所有商店的需求量大于车辆货物剩余量，则说明此车辆的剩余量不能满足其所负责的区域，因此该车辆需要回仓库进行货物补充。
当货物补充完之后进行判断剩余未服务商店的时间窗口和路程距离进行判断（产生方法同于第二问方案的产生方法），然后再进行服务。
服务商店之后再进行前面的判断，直至其所有负责商店都被服务完回到仓库。
六、模型的评价和推广
6.1模型的评价
由5.1和5.2建立的模型，我们得到了有软时间限制的物流配送车辆路径问题的解决办法。
首先我们对问题进行了合理的假设，模型简化了实际中的复杂问题，考虑了主要的约束条件与目标，思路清晰，结果也基本符合实际。
但是，模型对实际进行简化的同时忽略了实际中很多次要的条件，由累加效果可能会产生很大误差，同时，我们进行模型的求解时只是简单使用了遗传算法，没有对其进行改进。
6.2模型的推广
1．模型中不合实际的假设：
（1）在问题一和问题二总费用的组成上，我们没有考虑组织送货的费用，即每组织一辆车进行送货都需要一定的费用，我们设为S元/（次、辆）；
（2）在问题一中，我们假设每辆车送货时行驶的路程不超过它所能行驶的最远路程，但是实际上，考虑到车辆行驶中的耗油等因素，每辆车的行驶最大距离都有限制，我们设车辆行驶的最大距离为L，我们可以得到约束条件：
（3）在实际中，为了公平，每位送货车辆司机行驶的路程相差必须控制在一定范围之内，我们取这个差值的最大允许值为M，则有：
2.模型的推广
根据以上目标函数与约束条件，带入实际数据，由遗传算法即可求解出总费用最小的车辆行驶路径方案。
七、参考文献
[1]李军，谢秉磊，郭耀煌，非满载车辆调度问题的遗传算法。
系统工程理论与实践，2000，20（3）：
235—239；
[2]邢文训，谢金星编著现代优化计算方法。
北京：
清华大学出版社，1999.140；
[3]魏明高成修胡润洲，一种带时间窗和容量约束的车辆路线问题及其TabuSearch算法，运筹与管理，Vol.11,No.3：
P49-P53，2002；
[4]胡大伟朱志强胡勇，车辆路径问题的模拟退火算法，中国公路学报，Vol.19No.4：
P123-P126,2006
[5]阎庆鲍远律，新型遗传模拟退火算法求解物流配送路径问题，，2009/8/16
[6]张志霞邵必林，基于改进蚁群算法的运输调度规划，公路交通科技，Vo1．25No．4：
P137-P140，2008；
[7]杜文衰庆达周再玲，一类随机库存/运输联合优化问题求解过程分析，中国公路学报，Vol.17No．1：
P114-P118，2004.
八、附录
9.1附录一
表1任务的特征及其要求
任务
1
2
3
4
5
6
7
8
（吨）
2
1.5
4.5
3
1.5
4
2.5
3
（小时）
1
2
1
3
2
2.5
3
0.8
[1,4]
[4,6]
[1,2]
[4,7]
[3,5.5]
[2,5]
[5,8]
[1.5,4]
表2点对之间的距离
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
0
40
60
75
90
200
100
160
80
40
0
65
40
100
50
75
110
100
60
65
0
75
100
100
75
75
75
75
40
75
0
100
50
90
90
150
90
100
100
100
0
100
75
75
100
200
50
100
50
100
0
70
90
75
100
75
75
90
75
70
0
70
100
160
110
75
90
75
90
70
0
100
80
100
75
150
100
75
100
100
0
9.2附录二
Matlab7.0程序：
functiongatsp（s）
sum=0;
M=1000000;%无穷大数
inn=100;
citynum=8;
K=2;
gnmax=1000;%最大代数
pm=0.8;%变异概率
pc=0.2;
c=[0,40,60,75,90,200,100,160,80;40,0,65,40,100,50,75,110,100;
60,65,0,75,100,100,75,75,75;75,40,75,0,100,50,90,90,150;
90,100,100,100,0,100,75,75,100;200,50,100,50,100,0,70,90,75;
100,75,75,90,75,70,0,70,100;160,110,75,90,75,90,70,0,100;
80,100,75,150,100,75,100,100,0];
q=[21.54.531.542.53];
s=[121322.530.8];
a=[14143251];
b=[46275.5584];
%--------------------------------------------------------------------------
%产生初始种群
m=zeros（1,inn）;
m=m';
KM=citynum+K-1;
s=zeros（inn,citynum+K-1）;
fori=1:
1:
inn
s（i,:
）=randperm（KM）;
end
s=[ms];
fori=1:
inn
forj=1:
KM-1
ifs（i,j）>citynum
s（i,j）=0;
end
end
end
%--------------------------------------------------------------------------
%主程序
functionga
[f,p]=objf（s）
gn=1;
whilegnforj=1:
2:
inn
seln=sell（s,ps）;%选择操作
scro=cross（s,seln,pc）;%交叉操作
scnew（j,:
）=scross（1,:
）;
scnew（j+1,:
）=scross（2,:
）;
smnew（j,:
）=chang（scnew（j,:
）,pm）;%变异操作
smnew（j+1,:
）=chang（scnew（j+1,:
）,pm）;
end
s=smnew;%产生了新的种群
[f,p]=objf（s,dislist）;%计算新种群的适应度
%记录当前代最好和平均的适应度
[fmax,nmax]=max（f）;
ymean（gn）=1/mean（f）;
ymax（gn）=1/fmax;
%记录当前代的最佳个体
升级会员 