数模 送货路线设计问题论文

1、目录一、问题重述- 2 -1.1问题背景- 2 -1.2实际现状- 2 -1.3问题提出- 2 -二、基本假设- 3 -三、符号说明及名词解释- 3 -3.1基本符号- 3 -3.2部分符号说明与名词解释- 3 -四、问题分析、模型建立与模型求解- 4 -4.1问题一- 4 -问题分析- 4 -4.1.2 模型建立- 4 -模型求解- 6 -4.1.4 模型的优化- 7 -4.2问题二- 9 -问题分析- 9 -模型建立- 9 -模型求解- 10 -4.2.4 通过模拟进行校验- 11 -4.3问题三- 12 -问题分析- 12 -模型建立- 12 -模型求解- 14 -五、模型分析- 17

2、-5.1 模型优点- 17 -5.2 模型缺点- 17 -5.3模型的推广- 17 -六、参考文献- 17 -附录：- 19 -附录一：- 19 -附录二：- 23 -附录三：- 23 -送货路线设计问题一、问题重述1.1问题背景 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方。对于送货员而言，如何在按时将货物送到的前提下，使其送货耗时最少是一个不得不考虑的问题。基于上述情况，根据已有数据，运用数学建模的方法，对送货员的送货线路作出分析并提出合理建议是一个重要问题。准确分析进而制定出正确合理的决

3、策，使送货员能在最短的时间内将货物送达顾客，对于提高公司名声、效益，创造和谐的社会坏境，节约能源等诸多方面都具有重要意义。1.2实际现状对送货员送货路线的要求主要有以下几个特点，如：1）送货员出于成本及节约时间的考虑，总是要使送货所用时间最省；2）由于受设备等的限制，送货员最大载重50公斤，所带货物最大体积1立方米；3）考虑顾客对商品的需求情况，有些货物必须在指定时间前送达；这些因素都影响着送货路线最优化方案的设计。1.3问题提出 从目标位置的实际分布情况以及上述要求出发，依据相关数据： 1）在将130号货物送到指定地点并返回的前提下，建立一送货员送货线路模型，使得求得的最优化方案能够达到用时

4、最省的目的； 2）现实情况下，不同的顾客对货物的需求情况不同，有的顾客急需货物，就要求送货员在指定时间将货物送达。在进一步考虑顾客指定送货时间的情况下，制定出送货员的送货线路，使得送货员从早上8点上班开始送货，在不超过指定时间内将130号货物送达，并能够达到用时最省的目的；3）在1、2的基础上，若不考虑所有货物送达时间的限制(包括前30件货物)，并要将100件货物全部送到指定地点并返回，设计最快完成路线与方式。二、基本假设本题给出了送货员送货地点的网络图及相关数据，要求在不同的条件下送货的最佳路线。为解决此问题，需做如下的简化和抽象：1、由于送货指定地点的大小，与送货线路长相比，它们相对地小得

5、多，故可以抽象的看做一个点。两指定送货地点之间的线路，省略其弯曲，抽象简化为直线段，而直线段的长即为此段线路的长度。于是线路网络图在数学上抽象为赋权图。将送货员的送货网络图中的每个指定地点看作图中的一个顶点，各指定地点之间的线路看作图中对应顶点之间的边，各线路的长度看做各条边的权。2、问题可归结为图上的优化问题：在给定的赋权图上寻找从给定点O出发，经过图上某些或全部点后，再回到该给定点且使得所用的总时间最省的闭路线。3、假设送货员送货过程中的时间消耗只来自于指定地点之间的行走和货物交接花费，忽略其他应突发情况（如堵车等）造成的时间消耗。说明：以上是模型讨论过程中的全局假设，在以后的分步讨论中我

6、们可能引入新的局部性假设。三、符号说明及名词解释3.1基本符号G赋权图 G与赋权图G对应的完全赋权图V赋权图和完全赋权图的顶点e赋权图和完全赋权图的边赋权图和完全赋权图的权赋权图上任意两顶点之间的距离QH回路所对应的路程Wg每件货物的重量Tj每件货物的体积N货物编号Sp送货员的行进速度T完成任务所需时间t限时时间控制变量3.2部分符号说明与名词解释 上表所列符号并不完整，我们在后续各步中引入的新符号，到时再做说明。四、问题分析、模型建立与模型求解4.1问题一问题分析问题一要求得，在将130号货物送到指定地点并返回的前提下，建立一用时最省的送货员送货线路模型。由于130号货物的总重量、总体积均未

