数学建模_送货线路设计问题

《数学模型与数学软件综合训练》论文202311281796812112284210201212212422715344315训练题目：最优送货路线设计问题学生学号：07500124 姓名：呼德计通院信息与计算科学专业 指导教师：黄灿云 （理学院）2010年春季学期目录前言 (1)摘要 (2)关键字 (2)一、问题重述 (3)二、基本假设 (4)三、符号说明 (4)四、问题的分析 (5)五、模型的建立 (5)问题1： (5)问题2： (6)六、模型的优缺点 (8)1、优点： (8)2、缺点： (8)七．模型的推广 (8)八、参考文献 (9)数学模型与数学软件综合训练是信息与计算科学等数学类专业的一门重要的必修实践课程，是对学生的抽象思维能力、逻辑推理能力、运算能力、分析和解决实际问题能力进行综合培养的关键课程。

数学模型与数学软件综合训练是以问题为载体，应用数学知识建立数学模型，以计算机为手段，以数学软件为工具，以我们学生为主体，通过实验解决实际问题。

数学模型与数学软件综合训练是数学模型方法的实践，而数学模型方法是用数学模型解决实际问题的一般方法，它是根据实际问题的特点和要求，做出合理的假设，使问题简化，并进行抽象概括建立数学模型，然后研究求解所建的数学模型方法与算法，利用数学软件求解数学模型，最后将所得的结果运用到实践中。

数学模型与数学软件综合训练将数学知识、数学建模与计算机应用三者融为一体。

通过本次课程，可提高我们学习数学的积极性，提高我们对数学的应用意识，并培养我们用所学的数学知识、数学软件知识和计算机技术去认识问题和解决实际问题的能力。

我们自己动手建立模型，计算体验解决实际问题的全过程，了解数学软件的使用，也培养了我们的科学态度与创新精神。

