数学建模论文 物资调度问题

1、物资调度问题 摘要 “运输调度”数学模型是通过运输车运输路线的确定以及运输车调配方案的确定来使运输的花费最小。本文首先分析了物资调度中运费、载重量及各站点需求量间相互关系。而后，紧抓住总运营费用最小这个目标，找出最短路径，最后完成了每辆运输车的最优调度具体方案。 问题一：根据题目及实际经验得出运输车运输物资与其载重量及其行驶的路程成正比例关系，又运输的价格一定，再结合题目给出的条件“运输车重载运费2元/吨公里”，其重载运费的单位“元/吨公里”给我们的启发。于是结合题目给定的表，我们将两个决策变量（载重量，路程）化零为整为一个花费因素来考虑，即从经济的角度来考虑。同理我们将多辆车也化零为整，即用

2、一辆“超大运输车”来运输物资。根据这样从经济的角度来考虑，于是我们将需求点的需求量乘入需求点的坐标得到一个新的表，即花费经济表，我们再运用数学软件作出一个新的坐标，这样可以得到一个花费坐Mathematic标。于是按照从经济花费最少的角度，根据我们所掌握的最短路径及算法再结Dijkstra合数学软件，可求得经济花费坐标上的最短路径。具体求法上，采用了Mathematic，先保证每个站点的运营费用最小，从而找出所有站点算法结合“最优化原理”Dijkstra的总运营费用最小，即找出了一条总费用最低的最短路径。用我们的“超大运输车”走这条最小花费的路线，我们发现时间这个因素不能满足且计算结果与实际的