7、超出范围，且由MATLAB作图可以发现130），若只考虑130号货物的送达情况，可将问题一转化为从库房O点出发，行遍130号货物指定送达地点至少一次再回到O点，使得总权（路程） 图 4.1.1 (大图见附录)最小，即最佳旅行售货员回路的问题，然后加以修正即得到最优解。但此问题是不可解的，即无法给出最优解，只能给出一种启发式算法，得到一个较优解。因此有如下思路：简化抽象最佳售货员回路问题问题的疑似最优解 修正 比较问题的近似最优解4.1.2 模型建立单个售货员的最佳旅行售货员回路的问题是一个非常实际的问题，其本质是Hamilton回路的应用与引申，图论提法是在一个赋权图上寻求过每一个顶点至少一次

8、的总权最小的路，即所谓的最短售货员回路。赋权H图的总权最小的回路称为最短H回路。一般地，在 同一赋权图中，最短售货员回路与最短H回路不同。如 图 4.1.2图所示，最短售货员回路为V1V2V1V3V1，权为4，而最短H回路为V1V2V3V1，权为5。 这里我们不加证明的给出如下结论：若G=（V,E,W）中任意两个相异定点，均能满足三角不等式，则G中最短售货员回路与最短H回路相同。对于本题中的无向赋权图G，可以应用任意顶点对之间的最短路径算法构造一个等价完全赋权图,即在G中各顶点对之间的权由他们之间的最短路径的权代替。显然，在G中三角不等式均能满足，于是，由G解得的最短H回路即为原无向赋权图G的

9、最短售货员回路。l .1确立目标函数目标函数考虑完全赋权图G的H回路使得总权最小: （4.1.1）其中，Q是H回路的总权，为G中每条所走路线的权值；由于G中各顶点对之间的权由它们之间的最短路径的权代替，故可由计算赋权图G中任意两点之间的最短路得到。这里我们采用Floyd算法：设G是赋权图，权为实数,|V|=nd(i,j):i到j的距离r(i,j)：i到j之间的插入点输入：带权邻接矩阵（1）赋初值：对所有 （2）更新：对所有i，j，若，则（3）若k=n，停止。否则，转（2）l 构造约束条件在第一问中约束条件主要考虑的是体积与重量的限制，于是有如下的约束条件： (4.1.2)实际上，我们在计算13

10、0号货物的中来重量与体积之后，发现它们的重量与体积均未超出范围，也就可以不考虑约束条件，于是问题转化为单纯的单售货员的最佳售货员回路问题，也就是与之对应的完全赋权图的最短H回路问题。l .3 建立模型由前面的分析可得到问题一的模型是完全赋权图的最短H回路问题，即模型求解 由于问题一最终转化为单售货员的最佳售货员回路问题，进一步转化为了完全赋权回路的最短H回路问题。约束条件（1）表示H回路只能从出发一次，约束条件（2）表示H回路只能到达一次，约束条件（3）表示不会出现K个顶点构成的回路，K=2,3,n-1。最短H回路问题属于NP完全问题，目前还没有找到有效的算法。这里我们考虑矩阵翻转实现的二边逐

11、次修正法和遗传算法。l 矩阵翻转实现的二边逐次修正法首先构造完全赋权图，并用距离矩阵表示之，使所选初始圈的顶点为矩阵主对角线的上方元素对应的顶点；然后对距离矩阵加边框并进行若干次翻转，直到矩阵不满足二边逐次修正法的修正原则，最后得到的矩阵主对角线的上方元素确定了最佳H圈的权重和路线。算法如下：（1）任取初始H圈（2）对所有的，若，则C在中删去边而加入边，形成新的H圈（3）对C重复步骤二，直到条件不满足为止，最后得到的C即为所求l 遗传算法 遗传算法（如图4.1.3）是从代表问题可能潜在的解集的一个种群开始，仿照基因编码的工作，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越