当今社会，网购已成为一种常见的消费方式.随着物流行业的兴盛，如何用最短的时间，最节约成本的方案，完成送货任务显得尤为重要.针对本案例，我们采用了大量的科学分析方法，并进行了多次反复验证，得出如下结果：1：根据所给问题及有关数据，我们将题目中给出的城市，及其之间的线路可看成一个赋权连通简单无向图，采用了求这个图最小生成树的办法，求出最优线路.在此基础上，我们通过观察分析计算对上述结果进行修正，得出最终结果.2：根据所给问题，我们发现当货物不能一次送完时，中途需返回取货，而返回路径当然越短越好，可通过求途中两点最短路径的方法求出.关键字：送货线路优化，赋权连通简单无向图，Excel，最小生成树.一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，现有实业公司，该实业公司生产专业生产某专用设备产品，专用设备产品该每件重达5吨（其长5米，宽4米，高6米），该实业公司库房设在北京，所有货物均由一货机送货，该机种飞机翼展88.40米（机身可用宽20米），机长84米（可用长50米），机高18.2米（可用14米），最多可装载250吨货物，起飞全重达600吨，平均速度为900公里/小时）将货物送至全国各个省辖市（图1所示红色圆点，除北京之外共19个省辖市），假定货机只能沿这些连通线路飞行，而不能走其它任何路线；但由于受重量和体积限制，货机可中途返回取货.经过的各个省市都要一定的停靠费用和停靠时间（停靠时间为常量2小时），假设经过某个省市的停靠费用为：停靠费用=5000元×该省市的消费指数；问题1：若图示中19个省辖市每个省辖市只要一件产品请设计送货方案，使所用时间最少，标出送货线路.问题2：若图示中19个省辖市需求量见表1，请设计送货方案，使所用时间最少.问题3：若该实业公司为了花费最少，针对问题1和问题2分别求出花费、标出送货线路.表202311281796812112284210201212212422715344315二、基本假设1.假设货物在存放中，货物与货物之间无空隙.2.飞机在出行送货期间，无天气突变等突发状况.3.飞机自身无任何故障，并且在空中始终以平均速度为900公里/小时.4.假定货机只能沿着图中的连通路线飞行，而不走其他的路线.三、符号说明在地图上城市可以用点表示如北京可用A4表示，详细见下表.AiAj ：点Ai到点Aj的线段权（1）：表示题目中给出的两城市之间的权，如北京—上海（A1A5）的权（1）为9. 权（2）：表示通过两城市之间路程所花费的时间，如北京—上海（A1A5）的权（2）为9*100/900+2=3（小时）权（3）：表示通过两城市之间路程的花费，如北京—上海（A1A5）的权（3）为9*2500+1.85*5000=31750（小时），1.85为两城市指数的平均值.V ：A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A12，A13，A14，A15，A16，A17，A18，A19，A20的集合.E ：A1A2，A1A3，A1A5，A1A6，A2A4，A3A10，A4A10，A4A12，A4A13，A4A16，A4A5，A4A7，A5A14，A5A15，A6A14，A6A8，A7A10，A7A12，A7A19，A8A9，A9A11，A10A11，A10A19，A10A20，A11A12A，12A18，A13A16，A13A17，A17A18，A19A20的集合.W ：V中点之间的权（2）的集合，则G=（V，E，W）表示赋权连通简单无向图M ：V中点之间的权（3）的集合，则F=（V，E，M）表示赋权连通简单无向图四、问题的分析当今社会，网购已成为一种常见的消费方式.随着物流行业的兴盛，如何用最短的时间，最节约成本的方案，完成送货任务显得尤为重要.针对本案例，城市可以看成点，而他们之间的连线既可以看成是时间，也可以看成成本，那么就构成了两个赋权连通简单无向图，这个问题就转化成求这两种情况下，两种图的最小生成树问题.五、模型的建立问题1：根据题目意思，两城市之间的时间=权（1）*100/速度+2（单位：小时）例如北京到上海A4A5权（1）是17，则定义V为A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A12，A13，A14，A15，A16，A17，A18，A19，A20的集合，定义E为A1A2，A1A3，A1A5，A1A6，A2A4，A3A10，A4A10，A4A12，A4A13，A4A16，A4A5，A4A7，A5A14，A5A15，A6A14，A6A8，A7A10，A7A12，A7A19，A8A9，A9A11，A10A11，A10A19，A10A20，A11A12A，12A18，A13A16，A13A17，A17A18，A19A20的集合，定义W为V中点之间的权（2）的集合，则G=（V，E，W）表示图.根据最小生成树的求法可以求出改图G的最小生成树如图沿着最小生成树的路线相对较短，为：A4—A5—A15—A5—A14—A6—A8—A9—A11—A10—A20—A10—A19—A10—A11—A12—A18—A17—A13—A16—A4—A7—A4—A2—A1—A3—A1—A2—A4经过观察上面下划线的部分A11—A10—A20—A10 —A19—A10—A11并不是最短的，经计算这个路线A11—A10—A20—A19—A10—A11比上一个段，所以用之替换，得到最短的线路为：A4—A5—A15—A5—A14—A6—A8—A9—A11—A10—A20—A19—A10—A11—A12—A18—A17—A13—A16—A4—A7—A4—A2—A1—A3—A1—A2—A4可以将相邻两点的权（2）相加，和即为花费，经过计算上述线路所花时间是76.44444小时，为最短时间.问题2：根据题目意思，两城市之间运输的价格=权（1）*2500+平均指数*5000（单位：价格）例如北京到上海A4A5权（1）是17，北京的指数为1.9，上海为1.8，则先求出平均指数（1.9+1.8）/2=1.85，根据公式可得北京到上海A4A5关于时间的运输价格的权为9*2500+1.85*5000=31750（小时），其定义M 为V 中点之间的权（3）的集合，则P=（V ，E ，M ）表示图，根据最小生成树的求法可以求出改图P 的最小生成树如图同样的，沿着最小生成树的路线相对较短，为：A4—A5—A15—A5—A14—A6—A8—A9—A11—A10—A20—A10—A19—A10—A11—A12—A7—A12—A18—A17—A13—A16—A4—A2—A1—A3—A1—A2—A4经过观察上面下划线的部分A11—A10—A20—A10—A19—A10—A11并不是最短的，经计算这个路线A11—A10—A20—A19—A10—A11比上一个段，所以用之替换，得到最短的线路为：A4—A5—A15—A5—A14—A6—A8—A9—A11—A10—A20—A10 —A19—A10—A11—A12—A7—A12—A18—A17—A13—A16—A4—A2—A1—A3—A1—A2—A4可以将相邻两点的权（3）相加，和即为花费，经过计算上述线路所花运输花费是687000元，为最少花费.六、模型的优缺点1、优点：⑴、本文总共有三个问题，给出了在各种约束条件下的最短时间以及最少花费的计算方法，具有较强的实用性和通用性，在日上生活中经常可以用到。