3、经验偏差较大。于是我们重新分配路线，并且同时满足运输车工作时间这个因素的限制，重新对该方案综合考虑，作出了合理的调整.此处我们运用了“化整为零”的思想，将该路线分为八条路径。同时也将超大车进行分解，于是派八辆运输车向29个需求点运送物资。同样的道理我们也将运输车运送物资从经济的角度看，即将运量乘以其速度，又因运输的价格一定，因此便可以将运输车在整体上从经济考虑。于是便可以将整体从经济上来考虑。将运输最小花费转化从经济方面来考虑比较合理。由此可求解出运输车全程的最低费用： 29?cccSSScdL)?0.5(Min?Min?Min? n3总返1去2ijiji?1 结合各约束条件求得最低费用为19

4、80.16元。 问题二：由题目知运输车的载重量不同，但由于我们从整体的经济上来考虑运输物资的花费最少问题，因此花费坐标的最短路径仍然不变。因此结合运输车工作时间的这个因素，我们仍用问题一的思路，运用“化零为整”，“化整为零”的思想来考虑第二问。按照这样的的思路我们制定了八条路线，派了七辆运输车来运送物资。同样在整体上对问题从经济上来考虑比较合理。 29?）+20+34+18+243421275?2T+0.5（+i 1?i?LL）?（+0.5?（2）?TTTTT?527213420341824?302341 辆车71969.66结合各约束条件求得最低费用为元，需要 最优化原理最短路线 关键词：物

5、资调度 规划 0-1算法 Dijkstra 24 / 1 一、问题重述 1.1. 背景资料与条件 某城区有29个物资需求点，需求点的地理坐标和每天物资的需求量见如下表一。（表一为原表截取的一部分，原表其余部分见附录一）。每天凌晨都要从仓库（第30号站点）出发将物资运至每个需求点。现有已知一种运输车，载重 6吨，运输车平均速度为40公里小时，每台车每日工作 4小时，每个需求点需要用10分钟的时间下货。运输车重载运费2元/吨公里，空载费用0.5元/公里；并且街道方向均平行于坐标轴。 29个需求点物资需求量及地理坐标 坐标(km) 坐标(km) T T 需求量站点编号 站点编号 需求量x y x y

6、 2 16 1.50 3 2 1 2.50 16 6 0.80 18 1 5 17 2 1.00 11 1.50 5 3 4 1.50 17 18 15 7 1.20 4 4 12 0.90 19 19 5 9 1.40 0.85 20 0 8 22 1.20 6 11 5 1.30 21 3 下图为29个需求点的地理坐标示意图： 需求点地理坐标252024, 2015, 196, 1820, 1711, 1725, 162, 161515, 147, 1421, 13系列1y15, 1210, 123, 111027, 912, 97, 919, 90, 84, 714, 69, 622,

7、51, 555, 417, 310, 23, 221, 000, 014, 0301505102025x 图一：各需求点地理坐标图 1.2.需要解决的问题 问题一：在运输车的载重固定为6吨的情况下，为使运输费用最小，怎样调动运输车（包括运输车的数量,每台车的运营路线及费用）。 问题二：在运输车的载重分为三类（四吨，六吨，八吨）的情况下，为使运输费用最小，24 / 2 怎样调动运输车（包括运输车的数量,每台车的运营路线及费用）。 二、问题分析 2.1.问题的重要性分析（社会背景） 现代社会经济高速发展，各种信息物资交流频繁，特别是当今，对如何优化物资分配，降低经济成本，时间成本的要求十分迫切。研

8、究在使费用最小情况下的物资调度问题，对于满足各地物资需求，优化资源配置，促进经济社会发展具有十分重要的意义。 2.2. 有关方面在这个问题上做过的研究 2物流配送车辆优化调度问题最早是由学者 Dantzig和 Ramser 于 1959 年首次提出的,国外一般称之为vehicle routing problem或vehicle scheduling problem.一般以为 ,不考虑时间要求 ,仅根据空间位置安排线路时称为车辆线路安排问题VRP ;考虑时间要求 ,安排线路时称为车辆调度问题VSP。目前针对车辆优化调度问题的求解算法可以说是相当丰富,根据对这些算法本质的分类研究 ,基本上可以分为

9、精确算法和启发式算法两大类. 精确算法指可求出最优解的算法 ,主要有分枝定界法、 割平面法、 网络流算法和动态规划法.精确算法的计算量一般随问题规模的增大而呈指数增长 ,所以多用于规模较小的问题。启发式算法是指一种基于直观或经验构造的算法 ,目标是在可接受的花费(计算时间、 占用空间等)下得出待解决问题的满意解 ,而不是最优解.考虑到VRP是强NP难题 ,而启发式方法能够比较快地得到满意解 ,这对解决NP难题来说有着不可估量的作用.因此大部分文献中专家们主要是在构造各种高质量的启发式算法。 2.3.问题的思路分析 仓库物资由运输车进行调运。每辆车的工作时间不超过4小时，并且每辆车的载重不能超过

10、6吨。若调运的需求地点已经明确，为了使运费最小，必须用最少的车在允许的工作时间内把需要运送的物资运送到需求地点，因此选择什么样的调运路线和派遣多少车辆显得尤为重要。本论文试图从最短路程和最小花费的角度，建立起满足调运费用最少且调用车辆最少的数学模型，求出仓库派遣的车辆的数量和运送路线。 问题一的分析： 2.3.1.“化零为整”，求最短路 本题要求在使总运输费用最小的情况下，安排这29个运输点的车辆调度方案。 先考虑运输车运往各个需求地的总运输最小费用。假设从仓库（0,0）点开始，车先运往地，此时运费最小；再运往地，保证从地到地的总运费也是最小的；车再运往jjhii地，保证此时地与地的运费仍是最

11、小；即若每两地之间的运输费用都是最小的，那jh?ij地的最小么将所有联通的两个需求地的运费求和仍是最少的运费。即假设地和为ijddd为0则。若联通，则为1，若两地不连通，与运输费用，为0-1变量，即两地ijijijijs为：在运输车运往个需求点的过程中，总运输最小费用 去29?dS,j?1?29?Min? ij去ij1?i24 / 3 针对地，根据实际情况，其运输费用与该地的需求量及地到地的距离均成正比，故iij,y,x）到各个需求点的最短）将地的需求量和地理位置合成一个新量（，仓库（0,0,i路径即为总运输费用最小的路径。 2.3.2求总最小运输费用 在运输车从各个需求点回到仓库的过程中，由

12、于最短路已经确定，因而返回时按每条运输路线上终止需求点到仓库的最短路径，就可求出整个运输车运送物资与返回全过程的最小费用。 MinSccc )?0.5（n1返2即在运输车往返需求点的全过程中的最小费用为 29?cccdcSSS)?.5?MinMin(?Min?0 n32总返1去ijij1?i2.3.3.化整为零，调度车辆，分配每辆车运输线路 根据本文前部分的求解，能求出从仓库到29个需求点的最短物资调度线路，则调度车辆要考虑的因素是使总运费最小及使用的车辆尽量少。因为在实际物资调度过程中，派出一辆车的固定费用远高于一辆车的行驶费用，因此调度的车辆尽可能少也是优化车辆调度的一个重要考虑因素。本文

13、在此提供两种方案。 V在运到第个吨，假设运输车第一种方案：假设每辆运输车满载，即载重均为6jiV车，则此时运输到地的物资小于地的需求量将运输点时，6吨货全部卸完，jjMmiV车继续往地送货，满足返回，地的需求量后继续前进，按此种运输方式运输往各jjh个需求地的需求量，直至第29个需求点。即在此过程中，假设有一辆“超级大车”，载重了29个需求点的全部物资，每到一个需求点，就 卸下一部分物资，直至最后一个需求点。 V在运送完最短路上指定的几个需第二种方案：假设每辆运输车不一定满载，车iV沿着最短路线，继续运送物资。即在此种方案下，每个需求点后，即空载返回，车h求点只有一辆车来运送物资。 问题二的分

14、析： 在第一问已求出最短路的前提下，第二问中提供了三种载重不同的运输车。即在这种条件下，能够继续优化调度方案，使载重大的车(8吨的车)，运送离仓库较近的需求地的物资，使这几个需求地的物资总和尽量接近于8吨。载重越小的车，运往的需求地离仓库越远。因为大车的运营成本最高。（大车载重多，因而每公里的运输费用最高)。 思路图： 24 / 4 三、基本假设结合本题的实际，为了确保模型求解的准确性和合理性，我们排除了一些位置因素 的干扰，提出以下几点假设： 3.1问题一的假设 1.每辆车载重不同时速度均相等。 2.忽略运输车加速和制动的速度变化及时间的影响。 3.不考虑汽车在红绿灯，堵车，恶劣天气状况时的