12、好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 遗传算法图解在编程实现方面，我们选择了遗传算法，MATLAB程序代码见附录。 模拟得到的最佳结果如说明：其他所得结果见附录图4.1.4 最佳H圈 图4.1.5 最佳H圈搜索过程最短距离S=51051m，最短时间T=S / V+ t =51051/400+330=218min其中，t为交接时间。4.1.4 模型的优化 在前面的求解过程中，由于1

13、-30号货物的送达地点相对集中，故我们以这些点为主，搜索其最佳售货员回路。实际上，我们在构造邻接矩阵时已经将另外的点考虑在内，这也是对原模型的优化修正。4.2问题二问题分析问题二中假定送货员从早上8点上班开始送货，要求130号货物的送达时间不能超过指定时间，设计出最快完成路线与方式并标出送货线路。由问题一的分析，我们已经知道最佳旅行售货员回路问题不可解的，即无法给出最优解，只能给出一种启发式算法，得到一个近似最优解，因此我们可以在问题一的基础上增加上时间限制条件，再进行最短H回路的搜索。算法如下：（1）求出赋权图G中任意两个顶点之间的的最短距离（采用Floyd算法），构造出完全赋权图；（2）随

14、机产生一个存在潜在的解集的初始种群；（3）根据问题域中个体的适应度大小（主要是时间的限制方面）选择满足条件的个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。若不存在满足条件的个体，则重新产生初始种群；（4）在第（3）步求出的所有H圈中，找出权最小的一个，此即要找的最优H圈的近似解。模型建立l .1确立目标函数 目标函数仍然考虑完全赋权图G的H回路使得总权最小: （4.2.1）其中，Q是H回路的总权，为G中每条所走路线的权值；l 4.2.2.2 构造约束条件：由问题一得分析知道，130号货物的总重量、总体积均未超出范围，且由MATLAB作图可以发现130号货物的送

15、达地点相对集中（见附录），这样只需考虑130号货物的送达时间情况。只要在指定时间前将货物送到就算满足条件，于是有约束条件其中，为第n件货物送达时送货员所用时间， 为送货员从上班开始计时其送编号为n的货物的可用时间，具体数据见附录。l 4.2.2.3 建立模型由前面的分析，并结合问题一所建立的模型，我们对问题二建立了如下模型：模型求解 由于问题二是建立在问题一的基础之上的，因而其求解思路与问题有相似之处。随机产生种群，接着进行其中个体是否满足送货时间的要求的判断，根据适者生存和优胜劣汰的原理，筛选出符合时间限制的个体，组成新的中间过渡种群，然后按照自然遗传学的遗传算子进行组合交叉和变异，产生出代

16、表新的解集的下一代种群，这样逐代演化就会产生出越来越好的近似解。算法上，我们仍然采用遗传算法。由于加入了新的限制条件，故而在根据自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的下一代种群之前需进行一次判断，以排除其中不符合时间限制的个体。这一我们引入“中间过渡种群”的概念。中间过渡种群是指从上一代种群中按一定条件筛选出的满足要求的所有个体的集合。容易知道，中间过渡种群可以看作产生新的下一代种群的初始种群。对于约束条件的考虑，我们是对每一代种群中的每一个个体进行时间限制方面的考察。首先确定库房O点在每个个体中的位置，然后以O为起始点顺序读取其后的各个位置，并读进该位置的相关信息，包括

17、送达该地货物的件数以确定交接时间、该位置与上一位置的最短距离以确定行车时间等，进而循环检测其后各个送货地点的到达时间是否满足条件。若全部满足，则将该个体放入中间过渡种群，用以产生新的下一代种群；若不满足，则将此个体排除。用MATLAB程序实现的最佳结果结果如下（图4.2.1和图4.2.2）： 图4.2.1 最佳H圈 图4.2.2 最佳H圈搜索过程最短距离S=60362m，最短时间T=S / V+ t =60362/400+330=241min其中，t为交接时间。 通过模拟进行校验现在我们已利用MATLAB程序求得问题的近似最优解，需要对所建立的模型进行校验，测试此结果是否可以满足相应的时间限制