数学建模_送货线路设计问题送货路线设计问题1、问题重述现今社会⽹络越来越普及,⽹购已成为⼀种常见的消费⽅式,随之物流⾏业也渐渐兴盛,每个送货员需要以最快的速度及时将货物送达,⽽且她们往往⼀⼈送多个地⽅,请设计⽅案使其耗时最少。

现有⼀快递公司,库房在图1中的O点,⼀送货员需将货物送⾄城市内多处,请设计送货⽅案,使所⽤时间最少。

该地形图的⽰意图见图1,各点连通信息见表3,假定送货员只能沿这些连通线路⾏⾛,⽽不能⾛其它任何路线。

各件货物的相关信息见表1,50个位置点的坐标见表2。

假定送货员最⼤载重50公⽄,所带货物最⼤体积1⽴⽅⽶。

送货员的平均速度为24公⾥/⼩时。

假定每件货物交接花费3分钟,为简化起见,同⼀地点有多件货物也简单按照每件3分钟交接计算。

现在送货员要将100件货物送到50个地点。

请完成以下问题。

1、若将1~30号货物送到指定地点并返回。

设计最快完成路线与⽅式。

给出结果。

要求标出送货线路。

2、假定该送货员从早上8点上班开始送货,要将1~30号货物的送达时间不能超过指定时间,请设计最快完成路线与⽅式。

要求标出送货线路。

3、若不需要考虑所有货物送达时间限制(包括前30件货物),现在要将100件货物全部送到指定地点并返回。

设计最快完成路线与⽅式。

要求标出送货线路,给出送完所有快件的时间。

由于受重量与体积限制,送货员可中途返回取货。

可不考虑中午休息时间。

2、问题分析送货路线问题可以理解为:已知起点与终点的图的遍历问题的合理优化的路线设计。

图的遍历问题的指标:路程与到达的时间,货物的质量与体积,以及最⼤可以负载的质量与体积。

在路线的安排问题中,考虑所⾛的路程的最短即为最合理的优化指标。

对于问题⼆要考虑到所到的点的时间的要求就是否满⾜题意即采⽤多次分区域的假设模型从⽽找出最优的解对于问题三则要考虑到体积与质量的双重影响,每次到达后找到达到最⼤的体积与质量的点然后返回,再依次分析各个步骤中可能存在的不合理因素达到模型的进⼀步合理优化得到最合理的解。

货物配送问题【摘要】本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题提出的方案。

我们首先考虑在满足各个公司的需求的情况下，所需要的运输的最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了较为合理的优化模型，求出较为优化的调配方案。

针对问题一，我们在两个大的方面进行分析与优化。

第一方面是对车次安排的优化分析，得出①~④公司顺时针送货，⑤~⑧公司逆时针送货为最佳方案。

第二方面我们根据车载重相对最大化思想使方案分为两个步骤，第一步先是使每个车次满载并运往同一个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B材料有优先运输权；在第三批次中运输剩下所需的货物。

最后得出耗时最少、费用最少的方案。

耗时为40.5007小时，费用为4685.6元。

针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。

我们采取与问题一相同的算法，得出耗时最少，费用最少的方案。

耗时为26.063小时，费用为4374.4元。

针对问题三的第一小问，我们知道货车有4吨、6吨和8吨三种型号。

我们经过简单的论证，排除了4吨货车的使用。

题目没有规定车子不能变向，所以认为车辆可以掉头。

然后我们仍旧采取①~④公司顺时针送货，⑤~⑧公司逆时针送货的方案。

最后在满足公司需求量的条件下，采用不同吨位满载运输方案，此方案分为三个步骤：第一，使8吨车次满载并运往同一公司；第二，6吨位车次满载并运往同一公司；第三，剩下的货物若在1~6吨内，则用6吨货车运输，若在7~8吨内用8吨货车运输。

最后得出耗时最少、费用最省的方案。

耗时为19.6844小时，费用为4403.2。

一、问题重述某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。

路线是唯一的双向道路(如图１)。

货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。

B题快递公司送货策略摘要本文主要解决快递公司送货策略问题，研究在各种运货地点，重量的确定，业务员的运输条件和工作时间等各种约束条件下，设计最优的路线，得出最优送货策略。