15、延误时间。 4.每辆车派出的人工成本，装卸货等固定成本忽略不计。 5.供应物资的公司能够提供足够多的车辆。个j个需求点的需求量及仓库到第6.假设不考虑其他因素，第j个需求点的运费与第j 需求点的位置均成正比。 问题二的假设3.2 1.本题求解最小费用不考虑实际情况中三种载重不同的运输车的固定成本的差异。 2、不考虑三种载重不同的运输车速度的不同。 3.3.本文引用的数据、资料均真实可靠。 四、符号说明（其他未说明的符号在文中第一次出现为了便于问题的求解，我们给出以下符号说明： ）时会做详细的说明。 意义符号v 辆车第ii24 / 5 需求需求和需求之间的距i需求的物资需求需求量乘位置后需求的合

16、成坐变0-i之间的费和需求需求i辆车的总运输费i ?T ：i 地连通时j当i地与0? ：d?注一?ij地不连通时i1地与j当? yyy :xxxX个需求点的横纵坐、注二 ，其中均为题中所给的第ia?iijjiiji 标。 五、模型的建立与求解 5.1.问题一的求解 5.1.1模型一概述3 算法：Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。Dijkstra算法能得出主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 最短路径的最优解。表示其中 (这里描述的是从节点1开始到各点的算法，算法描述：DijkstrabWa?id) 的边的权值，

