1数学建模送货路线设计问题论文.doc

送货路线设计问题一、问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方对于送货员而言，如何在按时将货物送到的前提下，使其送货耗时最少是一个不得不考虑的问题基于上述情况，根据已有数据，运用数学建模的方法，对送货员的送货线路作出分析并提出合理建议是一个重要问题准确分析进而制定出正确合理的决策，使送货员能在最短的时间内将货物送达顾客，对于提高公司名声、效益，创造和谐的社会坏境，节约能源等诸多方面都具有重要意义对送货员送货路线的要求主要有以下几个特点，如：1〕送货员出于本钱及节约时间的考虑，总是要使送货所用时间最省；2〕由于受设备等的限制，送货员最大载重50公斤，所带货物最大体积1立方米；3〕考虑顾客对商品的需求情况，有些货物必须在指定时间前送达；……这些因素都影响着送货路线最优化方案的设计 从目标位置的实际分布情况以及上述要求出发，依据相关数据： 1〕在将1~30号货物送到指定地点并返回的前提下，建立一送货员送货线路模型，使得求得的最优化方案能够到达用时最省的目的； 2〕现实情况下，不同的顾客对货物的需求情况不同，有的顾客急需货物，就要求送货员在指定时间将货物送达。

在进一步考虑顾客指定送货时间的情况下，制定出送货员的送货线路，使得送货员从早上8点上班开始送货，在不超过指定时间内将1~30号货物送达，并能够到达用时最省的目的；3〕在1、2的根底上，假设不考虑所有货物送达时间的限制(包括前30件货物)，并要将100件货物全部送到指定地点并返回，设计最快完成路线与方式二、根本假设此题给出了送货员送货地点的网络图及相关数据，要求在不同的条件下送货的最正确路线为解决此问题，需做如下的简化和抽象：1、由于送货指定地点的大小，与送货线路长相比，它们相对地小得多，故可以抽象的看做一个点两指定送货地点之间的线路，省略其弯曲，抽象简化为直线段，而直线段的长即为此段线路的长度于是线路网络图在数学上抽象为赋权图将送货员的送货网络图中的每个指定地点看作图中的一个顶点，各指定地点之间的线路看作图中对应顶点之间的边，各线路的长度看做各条边的权2、问题可归结为图上的优化问题：在给定的赋权图上寻找从给定点O出发，经过图上某些或全部点后，再回到该给定点且使得所用的总时间最省的闭路线3、假设送货员送货过程中的时间消耗只来自于指定地点之间的行走和货物交接花费，忽略其他应突发情况〔如堵车等〕造成的时间消耗。

说明：以上是模型讨论过程中的全局假设，在以后的分步讨论中我们可能引入新的局部性假设三、符号说明及名词解释G赋权图 G′与赋权图G对应的完全赋权图V赋权图和完全赋权图的顶点e赋权图和完全赋权图的边赋权图和完全赋权图的权赋权图上任意两顶点之间的距离QH回路所对应的路程Wg每件货物的重量Tj每件货物的体积N货物编号Sp送货员的行进速度T完成任务所需时间t限时时间控制变量 上表所列符号并不完整，我们在后续各步中引入的新符号，到时再做说明四、问题分析、模型建立与模型求解问题一要求得，在将1~30号货物送到指定地点并返回的前提下，建立一用时最省的送货员送货线路模型由于1~30号货物的总重量、总体积均未超出范围，且由MATLAB作图可以发现1~30号货物的送达地点相对集中〔如图4.1.1〕，假设只考虑1~30号货物的送达情况，可将问题一转化为从库房O点出发，行遍1~30号货物指定送达地点至少一次再回到O点，使得总权〔路程〕 图 4.1.1 (大图见附录)最小，即最正确旅行售货员回路的问题，然后加以修正即得到最优解但此问题是不可解的，即无法给出最优解，只能给出一种启发式算法，得到一个较优解。

因此有如下思路：简化抽象 最正确售货员回路问题问题的疑似最优解 修正 比拟问题的近似最优解4.1.2 模型建立单个售货员的最正确旅行售货员回路的问题是一个非常实际的问题，其本质是Hamilton回路的应用与引申，图论提法是在一个赋权图上寻求过每一个顶点至少一次的总权最小的路，即所谓的最短售货员回路赋权H图的总权最小的回路称为最短H回路一般地，在 同一赋权图中，最短售货员回路与最短H回路不同如 图4.1.1所示，最短售货员回路为V1V2V1V3V1，权为4，而最短H回路为V1V2V3V1，权为5 这里我们不加证明的给出如下结论：假设G=〔V,E,W〕中任意两个相异定点，均能满足三角不等式，那么G中最短售货员回路与最短H回路相同。