主要研究如下三个问题。

问题一：首先考虑在时间和重量两个约束条件之下，优先考虑重量，通过对送货点的分布进行分析，将分布点按照矩形，弧形和树的理念将问题分成三种模块，从而建立三种送货方案。

方案一，运用矩形，将整个区域分成5个区域，以选择的点的送货质量之和小于25kg 且距离尽可能小的点的集合作为一个区域。

依次来分配业务员的送货地点。

方案二，运用弧形，以原点为圆心画同心圆，按照就近原则确定送货区域，依次分配业务员的送货地点。

方案三，运用Dijkstra 算法计算出每一个顶点到其它点的距离。

分析点的分布，由此得到最小树，在最小树的基础上，向四周延伸，得到相应区域。

且以送货质量小于25kg且距离尽可能小的点的集合作为一个区域。

依次来分配业务员的送货地点。

其次，再综合这三种方案所涉及到得时间，路程依次进行对比，画出柱形图，清晰可得出最优的方案为方案三。

问题二，是解决送货总费用最小的问题。

因此要求业务员的运行路线要尽量短，且尽早卸货。

首先将该区域安排送货点均匀度分为三个小区域，以每个点的信件质量从小到大排列，以送货点最大点为中心，选择该点附近质量较大且距离较短原则的下一个送货点，依次类推，直到根据约束条件为每次携带的快件量不超过25kg，找到该条路线最后一个送货点。

按此方法可得路线为0→10→12→11→0，0→7→14→27→0，0→1→26→28→0，0→13→19→25→0，0→2→5→16→17→0，0→22→15→29→30→0，0→6→20→18→24→0，0→4→3→8→9→21→23→0，并且利用C语言编程（见附录），算得每条路线的费用，所得总费用为14636.1元。

问题三，在问题一的基础上，将业务员的工作时间延长到8小时，由此在问题一的基础上，将8小时的工作时间所需花费的费用在三个方案中进行对比，由此得到依旧是方案三的为最优。

解决送货问题可以使用数学建模的方法，以下是一个基本的数学建模过程：
1. 定义问题：明确问题的背景和目标。

例如，送货问题可以定义为如何选择最佳的送货路线，以便在给定时间内尽可能快速地送达所有货物。

2. 建立数学模型：根据问题的特点，选择适当的数学模型来描述问题。

送货问题可以使用图论中的旅行商问题（Traveling Salesman Problem，TSP）进行建模。

在TSP中，每个送货点被看作是图中的节点，送货点之间的距离被看作是节点之间的边。

3. 确定目标函数：定义用于衡量送货路线的优劣的目标函数。

对于送货问题，可以选择目标函数为总送货距离或送货时间。

4. 添加约束条件：考虑问题中的各种约束条件，如送货员的工作时间限制、访问某些送货点的次序要求等。

5. 求解问题：使用优化算法来求解建立的模型。

对于TSP问题，可以使用蚁群算法、遗传算法等启发式算法来寻找最佳的送货路线。

6. 模型评估和优化：对求解结果进行评估，看是否满足问题的要求。

如果不满足，可以进行参数调整或尝试其他算法来优化模型。

7. 结果解释和应用：将最终的送货路线结果解释给相关人员，并将其应用于实际的送货任务中。

需要注意的是，送货问题的具体建模方法和求解策略可能因问题的具体情况而有所差异。

在实际应用中，还需要考虑更多的因素，如送货量、交通状况、车辆容量等。

因此，在进行数学建模时，要根据实际情况进行灵活调整和优化。

货物配送问题数学建模一、问题描述在物流配送中，如何合理地安排货物的配送路线，使得货物能够最快地到达目的地，同时保证配送成本最小化，是一个重要的问题。

本文将以某物流公司为例，探讨如何利用数学建模的方法解决货物配送问题。

二、问题分析该物流公司需要将货物从A地配送到B地，其中A地有n个发货点，B地有m个收货点。

每个发货点的货物重量不同，每个收货点的需求量也不同。

为了保证配送效率，该物流公司需要在每个发货点选择最优的配送路线，使得货物能够最快地到达目的地，同时保证配送成本最小化。

具体而言，该问题需要考虑以下因素：1.货物重量：每个发货点的货物重量不同，需要考虑不同重量的货物在配送过程中的影响。

2. 配送路线：如何选择最优的配送路线，使得货物能够最快地到达目的地，同时保证配送成本最小化。