17、即为最短路径值b?a?i1w?0d?S?n2,3?id?1?i) or + (1,置集合 1 数组之间存在边, i) (1. 之间不存在边无穷大?jsi?,i属于ssdjin?m?d为空集则算法结束，令中，在 2 令，若SS3 否则转?i?dmdi?indi,j?wji，转,，那么对全部 3属于如果存在边i?j-S2 24 / 6 ?算法思想为：分成两组，设是一个带权有向图，把图中顶点集合EVG?,DijkstraV中只有一个源点，以后每求表示，初始时第一组为已求出最短路径的顶点集合（用SS中，算法就结束中，直到全部顶点都加入到 加入到集合得一条最短路径 , 就将SS表示），按最短路径长度的递

18、增了），第二组为其余未确定最短路径的顶点集合（用U中各顶点的中。在加入的过程中，总保持从源点到次序依次把第二组的顶点加入SVS每个顶点对应一中任何顶点的最短路径长度。此外，最短路径长度不大于从源点到UV中的顶点的距离，是中的顶点的距离就是从到此顶点的最短路径长度，个距离，UVS 到此顶点只包括中的顶点为中间顶点的当前最短路径长度。从SV 算法具体步骤 外的其他顶点，。包含除的距离为0 （1）初始时，只包含源点，即UVSVSV 的出边邻接点）。）（若有边）或 不是中顶点距离为边上的权（若与VUVUU到中（该选定的距离就是最小的顶点，把加入 （2）从中选取一个距离VVUSkk 的最短路径长度）。k

19、 （若从源点到顶点为新考虑的中间点，3）以修改中各顶点的距离； （uUUVk的距离）短，则修改顶点）的距离（经过顶点）比原来距离（不经过顶点uUkk 的距离加上边上的权。值，修改后的距离值的顶点k 中。3）直到所有顶点都包含在4）重复步骤（2）和（S作为整个过程的最优策略，它满足相对前面决策所形成的状态而言，余下最优化原理:一个问题满足最优化原理也称其拥有最优子结构性的子策略必然构成“最优子策略”。 质。 5.1.2模型一的运用与求解 1）运用整体思想，最短路思想的由来（要求运输从仓库开出任一辆运输车对物资进行调运，到任意的未配送的需求点。元吨。且运输车重载运费24小时，各运输车的载重量不超过

20、6车的工作时间小于等于公里。为使总费用最小，则应使运输车从每一个需求点运往元/吨公里，空载费用0.5，下一个需求点的费用最少。现先采用“化零为整”的思想，假设有一辆“超级运输车”地的运输费用使运输车从仓库运往29个需求地的所有所需物资之和，即首先，装载了i地的运输费用最小，如此类推，若运输车从每一个需求地运往下地运往最少，再从ij个需求地的运输费用之和就是最少的费29一个需求地的都是费用最少的最优路径，则个需求地的路径即为总费用最少的路径。再采用“化整为零”的29用。即运输车走的思想，使所有运输车均排成一条长队，依次经过最短路径，当第一辆车运完所装载物资后，即空载撤回，第二辆车接着向下一个需求

21、点运送物资，在经过最短路上相应需求点运送完所装载物资后，也空载撤回，如此类推，直至最后一辆运输车运送完全部所需物 。1）资。再次，我们假设运输车行驶的速度与其载重无关（假设 ）由每个需求点的最小费用转化为求最短路（2ppaaaaa的费用最的费用为相连接，且代表与为连向设运往需求点jjiiijijiaa ，再经过“超大运输车”先经过少的需求点。即在最短路径上，。ji?pyaxTX,成正比例关=运输的费用与该点的物资需求量及该点的地理坐标iii,ijii系。对此我们将二者化零为整，将每个需求点的需求量乘以其坐标得到新的坐标。同时也将运输车的载重量乘以它的速度。将二者同时放在花费的角度上（金钱的角度

22、上）进吨。对得行求解。如此我们求了花费上的最短距离，同时我们设所有的运输车都载重6 到的最短行程做解，以得到最小的花费。24 / 7 pppkkTX可表示为： ，由上，设比例系数分别为。则,?iij,21jijiji?pkkXT? ii21jikkTX = ii,21?yxT =,Kiii?yxTT =?Kiiii? =y?xK?a?，的地理坐标与需求量合成为一个新的坐标将需求点即此处，该坐标表示的是y,xia的运输费用坐标。则题目转化为求一条最短路，将所有的29个需求点连接，需求点i使总运输费用最小。我们根据原始数据表（表1），将需求量乘入各个需求点的坐标建立一张新的表2。 表二 各站点花费

23、坐标表 地理坐标（站点编需求量号 T x km） 地理坐标（需求量花费坐标站点编T （km*t） 号 y x 1 2.5 3 2 1 1 2 12.5 16 1.5 2 5 6 17 0.8 6 3 1.5 5 4 13.5 18 1.5 11 4 1.2 4 7 13.2 19 0.9 15 5 0.85 0 8 6.8 20 19 6 1.3 3 11 18.2 21 22 7 1.2 7 0.9 9.48 22 21 8 2.3 9 6 34.5 23 27 9 1.4 10 2 16.8 24 15 10 1.8 14 0 25.2 25 15 11 1.1 17 3 22 26 12

24、 2.7 14 6 54 27 13 1.8 12 9 37.8 28 14 1.8 10 12 15 0.6 7 14 1.4 1.2 1.8 1.4 1.6 1.9 1 2 1 2.1 0 20 21 24 25 0 39.6 29 12.6 30 k花费坐km*y16271819.217421224.3939.2532.4037.8950.41954.41455.11737136820441686.100 我们又用Mathematica作出一张坐标图（程序见附录二）： 24 / 8 图二：各需求点花费坐标图 3）最短路的求法（算法可求得花费位置的最短路径（其中数据表，及Dijkstra根

25、据最小生成树及。流程图如下：Mathematica程序见附录） 图三：花费最短路径算法流程图（最短路上两相邻需求点的具体距离见附最后求得使总费用最少的最短路径示意图如下 录四）：24 / 9 图四：最短路径示意图 ）将合成坐标转化为地理坐标，确定具体调度方案（4这样便为我们找出了运输物资的最短路径,同时求解出了总运营的最低费用.根据上文,?并非为各需求点我们具体分配调度运输车扫清障碍。但问题一中各需求点的坐标yx,?是各需求的地理坐标，而是求最小费用的需求量与地理位置的合成坐标，即坐标yx, 点的费用坐标。因而，根据花费最少的最小路径，首先将合成坐标回归为地理坐标。: 在如何装载的问题上,显然

26、有两种情况根据最短路径经过的吨货物.:情况一若每量车均为满载,即每量发出的车均承载6vv发货到下一个,所装载物资发完,第二辆继续前进各站点依次发货,当第一辆货车21v也即是我们的”超大运输而此时第一辆.便空载撤回,为下一次的运输做好准备站点,14,有几辆车应该重复使用的(只需保证用时不大于.车”假想思路在这里需要提出的是具体的调,派出一辆车的固定费用远高于一辆车的行驶费用. ),小时因为根据实际情况 度方案见如下表一： 表一 运输车满载调配物资情况表8 6 7 2 1 3 4 5 车次30-17-25-26-24-23-3-6-168-20-111-22-14-27-调配路18 7 29-13

27、 28 21-9 线 -5-4-2 0-12 15-19 装载吨1.15 6 6 6 6 6 6 6 数24 / 10 308 262 298 里程数41 86 125 168 218 注：此处里程数仅为各运输车走完各自调配物资线路的里程数，不包括空载返回的里程 数。 具体车辆调配见下图五： 图五：满载车辆调配图 此图例也适用于图六、图七图例：考虑此种方案，目的是简化对车辆的调度。使得可以假想为所有的车辆排成一条长:注VV地的需求到地时恰好运完所有货物，空载返回，车接着补充，满足队，当车jjji 量，以此类推，直至满足完第29个需求地的需求量。比如根据最短,可以非满载), 情况二:若各辆车按具