18、，并且具有相应的较小的路径。 l .1模拟规则及方法 1、用MATLAB程序随机产生满足条件的最佳H圈，并还原成最佳售货员回路 2、根据相应的时间限制校验各个指定地点是否满足条件3、若计算所得送货员达到指定地点的时间与所要求的时间相差不大，则可认为模型是合理的。l .2校验结果我们共对问题二的模型进行了10次模拟，全部基本符合要求。校验结果见附录。4.3问题三问题分析问题三建立在问题一和在问题二的基础之上，要求设计出在不考虑货物送达时间的前提下，将100件货物全部送到指定地点并返回的最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。这个问

19、题可以描述为:一中心仓库拥有最大载重50公斤，所带货物最大体积1立方米的送货员1人, 负责对100个客户进行货物分送工作, 客户i 的货物需求为已知 , 求满足需求的路程最短的送货员行驶路径,并满足以下条件:1) 送货员每次所载货物之和不超过个人最大负重，而且体积不能超过1立方米。2) 每件货物必须送到指定地点；3）每次货物交接的时间为3分钟，途中速度为24km/h。4）为了计算方便，我们将货物一律用重量和体积来衡量，则货物总重量为148千克，总体积为2.8立方米。出于实际情况的考虑, 我们对人的最大行程不加限制，试图从最优化的角度，建立起满足设计要求的送货的数学模型，借助于计算机的高速运算与

20、逻辑判断能力，求出满足题意要求的结果。对于上述的路线确定问题，应用如下启发：从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未服务的送货点范围之内的邻居，并使各送货点总重量不超过50kg，总体积不超过1立方米。在上一售货员回到库房以后继续上述指派，直到没有未服务的送货点。对得到的可行的行程安排解中的每一条路径，求解一个最短售货员回路问题，决定指派给每一条行程的送货员的顺序，得到可行解的行程安排解后退出。模型建立根据上述分析，问题三就可转换为我们熟悉的接力赛问题。这样我们就把一个送货员的问题转化成了多个送货员的接力问题。上面的方法通过以下两种方法实现：（1）每一个行程的第一个送

21、货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总时间。（2）每一个行程的第一个送货点是距离总部最远的未服务的送货点，然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。 然后比较两组结果，通过函数拟合即可得到最优化结果。l 4.3.2.1 基本假设为求解模型，我们先做如下假设：（1）假设每个人的送货路线一旦确定，再不更改； （2）同一地点的货物必须在一次送完；（3）如果到某一个点距离最近的点不至一个，就按下面的方法进行确定：考虑该点需求的货物量，将其从大到小依次排列，货物量需求大者优先，但路线中各点总重量加上该点的货物重量超过50kg

22、或体积1立方米的上限时，该点舍去。另外，由常识我们知道回去取包裹的次数越少，越节省时间，而且此问题中至少需要分三次取包裹。在我们抽象简化的接力模型中，这一条件就转化为使用人数尽量少。l 符号说明A所有送货点的集合C任意一点到库房的距离一条路线所运行的总公里数i,j表示送货点，如i点，j点KK条路线qi点i的需求量，q0=0，表示库房的需求量Xij送货员路线安排m接力问题中送货员人数注：A=0，1，2，3，.，50，其中0代表库房l 4.3.2.3模型建立由问题一和问题二以及上述分析可把问题三转化为多个售货员接力的最佳售货员回路问题，其数学描述如下：目标函数：约束条件： 模型求解下面用框图来说明

23、两种方法的实现过程始开 找离库房最近的点V且把该点标记为可到达，输出该点并记录货物的重量Wg1和体积Tj1找离V最近的点，到达该点货物的重量Wg2和体积Tj2，且有Wg1+ Wg250，Tj1+ Tj2a d(i,j)=a; r(i,j)=k; end end endend最短H回路算法：遗传算法求最佳H圈function gaTSPCityNum=22;%城市数dislist,Clist,goodc=tsp(CityNum);%初始化TSP问题inn=100; %初始种群大小gnmax=200; %最大代数pc=0.8; %交叉概率pm=0.8; %变异概率num=0;%产生初始种群，顺序编