3. 配送成本：配送成本包括人工成本、车辆成本、油费等，需要考虑如何在保证配送效率的同时最小化配送成本。

三、数学建模为了解决上述问题，我们可以采用数学建模的方法。

具体而言，我们可以将该问题建模为一个最小费用最大流问题。

最小费用最大流问题是图论中的一个经典问题，其主要思想是在网络流的基础上，引入费用这一概念，使得在满足流量限制的同时，最小化总费用。

在本问题中，我们可以将发货点看作源点，收货点看作汇点，货物的重量看作每个边的流量限制，配送成本看作每个边的费用。

具体而言，我们可以将该问题建模为以下几个步骤：1. 建立网络模型：将发货点和收货点看作网络中的节点，将货物的配送路线看作网络中的边，建立网络模型。

2. 确定流量限制：将每个发货点的货物重量看作每个边的流量限制。

3. 确定费用：将配送成本看作每个边的费用。

4. 求解最小费用最大流：利用最小费用最大流算法，求解最小费用最大流，得到最优的配送路线。

四、实际案例为了验证上述方法的有效性，我们在某物流公司的实际配送中进行了测试。

具体而言，我们将该问题建模为一个最小费用最大流问题，并利用最小费用最大流算法求解最优的配送路线。

B题快递公司送货策略摘要本文主要解决快递公司送货策略问题，研究在各种运货地点，重量的确定，业务员的运输条件和工作时间等各种约束条件下，设计最优的路线，得出最优送货策略。

主要研究如下三个问题。

问题一：首先考虑在时间和重量两个约束条件之下，优先考虑重量，通过对送货点的分布进行分析，将分布点按照矩形，弧形和树的理念将问题分成三种模块，从而建立三种送货方案。

方案一，运用矩形，将整个区域分成5个区域，以选择的点的送货质量之和小于25kg 且距离尽可能小的点的集合作为一个区域。

依次来分配业务员的送货地点。

方案二，运用弧形，以原点为圆心画同心圆，按照就近原则确定送货区域，依次分配业务员的送货地点。

方案三，运用Dijkstra 算法计算出每一个顶点到其它点的距离。

分析点的分布，由此得到最小树，在最小树的基础上，向四周延伸，得到相应区域。

且以送货质量小于25kg且距离尽可能小的点的集合作为一个区域。

依次来分配业务员的送货地点。

其次，再综合这三种方案所涉及到得时间，路程依次进行对比，画出柱形图，清晰可得出最优的方案为方案三。

问题二，是解决送货总费用最小的问题。

因此要求业务员的运行路线要尽量短，且尽早卸货。

首先将该区域安排送货点均匀度分为三个小区域，以每个点的信件质量从小到大排列，以送货点最大点为中心，选择该点附近质量较大且距离较短原则的下一个送货点，依次类推，直到根据约束条件为每次携带的快件量不超过25kg，找到该条路线最后一个送货点。

按此方法可得路线为0→10→12→11→0，0→7→14→27→0，0→1→26→28→0，0→13→19→25→0，0→2→5→16→17→0，0→22→15→29→30→0，0→6→20→18→24→0，0→4→3→8→9→21→23→0，并且利用C语言编程（见附录），算得每条路线的费用，所得总费用为14636.1元。

问题三，在问题一的基础上，将业务员的工作时间延长到8小时，由此在问题一的基础上，将8小时的工作时间所需花费的费用在三个方案中进行对比，由此得到依旧是方案三的为最优。

快递公司的配送问题摘要配送是物流系统中非常重要的一个环节，在物流的各项成本中，配送成本占了相当高的比例，减少配送里程以降低物流配送成本成为物流管理过程中首要考虑的问题之一。

本文在已知货运车容量、各客户所需货物重量、快递公司与客户以及客户与客户之间的距离的条件下，建立了以单车场路径问题模型（即VRP模型）为基础、以车辆总行程最短为目标函数、以货物运输量小于汽车载重量以及在客户要求的时间范围内运送货物等为约束条件的单目标线性规划模型。

对于问题一，本文建立了两个模型：模型I：硬时间窗车辆路径规划模型首先根据题目所给条件，对运货所需的车辆数进行预估，然后结合货物运输量小于汽车载重量、一个客户点的货物仅由一辆车配送等约束条件，同时考虑线路的连通性和汽车到达客户点的时间范围，采用0-1规划法建立使总运行里程最小的车辆路径规划模型。