对于此题中的无向赋权图G，可以应用任意顶点对之间的最短路径算法构造一个等价完全赋权图,即在G′中各顶点对之间的权由他们之间的最短路径的权代替显然，在G′中三角不等式均能满足，于是，由G′解得的最短H回路即为原无向赋权图G的最短售货员回路目标函数考虑完全赋权图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〕在第一问中约束条件主要考虑的是体积与重量的限制，于是有如下的约束条件： (4.1.2)实际上，我们在计算1~30号货物的中来重量与体积之后，发现它们的重量与体积均未超出范围，也就可以不考虑约束条件，于是问题转化为单纯的单售货员的最正确售货员回路问题，也就是与之对应的完全赋权图的最短H回路问题。

4.1.2.3 建立模型由前面的分析可得到问题一的模型是完全赋权图的最短H回路问题，即 由于问题一最终转化为单售货员的最正确售货员回路问题，进一步转化为了完全赋权回路的最短H回路问题约束条件〔1〕表示H回路只能从出发一次，约束条件〔2〕表示H回路只能到达一次，约束条件〔3〕表示不会出现K个顶点构成的回路，K=2,3,…n-1最短H回路问题属于NP完全问题，目前还没有找到有效的算法这里我们考虑矩阵翻转实现的二边逐次修正法和遗传算法矩阵翻转实现的二边逐次修正法首先构造完全赋权图，并用距离矩阵表示之，使所选初始圈的顶点为矩阵主对角线的上方元素对应的顶点；然后对距离矩阵加边框并进行假设干次翻转，直到矩阵不满足二边逐次修正法的修正原那么，最后得到的矩阵主对角线的上方元素确定了最正确H圈的权重和路线算法如下：〔1〕任取初始H圈〔2〕对所有的，假设，那么C在中删去边而参加边，形成新的H圈〔3〕对C重复步骤二，直到条件不满足为止，最后得到的C即为所求遗传算法 遗传算法〔如图4.1.3〕是从代表问题可能潜在的解集的一个种群开始，仿照基因编码的工作，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解 图 4.1.3 遗传算法图解在编程实现方面，我们选择了遗传算法，MATLAB程序代码见附录 说明：其他所得结果见附录 图4.1.4 最正确H圈 图4.1.5 最正确H圈搜索过程最短距离S=51051m，最短时间T=S / V+ t =51051/400+3×30=218min其中，t为交接时间 4.1.4 模型的优化 在前面的求解过程中，由于1-30号货物的送达地点相对集中，故我们以这些点为主，搜索其最正确售货员回路实际上，我们在构造邻接矩阵时已经将另外的点考虑在内，这也是对原模型的优化修正问题二中假定送货员从早上8点上班开始送货，要求1~30号货物的送达时间不能超过指定时间，设计出最快完成路线与方式并标出送货线路。

由问题一的分析，我们已经知道最正确旅行售货员回路问题不可解的，即无法给出最优解，只能给出一种启发式算法，得到一个近似最优解，因此我们可以在问题一的根底上增加上时间限制条件，再进行最短H回路的搜索算法如下：〔1〕求出赋权图G中任意两个顶点之间的的最短距离〔采用Floyd算法〕，构造出完全赋权图；〔2〕随机产生一个存在潜在的解集的初始种群；〔3〕根据问题域中个体的适应度大小〔主要是时间的限制方面〕选择满足条件的个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群假设不存在满足条件的个体，那么重新产生初始种群；〔4〕在第〔3〕步求出的所有H圈中，找出权最小的一个，此即要找的最优H圈的近似解 目标函数仍然考虑完全赋权图G′的H回路使得总权最小: 〔4.2.1〕其中，Q是H回路的总权，为G′中每条所走路线的权值；4.2.2.2 构造约束条件：由问题一得分析知道，1~30号货物的总重量、总体积均未超出范围，且由MATLAB作图可以发现1~30号货物的送达地点相对集中〔见附录〕，这样只需考虑1~30号货物的送达时间情况。

只要在指定时间前将货物送到就算满足条件，于是有约束条件 其中，为第n件货物送达时送货员所用时间， 为送货员从上班开始计时其送编号为n的货物的可用时间，具体数据见附录4.2.2.3 建立模型由前面的分析，并结合问题一所建立的模型，我们对问题二建立了如下模型： 。