数学建模送货路线设计问题论文 59页

送货路线设计问题一、问题重述1.1问题背景现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方。对于送货员而言，如何在按时将货物送到的前提下，使其送货耗时最少是一个不得不考虑的问题。基于上述情况，根据已有数据，运用数学建模的方法，对送货员的送货线路作出分析并提出合理建议是一个重要问题。准确分析进而制定出正确合理的决策，使送货员能在最短的时间内将货物送达顾客，对于提高公司名声、效益，创造和谐的社会坏境，节约能源等诸多方面都具有重要意义。1.2实际现状对送货员送货路线的要求主要有以下几个特点，如：1）送货员出于成本及节约时间的考虑，总是要使送货所用时间最省；-59- 2）由于受设备等的限制，送货员最大载重50公斤，所带货物最大体积1立方米；3）考虑顾客对商品的需求情况，有些货物必须在指定时间前送达；……这些因素都影响着送货路线最优化方案的设计。1.3问题提出从目标位置的实际分布情况以及上述要求出发，依据相关数据：1）在将1~30号货物送到指定地点并返回的前提下，建立一送货员送货线路模型，使得求得的最优化方案能够达到用时最省的目的；2）现实情况下，不同的顾客对货物的需求情况不同，有的顾客急需货物，就要求送货员在指定时间将货物送达。在进一步考虑顾客指定送货时间的情况下，制定出送货员的送货线路，使得送货员从早上8点上班开始送货，在不超过指定时间内将1~30号货物送达，并能够达到用时最省的目的；3）在1、2的基础上，若不考虑所有货物送达时间的限制(包括前30件货物)，并要将100件货物全部送到指定地点并返回，设计最快完成路线与方式。二、基本假设本题给出了送货员送货地点的网络图及相关数据，要求在不同的条件下送货的最佳路线。为解决此问题，需做如下的简化和抽象：-59- 1、由于送货指定地点的大小，与送货线路长相比，它们相对地小得多，故可以抽象的看做一个点。两指定送货地点之间的线路，省略其弯曲，抽象简化为直线段，而直线段的长即为此段线路的长度。于是线路网络图在数学上抽象为赋权图。将送货员的送货网络图中的每个指定地点看作图中的一个顶点，各指定地点之间的线路看作图中对应顶点之间的边，各线路的长度看做各条边的权。2、问题可归结为图上的优化问题：在给定的赋权图上寻找从给定点O出发，经过图上某些或全部点后，再回到该给定点且使得所用的总时间最省的闭路线。3、假设送货员送货过程中的时间消耗只来自于指定地点之间的行走和货物交接花费，忽略其他应突发情况（如堵车等）造成的时间消耗。说明：以上是模型讨论过程中的全局假设，在以后的分步讨论中我们可能引入新的局部性假设。三、符号说明及名词解释3.1基本符号G赋权图G′与赋权图G对应的完全赋权图V赋权图和完全赋权图的顶点e赋权图和完全赋权图的边赋权图和完全赋权图的权赋权图上任意两顶点之间的距离QH回路所对应的路程-59- Wg每件货物的重量Tj每件货物的体积N货物编号Sp送货员的行进速度T完成任务所需时间t限时时间控制变量3.2部分符号说明与名词解释上表所列符号并不完整，我们在后续各步中引入的新符号，到时再做说明。四、问题分析、模型建立与模型求解4.1问题一4.1.1问题分析问题一要求得，在将1~30号货物送到指定地点并返回的前提下，建立一用时最省的送货员送货线路模型。由于1~30号货物的总重量、总体积均未超出范围，且由MATLAB作图可以发现1~30号货物的送达地点相对集中（如图4.1.1），若只考虑1~30号货物的送达情况，可将问题一转化为从库房O点出发，行遍1~30号货物指定送达地点至少一次再回到O点，使得总权（路程）图4.1.1(大图见附录)-59- 最小，即最佳旅行售货员回路的问题，然后加以修正即得到最优解。但此问题是不可解的，即无法给出最优解，只能给出一种启发式算法，得到一个较优解。因此有如下思路：简化抽象最佳售货员回路问题问题的疑似最优解修正比较问题的近似最优解4.1.2模型建立-59- 单个售货员的最佳旅行售货员回路的问题是一个非常实际的问题，其本质是Hamilton回路的应用与引申，图论提法是在一个赋权图上寻求过每一个顶点至少一次的总权最小的路，即所谓的最短售货员回路。赋权H图的总权最小的回路称为最短H回路。一般地，在同一赋权图中，最短售货员回路与最短H回路不同。如图4..1.2图4.1.1所示，最短售货员回路为V1V2V1V3V1，权为4，而最短H回路为V1V2V3V1，权为5。这里我们不加证明的给出如下结论：若G=（V,E,W）中任意两个相异定点，均能满足三角不等式，则G中最短售货员回路与最短H回路相同。对于本题中的无向赋权图G，可以应用任意顶点对之间的最短路径算法构造一个等价完全赋权图,即在G′中各顶点对之间的权由他们之间的最短路径的权代替。显然，在G′中三角不等式均能满足，于是，由G′解得的最短H回路即为原无向赋权图G的最短售货员回路。4.1.2.1确立目标函数目标函数考虑完全赋权图G′的H回路使得总权最小:（4.1.1）其中，Q是H回路的总权，为G′中每条所走路线的权值；由于G′中各顶点对之间的权由它们之间的最短路径的权代替，故-59- 可由计算赋权图G中任意两点之间的最短路得到。这里我们采用Floyd算法：设G是赋权图，权为实数,|V|=nd(i,j):i到j的距离r(i,j)：i到j之间的插入点输入：带权邻接矩阵（1）赋初值：对所有（2）更新：对所有i，j，若，则（3）若k=n，停止。否则，转（2）4.1.2.2构造约束条件在第一问中约束条件主要考虑的是体积与重量的限制，于是有如下的约束条件：(4.1.2)实际上，我们在计算1~30号货物的中来重量与体积之后，发现它们的重量与体积均未超出范围，也就可以不考虑约束条件，于是问题转化为单纯的单售货员的最佳售货员回路问题，也就是与之对应的完全赋权图的最短H回路问题。4.1.2.3建立模型-59- 由前面的分析可得到问题一的模型是完全赋权图的最短H回路问题，即4.1.3模型求解由于问题一最终转化为单售货员的最佳售货员回路问题，进一步转化为了完全赋权回路的最短H回路问题。约束条件（1）表示H回路只能从出发一次，约束条件（2）表示H回路只能到达一次，约束条件（3）表示不会出现K个顶点构成的回路，K=2,3,…n-1。最短H回路问题属于NP完全问题，目前还没有找到有效的算法。这里我们考虑矩阵翻转实现的二边逐次修正法和遗传算法。-59- 矩阵翻转实现的二边逐次修正法首先构造完全赋权图，并用距离矩阵表示之，使所选初始圈的顶点为矩阵主对角线的上方元素对应的顶点；然后对距离矩阵加边框并进行若干次翻转，直到矩阵不满足二边逐次修正法的修正原则，最后得到的矩阵主对角线的上方元素确定了最佳H圈的权重和路线。算法如下：（1）任取初始H圈（2）对所有的，若，则C在中删去边而加入边，形成新的H圈（3）对C重复步骤二，直到条件不满足为止，最后得到的C即为所求遗传算法-59- 遗传算法（如图4.1.3）是从代表问题可能潜在的解集的一个种群开始，仿照基因编码的工作，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。图4.1.3遗传算法图解在编程实现方面，我们选择了遗传算法，MATLAB程序代码见附录。模拟得到的最佳结果如图4.1.4和图4.1.5说明：其他所得结果见附录-59- 图4.1.4最佳H圈图4.1.5最佳H圈搜索过程最短距离S=51051m，最短时间T=S/V+t=51051/400+3×30=218min-59- 其中，t为交接时间。4.1.4模型的优化在前面的求解过程中，由于1-30号货物的送达地点相对集中，故我们以这些点为主，搜索其最佳售货员回路。实际上，我们在构造邻接矩阵时已经将另外的点考虑在内，这也是对原模型的优化修正。4.2问题二4.2.1问题分析问题二中假定送货员从早上8点上班开始送货，要求1~30号货物的送达时间不能超过指定时间，设计出最快完成路线与方式并标出送货线路。由问题一的分析，我们已经知道最佳旅行售货员回路问题不可解的，即无法给出最优解，只能给出一种启发式算法，得到一个近似最优解，因此我们可以在问题一的基础上增加上时间限制条件，再进行最短H回路的搜索。算法如下：（1）求出赋权图G中任意两个顶点之间的的最短距离（采用Floyd算法），构造出完全赋权图；（2）随机产生一个存在潜在的解集的初始种群；（3）根据问题域中个体的适应度大小（主要是时间的限制方面）选择满足条件的个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。若不存在满足条件的个体，则重新产生初始种群；-59- （4）在第（3）步求出的所有H圈中，找出权最小的一个，此即要找的最优H圈的近似解。4.2.2模型建立4.2.2.1确立目标函数目标函数仍然考虑完全赋权图G′的H回路使得总权最小:（4.2.1）其中，Q是H回路的总权，为G′中每条所走路线的权值；4.2.2.2构造约束条件：由问题一得分析知道，1~30号货物的总重量、总体积均未超出范围，且由MATLAB作图可以发现1~30号货物的送达地点相对集中（见附录），这样只需考虑1~30号货物的送达时间情况。只要在指定时间前将货物送到就算满足条件，于是有约束条件其中，为第n件货物送达时送货员所用时间，为送货员从上班开始计时其送编号为n的货物的可用时间，具体数据见附录。-59- 4.2.2.3建立模型由前面的分析，并结合问题一所建立的模型，我们对问题二建立了如下模型：4.2.3模型求解-59- 由于问题二是建立在问题一的基础之上的，因而其求解思路与问题有相似之处。随机产生种群，接着进行其中个体是否满足送货时间的要求的判断，根据适者生存和优胜劣汰的原理，筛选出符合时间限制的个体，组成新的中间过渡种群，然后按照自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的下一代种群，这样逐代演化就会产生出越来越好的近似解。算法上，我们仍然采用遗传算法。由于加入了新的限制条件，故而在根据自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的下一代种群之前需进行一次判断，以排除其中不符合时间限制的个体。这一我们引入“中间过渡种群”的概念。中间过渡种群是指从上一代种群中按一定条件筛选出的满足要求的所有个体的集合。容易知道，中间过渡种群可以看作产生新的下一代种群的初始种群。对于约束条件的考虑，我们是对每一代种群中的每一个个体进行时间限制方面的考察。首先确定库房O点在每个个体中的位置，然后以O为起始点顺序读取其后的各个位置，并读进该位置的相关信息，包括送达该地货物的件数以确定交接时间、该位置与上一位置的最短距离以确定行车时间等，进而循环检测其后各个送货地点的到达时间是否满足条件。若全部满足，则将该个体放入中间过渡种群，用以产生新的下一代种群；若不满足，则将此个体排除。-59- 用MATLAB程序实现的最佳结果结果如下（图4.2.1和图4.2.2）：-59- 图4.2.1最佳H圈-59- 图4.2.2最佳H圈搜索过程最短距离S=60362m，最短时间T=S/V+t=60362/400+3×30=241min其中，t为交接时间。4.2.4通过模拟进行校验现在我们已利用MATLAB程序求得问题的近似最优解，需要对所建立的模型进行校验，测试此结果是否可以满足相应的时间限制，并且具有相应的较小的路径。4.2.4.1模拟规则及方法1、用MATLAB程序随机产生满足条件的最佳H圈，并还原成最佳售货员回路2、根据相应的时间限制校验各个指定地点是否满足条件3、若计算所得送货员达到指定地点的时间与所要求的时间相差不大，则可认为模型是合理的。4.2.4.2校验结果我们共对问题二的模型进行了10次模拟，全部基本符合要求。校验结果见附录。-59- 4.3问题三4.3.1问题分析问题三建立在问题一和在问题二的基础之上，要求设计出在不考虑货物送达时间的前提下，将100件货物全部送到指定地点并返回的最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。这个问题可以描述为:一中心仓库拥有最大载重50公斤，所带货物最大体积1立方米的送货员1人,负责对100个客户进行货物分送工作,客户i的货物需求为已知,求满足需求的路程最短的送货员行驶路径,并满足以下条件:1)送货员每次所载货物之和不超过个人最大负重，而且体积不能超过1立方米。2)每件货物必须送到指定地点；3）每次货物交接的时间为3分钟，途中速度为24km/h。4）为了计算方便，我们将货物一律用重量和体积来衡量，则货物总重量为148千克，总体积为2.8立方米。出于实际情况的考虑,我们对人的最大行程不加限制，试图从最优化的角度，建立起满足设计要求的送货的数学模型，借助于计算机的高速运算与逻辑判断能力，求出满足题意要求的结果。-59- 对于上述的路线确定问题，应用如下启发：从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未服务的送货点范围之内的邻居，并使各送货点总重量不超过50kg，总体积不超过1立方米。在上一售货员回到库房以后继续上述指派，直到没有未服务的送货点。对得到的可行的行程安排解中的每一条路径，求解一个最短售货员回路问题，决定指派给每一条行程的送货员的顺序，得到可行解的行程安排解后退出。4.3.2模型建立根据上述分析，问题三就可转换为我们熟悉的接力赛问题。这样我们就把一个送货员的问题转化成了多个送货员的接力问题。上面的方法通过以下两种方法实现：（1）每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总时间。（2）每一个行程的第一个送货点是距离总部最远的未服务的送货点，然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。然后比较两组结果，通过函数拟合即可得到最优化结果。4.3.2.1基本假设为求解模型，我们先做如下假设：（1）假设每个人的送货路线一旦确定，再不更改；（2）同一地点的货物必须在一次送完；-59- （3）如果到某一个点距离最近的点不至一个，就按下面的方法进行确定：考虑该点需求的货物量，将其从大到小依次排列，货物量需求大者优先，但路线中各点总重量加上该点的货物重量超过50kg或体积1立方米的上限时，该点舍去。另外，由常识我们知道回去取包裹的次数越少，越节省时间，而且此问题中至少需要分三次取包裹。在我们抽象简化的接力模型中，这一条件就转化为使用人数尽量少。4.3.2.2符号说明A所有送货点的集合C任意一点到库房的距离一条路线所运行的总公里数i,j表示送货点，如i点，j点KK条路线qi点i的需求量，q0=0，表示库房的需求量Xij送货员路线安排m接力问题中送货员人数注：A={0，1，2，3，…….，50}，其中0代表库房4.3.2.3模型建立由问题一和问题二以及上述分析可把问题三转化为多个售货员接力的最佳售货员回路问题，其数学描述如下：目标函数：约束条件：-59- 4.3.3模型求解下面用框图来说明两种方法的实现过程始开找离库房最近的点V且把该点标记为可到达，输出该点并记录货物的重量Wg1和体积Tj1找离V最近的点，到达该点货物的重量Wg2和体积Tj2，且有Wg1+Wg2<50，Tj1+Tj2<1，当不成立时找次近点没有符合条件的点。满足条件的点不止一个按假设(3)选择，该点设为设为已到达，输出该点，赋值给V，且Wg1=Wg1+Wg2。Tj1=Tj1+Tj2,-59- 图4.3.1方法一思路框图方法二的思路与方法一相同，这里不再重复论述。根据题目所给数据以及问题一、问题二中的导出数据，用MATLAB编程实现，得如下结果：方案一的图4.3.2和4.3.3，方案二的图4.3.4和4.3.5。-59- 方案一：图4.3.2最佳H圈图4.3.3最佳H圈的搜索过程-59- 最短距离S=161140m最短时间T=S/V+t=161140/400+3×100=703min方案二：图4.3.4最佳H圈-59- 图4.3.5最佳H圈的搜索过程最短距离S=158414m最短时间T=S/V+t=158414/400+3×100=696min经过比较方案一和方案二的结果，我们可以看出两种方案的走法时间相差不大，故我们认为方案一的线路和方案二的路线基本相同。五、模型分析5.1模型优点（1）本文针对一系列问题主要采取的是图论的模型，实用性和通用性较强；（2）在问题一的模型中我们从全部送货地点的整体情况出发，综合考虑前30号货物的送达情况，这对塑造模型起着至关重要的作用。-59- （3）在问题一的模型中，我们对最佳H圈的求解给出了两种算法，可以比较选择。（4）问题二不需要单独建立模型，可以移植问题一的算法，只需在增添限制条件。（5）问题三我们根据需要，将一个售货员问题转化为多个售货员的接力问题，不仅能起到简化问题的作用，而且带有一定的创新性；（6）每一问题我们都给出了几种不同的方案，使有关决策者可根据需要选取。5.2模型缺点（1）问题一中主要是针对1-30号货物的情况进行讨论，并对其周围的点加以修正，但还是不能保证所求解最优，但在全局范围内讨论会增加难度，故退而求其次；（2）问题三的解决可能有很多其他影响因素没有考虑在模型中,例如，售货员在回到库房取货，期间必有停留，但在模型中我们并未考虑。5.3模型的推广（1）本模型不但适合于快递公司送货问题，还是用于一般的送货以及运输问题，只需要稍微改动模型即可；（2）模型方便、直观，可以实现计算机模拟；-59- （3）建模的方法和思想可以推广到其他类型，如车辆调度问题等。六、参考文献[1]西北工业大学数学建模指导委员会.《数学建模简明教程》[M].北京:高等教育出版社,2008.[2]《数学建模基础教程》[M].北京:科学出版社,2007.[3]李天胜徐军.《数学模型应用实例》[M].合肥:合肥工业大学出版社,2007.[4]姜启源.《数学建模教程》[M].北京:清华大学出版社2005.[5]姜启源谢金星叶俊.《数学模型》（第3版）[M].北京:高等教育出版社，2003.[6]吴建国汪名杰李虎军刘仁云.《数学建模案例精编》（第1版）[M].北京：中国水利水电出版社，2005.[7]唐焕文、贺明峰.《数学模型引论》（第3版）[M].北京：高等教育出版社，2005.[8]杨秀文陈振杰李爱玲田艳芳.利用矩阵翻转法求最佳H圈[J].后勤工程学院学报,2008,24(1):102-106.-59- -59- 附录：附录一：相关数据表一G图中的互达信息与相邻两点的权位置点X坐标(米)Y坐标(米)G图中两点距离1131914.282182863.7832207823.314242292.645381958.096343536.417422592.3385155437.689521537.8110611294.31117185917.94-59- 12711968.25138121756.77149142681.35159101945.511610185909.55171072059.371811121417.681912131456.792012255756.572112155805.82213183113.462313193455.72413111669.562514185342.182614162607.682714172795.722814213296.732915222860.983015254235.43116232097.643217231774.513318312103.69-59- 3419242258.643520221498.933621262191.743721362880.183821171823.913922301287.494023171774.514124311780.154225414145.594325191966.214425291885.94527311067.754628331325.694729221097.86483028996.124930414997.625031261537.03表二1-30号货物送达地点的相关信息送达地点货物号不超过时间货物件数（min）1319：001601829：00160-59- 313,219：30290264,2312：00224021512：00124014612：00124017712：001240238，2912：002240329,17,2812：003240381010：1511354511,14,269：303904312,1610：152135391312：001240421510：151135361812：0012402719,2212：00224024209：0016034249：3019040259：30190492710：151135163012：001240-59- 表三完全赋权图中任意两顶点之间的权-59- -59- -59- 附录二：分析求解中的部分图形图11-30号货物送达地点示意图-59- 问题一的搜索结果举例：-59- 最短距离为54868m-59- 最短距离为53388m-59- -59- 最短距离为53388m-59- -59- 最短距离为53268m-59- -59- 最短距离为53268m-59- 问题二的搜索结果举例：最短距离为60700m-59- 最短距离为60362m-59- 附录三：相关程序代码Floyd算法：计算G图中任意两顶点之间的最短距离functionditance()city50=xlsread("shwt","sheet1");cango=xlsread("shwt","相互到达信息");fori=1:51forj=1:51if(i==j)DL50(i,j)=0;elseDL50(i,j)=inf;endendendfori=1:51forj=1:77if(cango(j,2)==i)DL50(i,cango(j,3))=((city50(i,1)-city50(cango(j,3),1))^2+(city50(i,2)-city50(cango(j,3),2))^2)^0.5;-59- DL50(cango(j,3),i)=DL50(i,cango(j,3));endendendd=DL50fori=1:51forj=1:51r(i,j)=j;endendfork=1:51fori=1:51forj=1:51a=d(i,k)+d(k,j);ifd(i,j)>ad(i,j)=a;r(i,j)=k;endendendend-59- 最短H回路算法：遗传算法求最佳H圈functiongaTSPCityNum=22;%城市数[dislist,Clist,goodc]=tsp(CityNum);%初始化TSP问题inn=100;%初始种群大小gnmax=200;%最大代数pc=0.8;%交叉概率pm=0.8;%变异概率num=0;%产生初始种群，顺序编码fori=1:inns(i,:)=randperm(CityNum);dn=size(s(i,:),2);end[f,p]=objf(s,dislist);%计算初始种群的适应值gn=1;%迭代次数whilegn