24、码for i=1:inn s(i,:)=randperm(CityNum); dn=size(s(i,:),2);endf,p=objf(s,dislist);%计算初始种群的适应值gn=1;%迭代次数while gngnmax+1%判断是否达到最大迭代次数 for j=1:2:inn%从1开始，间隔为2，到种群大小，保证每次产生2个新个个体 seln=sel(s,p); %选择操作 scro=cro(s,seln,pc); %交叉操作 scnew(j,:)=scro(1,:);%获取进行变异的第1个个体 scnew(j+1,:)=scro(2,:);%获取进行变异的第2个个体 smnew(j

25、,:)=mut(scnew(j,:),pm); %对第1个个体进行变异操作 smnew(j+1,:)=mut(scnew(j+1,:),pm);%对第2个个体进行变异操作 end s=smnew; %产生了新的种群 f,p=objf(s,dislist); %计算新种群的适应度 fmax,nmax=max(f);%记录当前代最好和平均的适应度 ymean(gn)=1000/mean(f);%记录每一代种群的平均路径长度 ymax(gn)=1000/fmax;%记录每一代种群的最短路径长度 %ymax %输出 x=s(nmax,:);%记录当前代的最佳个体 drawTSP(Clist,x,yma

26、x(gn),gn,0);%画图 gn=gn+1; %pause;end %搜索结束for i=1:22goodc(x(i)%最优解顺序endgn=gn-1;figure(2);plot(ymax,r); hold on;%绘制最短路径变化曲线plot(ymean,b);grid;%绘制平均路径变化曲线title(搜索过程);legend(最优解,平均解);%text(5,5,最终搜索结果：最短距离 ,num2str(ymax);end%-%计算适应度函数function f,p=objf(s,dislist);%f为种群中每个个体的适应值，p为每个个体的累积选择概率inn=size(s,1);

27、 %读取种群大小for i=1:inn %依次计算种群中每个个体的路径长度 f(i)=CalDist(dislist,s(i,:); endf=1000./f;%取倒数，使路径短和个体具有较大的适应值%计算选择概率fsum=0;for i=1:inn fsum=fsum+f(i)15;endfor i=1:inn ps(i)=f(i)15/fsum;end%计算累积概率p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p;end%-function pcc=pro(pc);%根据交叉概率决定是否进行交叉操作%根据变异概率决定是否进行变异操作test(1

28、:100)=0;%令中所有数为0k=round(100*pc);%概率与100相乘后取整得ktest(1:k)=1;%令test中从1到k的数为1n=round(rand*99)+1;%随机数与99的积取整后加1pcc=test(n);%取test中的第个n数 end%-%“选择”操作function seln=sel(s,p);%s为当前种群，p为每个个体的累积选择概率inn=size(p,1);for i=1:2%从种群中选择两个个体 r=rand; %产生一个随机数 prand=p-r;%计算每个个体的累积选择概率与随机数之差 j=1; while prand(j)0%循环，直到找到一个

29、累积选择概率大于随机数的个体 j=j+1; end seln(i)=j; %选中个体的序号endend%-%“交叉”操作function scro=cro(s,seln,pc);%s为当前种群，seln为被选中的两个个体编号，pc为交叉概率bn=size(s,2);%获取个体的编码长度，即城市数pcc=pro(pc); %根据交叉概率决定是否进行交叉操作，1则是，0则否%torf=1;%while(torf)scro(1,:)=s(seln(1),:);%获取被选择的第1个个体scro(2,:)=s(seln(2),:);%获取被选择的第2个个体if pcc=1%如果要进行交叉 c1=roun

30、d(rand*(bn-2)+1; %在1,bn-1范围内随机产生一个交叉位 c2=round(rand*(bn-2)+1; %在1,bn-1范围内随机产生另一个交叉位 chb1=min(c1,c2);%获得交叉位的最小值 chb2=max(c1,c2);%获得交叉位的最大值 middle=scro(1,chb1+1:chb2);%获得第1个个体编码中位于两交叉点间的部分 scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2);%用第2个个体的中间部分替换第1个个体的中间部分 scro(2,chb1+1:chb2)=middle;%用第1个个体的中间部分替换第2个个体的中间部分 %-以下用部分映射交叉（PMX）