28、体需求量装载货物(可以满载M而前四个站点需要总物资为吨,如果前3个站点需要总物资为m(m6）三个站点恰好运完货物，此时就可以空载撤回，第二辆也再通过计算下几个站点需要的具体物资去装载具体的物资量，完全发配以此类推，直到最后一个站点运输v 完毕，即最后一辆车恰好运完，空载撤回具体的调度方案见如下表二：n 各辆车非满载调配物资情况表表二车8 7 5 3 1 2 4 6 次24 / 11 调30-17-7-15-19-26-29-24-23-12-11-22-2-8-20-配3-6-16-59-14-18 25 28 27 10 13 路-4 21 线装载5.7 5.6 5.2 4.9 6 5.15

29、 5.5 5.1 吨 数里308 218 37 程262 78 112 147 174 数1352.5 1065.6 601.2 246.8 547 654.2 991 费319.6 用 注：此处里程数仅为各运输车走完各自调配物资线路的里程数，不包括空载返回的里程 数。 :图六非满载车辆调配图由表一和表二的对比，可以看出虽然满载和非满载两种情况下调配车辆辆数一样，但非v当运输车满载情况下总运输费用远小于满载情况下总运输费用。原因是满载情况下，ii小于最小路线上，即使在运完第很小，个需求点，此时运输总量小于6m6m?6?mv必须前往下一个需求点将余下物资卸完，因而会多出行进,但下一个需求点的需求

30、量ixij 与需求点之间的距离），多运送（需求点m?6ij 吨物资所需的耗费。24 / 12 （5）问题一进一步的优化 在前面两种情况中，考虑的均是让所有运输车沿着同一条线路运送物资，即花费最短路。事实上，可以让各运输车按最近路径从仓库到达各调配路线的初始需求点，而不是沿花费最短路，使得开往各初始需求点的费用大大减少。返回时则由各调配路线终止点按最近路径返回仓库，而不是按花费最少路径。 根据上述思路，由题意知：运输车的速度为40公里/小时，最大载重量为6吨， 可得车一次最在可运（40公里/小时）6吨，即对车有最大运量240吨公里/小时。 ?）。数）*我们重新定义每个需求点的需求（该需求点的坐标

31、和为：（需求量yx?TT据见表二（见附录2）。 ?为： 如此我们可求得总需求量T?29?LL， ?TT?TT?T?T?304123i1i?T?=939.08吨公里由表二我们可求得： 对图六非满载车辆调配图作如下运输车辆调配方案： 非满载最优车辆调配图 车1 次调3-6-16-2 2-8-20-3 12-11-224 9-14-5 15-19-26 26-29-7 24-23-8 30-17-7配5-4 路 线5.15 装10 6 -21 5.5 27 5.1 5 4.9 13 5.6 28 5.2 -18 5.7 载吨 数34 里46 54 50 49 73 80 87 程 数对于该方案： 我

32、们派出去八辆车，分别开往3，2，12，9，15，26，24，30这八个站点。 第一条路线有： 车载重为5.15吨，其行程为34km，返回时行驶了11km.，停留了40分钟， 共用时约为2小时； ?T+T+T+T+T（； 花费为：2+0.5）11 6341165第二条路线有： 车载重为6吨，其行程为46km，返回时行驶了14km，停留了40分钟， 共用时约为2.5小时了； 24 / 13 ?）+0.514； 花费为：2（T+T+T+T282010第三条路线有： 车载重为5.5吨，其行程为54km，返回时行驶了27km，停留了40分钟， 共用时约为3小时了； ?）+0.527 花费为：2（T+T+

33、T+T12221121第四条路线有： 车载重为5.1吨，其行程为50km，返回时行驶了34km，停留了30分钟， 共用时约为2.5小时了； ?（234 花费为：）+0.5+TT+T14927第五条路线有： 车载重为4.9吨，其行程为49km，返回时行驶了29km，停留了30分钟， 共用时约为2.5小时了； ?T+T+T（花费为：2+0.529 ）151925第六条路线有： 车载重为5.6吨，其行程为73km，返回时行驶了21km，停留了30分钟， 共用时约为3小时了； ?T+T+T（花费为：221 ）+0.5262913第七条路线有： 车载重为5.2吨，其行程为80km，返回时行驶了44km，

34、停留了30分钟， 共用时约为3.5小时了； ?T+T+T（244 花费为：）+0.5242823第八条路线有： 车载重为5.7吨，其行程为87km，返回时行驶了24km，停留了40分钟， 共用时约为3.5小时了； ?T+T+T+T（花费为：24 2）+0.53018177综上：对第一到第八条路线有总花费P（总）= ?LLLT+T+T+T+T+T+TL（）+0.524 ）+0.52（11+30117476318即 ：花费P（总）= 29?LL（）+0.5T?4429?21?24?T?T?T?T342714?2T+0.511?3021i431i?（11+14+27+34+29+21+44+24）

35、求解得：花费P（总）=1980.16元 5.2.问题二的求解 由问题一的求解已找出使总费用最小的最短路径，因此在问题二中，只需沿着最小路径，具体分配载重量不同的运输车辆。考虑到一辆载重大的运输车每公里的运营费用远大于载重小的运输车，因为在每吨物资每公里均为2元的情况下，载重越多，运营公24 / 14 里数越多，所需总费用也越多，因此，在分配时，首先应考虑尽量分配大的运输车，先让载重大的运输车前往距离近的运输点。再让载重小一些的运输车前往距离远的运输点，此种情况下使运输费用得到优化。具体分配载重不同的车辆时，原则是尽量用一辆运输车运送最短路上相邻的需求点需求物资。即使最短路上需求点的需求量之和先

36、满足八吨的运输车，再满足六吨的运输车，最后满足四吨的运输车。离仓库越近的需求点，使用的的运输车载重越大。 具体分配情况如表三所示: 表三 三种载重不同车辆物资调度表 7 6 4 5 1 2 3 车次 4吨4吨车型吨8吨的 8吨的 6吨的 6吨的 6吨的 6吨的 的 的 数调配路8-20-10-12-11- 27-15- 26-29- 24-23- 30-17 3-6-16-5-4-2 7-18 21-9-14 28 19-25 线13 22 装载吨7.65 7.6 5.5 5.9 5.6 5.2 3.6 2.1 数10 41 73 80 71 54 76 87 里程数 车车调配路装载吨里程 4

37、251663吨81 417.65 24 / 15 对于该方案： 7这七个站点。24，30，8，21，27，26，3我们派出去七辆车，分别开往， 8吨的车第一条路线有： 60分钟，41km，返回时行驶了5km.，停留了车载重为7.65吨，其行程为 2小时；共用时约为?+TT+T+T+T+T（花费为：2）+0.55 63216451 吨的车8第二条路线有： 分钟，27km.，停留了60车载重为7.6吨，其行程为80km，返回时行驶了 小时；共用时约为3.5?+T+T+T+TT+T（）+0.527 花费为：220221112108 吨的车 6第三条路线有： 分钟，停留了30吨，其行程为54km，返回

38、时行驶了21km.5.5车载重为 小时；共用时约为2.5?T+T+T（2+0.521 花费为：）21914 6吨的车第四条路线有： 40分钟，返回时行驶了34km.，停留了车载重为5.9吨，其行程为76km 3.7小时；共用时约为?T+T+T+T（34 花费为：2）+0.527152519 吨的车 6第五条路线有： 分钟，停留了30吨，其行程为73km，返回时行驶了20km.车载重为5.6 2.6小时；共用时约为?T+T+T（花费为：20 2)+0.5262913 吨的车第六条路线有： 6 30分钟，停留了5.2吨，其行程为87km，返回时行驶了34km.车载重为 2.6小时；共用时约为?T+

39、T+T（2+0.5）34 花费为：242328 吨的车4第七条路线有： 24 / 16 车载重为3.6吨，其行程为71km，返回时行驶了18km.，停留了20分钟， 共用时约为2.5小时； ?T+T（花费为：2）+0.518 3017第八条路线有： 4吨的车（路线七的车） 车载重为3.6吨，其行程为10km，返回时行驶了24km.，停留了20分钟， 共用时约为1.3小时； ?+TTT+T（24 花费为：2）+0.5187187综上：对第一到第八条路线有： ?LLL+T+LT+TT+T（总）=2（+0.55+）费）+0.524 总花P2316718即 ：花费P（总）= 29?）+20+34+18

40、+242127+?+T34+0.5?（5+2i 1?i?LL?T+0.5?（5?27?21?34?20?34?18?24）（）?2?T?T?T?T303214此时求解得：花费P（总）=1969.66元 六、模型结果的分析和检验 1.1. 在研究物资调配问题时，我们忽略了交通，天气等客观因素，大大简化了最短路径的建立与求解。 1.2. 最初我们便通过“化零为整”思想确立了一条“经济”上最短路径，并在下文求解最低费用以及运输车的具体调配中深刻落实。这样便最大程度上保证总运输费用最低这一主旨，应该说在落实“最低费用”方面是相当可靠的，也是可行的。并且最终我们利用此方法求解出的低费用，也证明了这一点。

41、但是这个模型也并非最优的，因为此模型没有充分考虑时间这个约束条件。换言之，如果以“最低费用”为主要要求，我们的模型有很高的可行性；如果以“时间”为主要要求，此模型可能会产生较大误差。但是，这个误差并非无法弥补的，我们又可以通过“人工改进调配”，灵活的运用此模型。 1.3. 在第一问中，我们最终选择八辆车非满载的调配方案，并求解出了相对最低的运 输费用。因为在问题中我们已经给出了每辆车要经过的具体路线以及需要的承载 量，于是便可以按着具体的运输方案进行检验，经过多次求解调配，发现每次的 误差并不大，这便一定程度说明此模型的稳定性与可行性；而在第二问中，我们通过同样的方法，结合利用软件，计算检验。

42、 mathematic1.4 .仓库每天要运送的物资在早上出发时间之前已经全到了，没有到的当天就不运送这种模型现在已经很成熟，因此采用这种解法应该能够达到减少运费的要求。且总费用控制在了一个较为合理的范围内。但是由于物资调运是一个比较复杂的问题设计到众多的变量，上述模型尚有许多因素没有考虑在内。比如每辆车送完物资，回来再准备第二趟运送这个过程也要花时间，这个时间没有考虑到时间范围内，还有像城市交通不平衡等问题，货物分类等问题。 七、模型的推广 目前 ,物流配送车辆优化调度在国外已广泛运用于生产和生活的各个方面 ,如报纸、 牛奶投递及线路优化 ,工业原材料和成品的运输 ,电话或网络购物的车辆配装

43、及线路设计 ,航运公司轮船经过港口和货物装卸的优化设计 ,连锁商店的送配货等等 ,24 / 17 并已经取得了极大的经济效益.如美国沃尔玛特百货有限公司 ,其成为全球零售业霸主的首要因素是拥有了最先进的物流配送指挥系统 ,全球各门店通过卫星实现联网 ,可以最大限度地降低其商品物流成本和增加销售量 ,从而在竞争中始终处于优势地位56 在我国 ,随着国民经济健康稳定的高速发展 ,市场经济日益发达 ,各种生产经营方式发展得十分迅速.在生产活动中 ,提出了以零库存为目标的Just2in2time 模式;而各式连锁经营的便利店和直送业务的蓬勃发展 , 也使零售业物流配送呈现出多频度、 小批次的特点 ,这

44、些都对以运输为中心的物流配送活动提出了更高的要求.但就目前情况而言 ,我国的VRP研究仍然有限 ,可以说仍未能满足经济发展的需要.首先是起步较晚 ,通用理论研究较少;其次 ,对于具体问题提出的应用研究相对较多 ,但多为对具体算法 .局限性较强 ,且限于各自的适用条件 ,的部分改进八、模型的评价与优化 9.1模型的优缺点分析 9.1.1模型的优点 1、花费最小路的思想。将总费用最小分解为任意两个需求点间费用最小，即若每一需求点到下一需求点的花费最小，则总花费最小。从而由通过计算每两个需求点间费用最小而得到总费用最小。避免了通过穷举法搜索。 2、各需求点经济坐标的合成。将各需求点费用的两个影响因素

45、地理位置与需求量合成一个新的坐标，从而减少了变量的个数，大大简化问题，至此使每个需求点费用直接与总费用相联系。 3、统一所有量的单位。对最小路上个边权的意义的深化。在将各需求点的坐标单位合成为吨千米后，将运输车载重6吨及速度为40千米/小时合成为240吨千米/小时，计算时按不是按地理意义上的最短路而是按花费意义上的最短路，对问题的抽象与简化。 4、在研究物资调配问题时，我们忽略了交通，天气等客观因素，大大简化了最短路径的建立与求解。 5、作图表示出最短路具体路径，直观清晰。 6、在最短路的总体思想下，综合考虑时间与运费等客观约束条件，使模型更贴近实际，同时使运输车的调配更加合理清晰。 9.1.

46、2模型的缺点 1、在第一问中要派出八辆车，在第二问中也要派出七辆车，派出的车辆过多，而实际上，新派出一辆车的成本远高于一辆车往返运输的成本。且在本题求解的两问中，各辆车总的运输时间离每天四小时的工作限制还有较大的余地，因此应考虑进一步优化调运方案，减少派出车辆的辆数。 2、虽然我们运用具体模型求解时，完全根据题中所给出的约束条件，但是交通状况，车速变化等客观因素仍然对模型的紧缺度有较大影响。 3、我们虽然通过“化零为整”，“人工优化”等措施最大程度上保证了运输车的最优调配，但是仍然不排除个别站点间最短距离与花费存在误差。 9.1.3模型的优化 由于我们运输车的工作时间没有充分利用，且没有充分考

47、虑实际情况。对劳动力有较大的浪费。因此我们可以假设在行车时有平均耽搁时间为Td，以及平均损耗为n元/小时辆，工人的工资q元/小时，每辆车过收费站的平均花费为w元/小时对于运送较近的运输车，在影响工作时间不大的情况下可以运输两趟。因此在花费还应加入这些花费。24 / 18 然后综合考虑，得出符合实际的最优解； 优化模型求解： 设时间为t； ? ）则：花费P=（n+q+w）t+ +0.511+ 2（ +（+0.524 ）+T+T+TL+T+TT+T?47183063171同样的道理对于第二问我们有： ? ）+0.524 则：花费P=（n+q+w）t+2（ ）+0.55+ +（+T+T+TLT+T?

48、2316718这样我们便可求出真实的解。 24 / 19 参考文献 1冯小杰，黄力伟，王力勤，尹成义，数学建模原理与案例：P120-P137，北京：科学出版社，2007 2杨弋,顾幸生,物流配送车辆优化调度的综述，东南大学学报 (自然科学 版):P105-P111,2003 3百度百科，Dijkstra算法，http:/ 附件 1. 附件一 附表一29个需求点物资需求量及地理坐标 站点编号 需求量T 坐标(km) x y 站点编号 T 需求量坐标x (km) 1.20 7 8 2.30 9 1.40 1.80 10 7 9 10 14 9 6 2 0 22 23 24 25 1.80 1.40

49、 1.60 1.90 21 27 15 15 11 1.10 12 2.70 13 1.80 14 1.80 17 14 12 10 3 6 9 12 26 27 28 29 1.00 2.00 1.00 2.10 20 21 24 25 15 0.60 7 14 30 0.00 0 y091914171320160 2. 附件二 用mathematic表示的29个需求点地理位置的作图程序： a=ImportD:/data1.xls1; Axis?Red,FillingListPlota,PlotStyle3附件三 aaaa确由）点到点的确定。此后由确定，00求解最短路以下为用mathemat

50、ica（，2121a及以后的费用最小的需求点的方法与此相同。此处不再重复。定 324 / 20 Clearx,y,i,c; x=ImportD:/data2.xls1,1; y=ImportD:/data2.xls1,2; p=; 30,i+, Fori=1,ic=Absx2-xi+Absy2-yi; d=AppendTop,c; e=Mind; Printd,e ExportD:/data3.xls,d Red,FillingListPlota,PlotStyleAxis :最短路的确定及最短路上任意两点间的距离4附件四5 4 6 1 2 3 13.2 6 13.5 6.8 1 0 12.5

51、 6.1 9.3 2 12.5 0 6.5 1 7.2 7.5 2.8 6 6.5 0 3 5.1 7.5 0 8.3 4 13.5 1 0 7.2 5 13.2 6.1 5.1 6.4 6.4 0 9.3 2.8 8.3 6 6.8 6.8 11.4 18.2 7 12.9 12.2 11.9 6 12.4 5.7 19.2 6.7 13.2 8 21.3 21 27.7 9 34.5 22 28.5 14.8 10 16.8 18 8.7 15.2 9.7 28.8 23.7 32 11 25.2 22.7 29.2 19 13.9 12.9 19.4 22.2 12 22 40.8 48

52、 13 54 41.5 40.5 47.2 24.6 24.3 31 25.3 14 37.8 31.8 26.4 32.8 27.1 33.6 26.1 39.6 15 0.6 5.7 16 12.6 6.7 6.6 5.8 17.4 20.2 21 17 27 23.5 22.5 6 12.4 11.1 12.1 18 19.2 13.2 28.8 28.5 35.2 42 19 29.5 36 11.1 17.5 10.8 11.8 20 24.3 18.3 26 32.4 33.2 21 39.2 26.7 25.7 24 18.9 19.9 22 32.4 26.4 27.2 41.

53、4 35.3 44.6 41.8 36.3 37.8 23 37.2 24 50.4 43.6 36.9 37.9 44.4 41.2 54.4 25 41.9 40.9 47.6 48.4 41.9 49.1 42.6 26 55.1 48.3 41.6 23.8 31 37 27 24.5 23.5 30.2 54.8 55.5 68 28 62 61.2 54.5 30.8 38 31.5 30.5 37.2 44 29 79.3 80.1 73.6 86.1 30 72.9 72.6 24 / 21 1 7 8 9 10 11 12 22 34.5 25.2 16.8 19.2 2 1

54、8.2 12.9 6.7 22 8.7 22.7 3 12.9 19.4 13.2 28.5 15.2 4 12.2 29.2 13.9 23.7 5.7 5 11.9 21 9.7 19 14.8 6 6 6.8 21.3 28.8 22.2 32 12.4 7 11.4 27.7 18 25.8 17.3 8 0 8 21.6 35.6 17.8 8 13.6 0 15.3 27.6 9 12.5 10 17.3 18.3 15.3 0 17.7 5.2 0 13.6 17.7 14 11 21.6 9.8 18.3 27.6 12 35.6 14 0 0 17.8 12.5 13 25.8 9.8 5.2 32 35.8 19.5 37.2 28.8 34.8 14 15.8 15 19.6 18.6 3.3 21 19.8 19 22.8 28.8 16 21.4 10.5 20.4 19.6 15.4 17 6.2 21.9 6.6 29.4 10.4 22.8 30.8 13.5 15.6