模型II：软时间窗车辆路径规划模型在模型I硬时间窗车辆路径规划模型的基础上，将模型I中的关于时间范围的约束条件，通过设定惩罚函数的系数，变成目标函数的一部分。

本文在考虑路程最短的目标的同时，也要求尽可能在时间范围内到达。

因此，建立了以成本（包括惩罚成本以及行驶过程中带来的成本）最小为目标的函数，以运输量小于汽车载重量以及线路的连通性等为约束条件，建立软时间车辆路径规划模型。

最后运用遗传算法求解模型。

对于问题二，根据题目所提供的数据，利用硬时间窗车辆路径规划模型。

首先，根据货运车的载重量和客户点的需求总量，估计出运货所需车辆数为3，然后，借助Lingo 求解该模型。

得到最优路径的总里程数为910千米，快递公司每天的配送方案应为:每天出动3辆车。

3辆车的行驶路径分别为：0->3->1->2->0，0->6->4->0，0->8->5->7->0关键词： VRPTW 遗传算法 0-1规划法 Lingo目录一、问题重述 (1)二、模型假设和符号说明 (1)三、问题分析 (2)四、模型的建立与求解 (3)4.1问题一的解答 (3)4.1.1模型的准备 (3)4.1.2模型的建立 (3)4.1.3模型的求解 (6)4.2问题二的解答 (7)4.2.1对货运车辆数的估计 (7)4.2.2路线的规划 (7)五、模型的评价与改进 (10)5.1模型的优缺点分析 (10)5.2 模型的改进 (11)六、参考文献 (11)七、附录 (12)一、问题重述某快递公司在某个地区拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/小时）相同，该快递公司用这样的车为若干个客户配送物品，快递公司与客户以及客户与客户之间的公路里程（千米）为已知。

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：西安财经学院参赛队员(打印并签名)：1.李云2.李鑫3.刘莎莎指导教师或指导教师组负责人(打印并签名)：张娟日期：2013年7月8日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：送货路线设计问题摘要本文是有关送货员送货路线优化问题，即在给定送货地点和给定设计规范的条件下，综合考虑最大载重范围、最大带货体积以及各货物送货时限，确定业务员的最佳运行路线策略可以转化为在遍历所有要送达货物节点的前提下，使总路程最小。

并总结出一些在这类图中求解近似最优回路的有效法则.问题一：将1~30号货物送到指定地点并返回，用Floyd算法迭代出任意两点最短路的距离矩阵，并将原来的图构造成完全图，利用floyd算法和用二边逐次修正法求解Hamilton圈，构造最优Hamilton回路，设计出最快完成路线与方式，得出结果。

数学建模运输问题送货问题数学建模论文题目: 送货问题学院(直属系数学与计算机学院年级、专业: 2010级信息与计算科学姓名:杨尚安指导教师: 蒲俊完成时间: 2012年 3 月20 日本文讨论的是货运公司的运输问题，根据各公司需求和运输路线图，建立了线性规划模型和0-1规划模型，对货运公司的出车安排进行了分析和优化，得出运费最小的调度方案。

对于问题一，由于车辆在途中不能掉头，出车成本固定，要使得总成本最小，即要使在一定的车辆数下，既满足各公司的需求，又要尽量减小出车次数。

故以最小出车数为目标函数，建立线性规划模型，并通过lingo求解，得出最小出车数27次。

接着考虑车的方向问题，出车分为顺时针和逆时针，建立0-1模型，并求解，得出满足问题一的调度方案（见附录表1）。

对于问题二，车辆允许掉头，加上车辆装载货物和空装时运输费不同，，要使总成本最小，故可以通过修改原目标函数，建立线性规划模型和0-1规划模型，求解，得出最佳派出车辆3辆并列出满足问题二的调度方案。

对于问题三第一小问，增加了运输车辆的类型。

即装载材料的方法很多，在上述分析的基础上，通过增加约束条件，建立新的线性规划模型，并求解，得出满足问题三的调度方案。

在第二小问中，由于给出部分公司有道路相通，可采用运筹学中的最短路问题的解决方法加以解决。

关键字：线性规划模型0-1规划模型调度一、问题重述某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。

路线是唯一的双向道路(如图１)。

货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。

每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。

运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。