数学建模论文-物资调度问题
物资调度问题
摘要
“运输调度”数学模型是通过运输车运输路线的确定以及运输车调配方案的确定来使运输的花费最小。本文首先分析了物资调度中运费、载重量及各站点需求量间相互关系。而后，紧抓住总运营费用最小这个目标，找出最短路径，最后完成了每辆运输车的最优调度具体方案。
问题一：根据题目及实际经验得出运输车运输物资与其载重量及其行驶的路程成正比例关系，又运输的价格一定，再结合题目给出的条件“运输车重载运费2元/吨公里”，其重载运费的单位“元/吨公里”给我们的启发。于是结合题目给定的表，我们将两个决策变量（载重量，路程）化零为整为一个花费因素来考虑，即从经济的角度来考虑。同理我们将多辆车也化零为整，即用一辆“超大运输车”来运输物资。根据这样从经济的角度来考虑，于是我们将需求点的需求量乘入需求点的坐标得到一个新的表，即花费经济表，我们再运用数学软件Mathematic 作出一个新的坐标，这样可以得到一个花费坐标。于是按照从经济花费最少的角度，根据我们所掌握的最短路径及Dijkstra 算法再结合数学软件Mathematic ，可求得经济花费坐标上的最短路径。具体求法上，采用了
，先保证每个站点的运营费用最小，从而找出所有站点Dijkstra 算法结合“最优化原理”
的总运营费用最小，即找出了一条总费用最低的最短路径。用我们的“超大运输车”走这条最小花费的路线，我们发现时间这个因素不能满足且计算结果与实际的经验偏差较大。于是我们重新分配路线，并且同时满足运输车工作时间这个因素的限制，重新对该方案综合考虑，作出了合理的调整. 此处我们运用了“化整为零”的思想，将该路线分为八条路径。同时也将超大车进行分解，于是派八辆运输车向29个需求点运送物资。同样的道理我们也将运输车运送物资从经济的角度看，即将运量乘以其速度，又因运输的价格一定，因此便可以将运输车在整体上从经济考虑。于是便可以将整体从经济上来考虑。将运输最小花费转化从经济方面来考虑比较合理。由此可求解出运输车全程的最低费用：
29
Min S 总=Min S 去+Min S 返=∑d ij ⨯+0.5⨯(c 1+c 2+c 3++c n ) ij
i =1
结合各约束条件求得最低费用为1980.16元。
问题二：由题目知运输车的载重量不同，但由于我们从整体的经济上来考虑运输物资的花费最少问题，因此花费坐标的最短路径仍然不变。因此结合运输车工作时间的这个因素，我们仍用问题一的思路，运用“化零为整”，“化整为零”的思想来考虑第二问。按照这样的的思路我们制定了八条路线，派了七辆运输车来运送物资。同样在整体上对问题从经济上来考虑比较合理。
μ
'）=2⨯（T 1'+T 2'+T 3'+T 4'++T 30+0.5⨯（5+27+21+34+20+34+18+24）
结合各约束条件求得最低费用为1969.66元，需要7辆车
关键词：物资调度 最短路线 最优化原理 Dijkstra算法 0-1规划
i =1
2⨯∑T i '+0.5⨯（5+27+21+34+20+34+18+24）
29
一、问题重述
1.1. 背景资料与条件
某城区有29个物资需求点，需求点的地理坐标和每天物资的需求量见如下表一。（表一为原表截取的一部分，原表其余部分见附录一）。每天凌晨都要从仓库（第30号站点）出发将物资运至每个需求点。现有已知一种运输车，载重 6吨，运输车平均速度为40公里／小时，每台车每日工作 4小时，每个需求点需要用10分钟的时间下货。运输车重载运费2元/吨公里，空载费用0.5元/公里；并且街道方向均平行于坐标轴。
下图为29个需求点的地理坐标示意图：
图一：各需求点地理坐标图
1.2. 需要解决的问题 问题一：在运输车的载重固定为6吨的情况下，为使运输费用最小，怎样调动运输车（包括运输车的数量, 每台车的运营路线及费用）。
问题二：在运输车的载重分为三类（四吨，六吨，八吨）的情况下，为使运输费用最小，
怎样调动运输车（包括运输车的数量, 每台车的运营路线及费用）。
二、问题分析
2.1. 问题的重要性分析（社会背景）
现代社会经济高速发展，各种信息物资交流频繁，特别是当今，对如何优化物资分配，降低经济成本，时间成本的要求十分迫切。研究在使费用最小情况下的物资调度问题，对于满足各地物资需求，优化资源配置，促进经济社会发展具有十分重要的意义。 2.2. 有关方面在这个问题上做过的研究
[2]
物流配送车辆优化调度问题最早是由学者 Dantzig和 Ramser 于 1959 年首次提出的, 国外一般称之为vehicle routing problem或vehicle scheduling problem.一般以为 ,不考虑时间要求 ,仅根据空间位置安排线路时称为车辆线路安排问题VRP ;考虑时间要求 ,安排线路时称为车辆调度问题VSP 。目前针对车辆优化调度问题的求解算法可以说是相当丰富, 根据对这些算法本质的分类研究 ,基本上可以分为精确算法和启发式算法两大类. 精确算法指可求出最优解的算法 ,主要有分枝定界法、 割平面法、 网络流算法和动态规划法. 精确算法的计算量一般随问题规模的增大而呈指数增长 ,所以多用于规模较小的问题。启发式算法是指一种基于直观或经验构造的算法 ,目标是在可接受的花费(计算时间、 占用空间等) 下得出待解决问题的满意解 ,而不是最优解. 考虑到VRP 是强NP 难题 ,而启发式方法能够比较快地得到满意解 ,这对解决NP 难题来说有着不可估量的作用. 因此大部分文献中专家们主要是在构造各种高质量的启发式算法。
2.3. 问题的思路分析
仓库物资由运输车进行调运。每辆车的工作时间不超过4小时，并且每辆车的载重不能超过6吨。若调运的需求地点已经明确，为了使运费最小，必须用最少的车在允许的工作时间内把需要运送的物资运送到需求地点，因此选择什么样的调运路线和派遣多少车辆显得尤为重要。本论文试图从最短路程和最小花费的角度，建立起满足调运费用最少且调用车辆最少的数学模型，求出仓库派遣的车辆的数量和运送路线。 问题一的分析：
2.3.1. “化零为整”，求最短路
本题要求在使总运输费用最小的情况下，安排这29个运输点的车辆调度方案。 先考虑运输车运往各个需求地的总运输最小费用。假设从仓库（0,0）点开始，车先运往i 地，此时运费最小；再运往j 地，保证从i 地到j 地的总运费也是最小的；车再运往h 地，保证此时地j 与h 地的运费仍是最小；即若每两地之间的运输费用都是最小的，那么将所有联通的两个需求地的运费求和仍是最少的运费。即假设μ为j 地和i 地的最小
ij
运输费用，d ij 为0-1变量，即两地j 与i 若联通，则d ij 为1，若两地不连通，则d ij 为0。在运输车运往个需求点的过程中，总运输最小费用s 去为：
Min S 去=∑
i =129
d ⨯μ
ij
ij
, j =1 29
针对i 地，根据实际情况，其运输费用与该地的需求量及j 地到i 地的距离均成正比，故将i 地的需求量和地理位置合成一个新量（x , y ），仓库（0,0）到各个需求点的最短
,
,
路径即为总运输费用最小的路径。 2.3.2求总最小运输费用
在运输车从各个需求点回到仓库的过程中，由于最短路已经确定，因而返回时按每条运输路线上终止需求点到仓库的最短路径，就可求出整个运输车运送物资与返回全过程的最小费用。
Min S
M i n
返
=0.5⨯（c 1+c 2+ +c n )
即在运输车往返需求点的全过程中的最小费用为
S
总
=M i n S 去+M i n S 返=∑
i =1
29
d ⨯μ
ij
ij
+0. 5⨯(c 1+c 2+c 3+ +c n )
2.3.3. 化整为零，调度车辆，分配每辆车运输线路
根据本文前部分的求解，能求出从仓库到29个需求点的最短物资调度线路，则调度车辆要考虑的因素是使总运费最小及使用的车辆尽量少。因为在实际物资调度过程中，派出一辆车的固定费用远高于一辆车的行驶费用，因此调度的车辆尽可能少也是优化车辆调度的一个重要考虑因素。本文在此提供两种方案。
第一种方案：假设每辆运输车满载，即载重均为6吨，假设运输车V i 在运到第j 个运输点时，将6吨货全部卸完，此时运输到j 地的物资m 小于j 地的需求量M ，则V i 车返回，V h 车继续往j 地送货，满足j 地的需求量后继续前进，按此种运输方式运输往各个需求地的需求量，直至第29个需求点。即在此过程中，假设有一辆“超级大车”，载重了29个需求点的全部物资，每到一个需求点，就
卸下一部分物资，直至最后一个需求点。
第二种方案：假设每辆运输车不一定满载，车V i 在运送完最短路上指定的几个需求点后，即空载返回，车V h 沿着最短路线，继续运送物资。即在此种方案下，每个需求点只有一辆车来运送物资。 问题二的分析：
在第一问已求出最短路的前提下，第二问中提供了三种载重不同的运输车。即在这种条件下，能够继续优化调度方案，使载重大的车(8吨的车) ，运送离仓库较近的需求地的物资，使这几个需求地的物资总和尽量接近于8吨。载重越小的车，运往的需求地离仓库越远。因为大车的运营成本最高。（大车载重多，因而每公里的运输费用最高) 。 思路图：
三、基本假设
结合本题的实际，为了确保模型求解的准确性和合理性，我们排除了一些位置因素的干扰，提出以下几点假设： 3.1．问题一的假设
1. 每辆车载重不同时速度均相等。
2. 忽略运输车加速和制动的速度变化及时间的影响。
3. 不考虑汽车在红绿灯，堵车，恶劣天气状况时的延误时间。 4. 每辆车派出的人工成本，装卸货等固定成本忽略不计。 5. 供应物资的公司能够提供足够多的车辆。 6. 假设不考虑其他因素，第j 个需求点的运费与第j 个需求点的需求量及仓库到第j 个需求点的位置均成正比。 3.2．问题二的假设
1. 本题求解最小费用不考虑实际情况中三种载重不同的运输车的固定成本的差异。 2、不考虑三种载重不同的运输车速度的不同。 3.3. 本文引用的数据、资料均真实可靠。
四、符号说明
为了便于问题的求解，我们给出以下符号说明：（其他未说明的符号在文中第一次出现
T '：
i
⎧0
注一：d ij =⎨
⎩1注二: X ij =标。
i
当i 地与j 地连通时当i 地与j 地不连通时
j
x -x
+
y -y
i
j
a ，其中x i 、y i 均为题中所给的第i 个需求点的横纵坐
五、模型的建立与求解
5.1. 问题一的求解 5.1.1模型一概述
Dijkstra 算法：
Dijkstra 算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法能得出最短路径的最优解。
算法描述：(这里描述的是从节点1开始到各点的Dijkstra 算法，其中Wa ->b 表示a ->b 的边的权值，d (i )即为最短路径值)
1． 置集合S ={2, 3 n }数组d (1)=0, d (i )=w 1->i (1,i 之间存在边) or +无穷大(1. i 之间不存在边)
2． 在S 中，令d (j )=min {d (i ), i 属于s }，令s =s -{j }，若S 为空集则算法结束，否则转3
3． 对全部i 属于S , 如果存在边j->i ，那么d (i )=min {d (i ), d (j )+wj ->i }，转
2
[3]
设G =(V, E )是一个带权有向图，把图中顶点集合V 分成两组，Dijkstra 算法思想为：
第一组为已求出最短路径的顶点集合（用S 表示，初始时S 中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S 中，直到全部顶点都加入到S 中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点加入S 中。在加入的过程中，总保持从源点V 到S 中各顶点的最短路径长度不大于从源点V 到U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S 中的顶点的距离就是从V 到此顶点的最短路径长度，U 中的顶点的距离，是从V 到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。 算法具体步骤
（1）初始时，S 只包含源点，即S ＝V 的距离为0。V 包含除V 外的其他顶点，U 中顶点U 距离为边上的权（若V 与U 有边）或 ）（若U 不是V 的出边邻接点）。 （2）从U 中选取一个距离V 最小的顶点k ，把k 加入S 中（该选定的距离就是V 到k 的最短路径长度）。 （3）以k 为新考虑的中间点，修改U 中各顶点的距离；若从源点V 到顶点U （u U ）的距离（经过顶点k ）比原来距离（不经过顶点k ）短，则修改顶点u 的距离值，修改后的距离值的顶点k 的距离加上边上的权。
（4）重复步骤（2）和（3）直到所有顶点都包含在S 中。
最优化原理:作为整个过程的最优策略，它满足相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。一个问题满足最优化原理也称其拥有最优子结构性质。
5.1.2．模型一的运用与求解
（1）运用整体思想，最短路思想的由来
从仓库开出任一辆运输车对物资进行调运，到任意的未配送的需求点。要求运输
车的工作时间小于等于4小时，各运输车的载重量不超过6吨。且运输车重载运费2元/吨公里，空载费用0.5元/公里。为使总费用最小，则应使运输车从每一个需求点运往下一个需求点的费用最少。现先采用“化零为整”的思想，假设有一辆“超级运输车”，装载了29个需求地的所有所需物资之和，即首先，使运输车从仓库运往i 地的运输费用最少，再从i 地运往j 地的运输费用最小，如此类推，若运输车从每一个需求地运往下一个需求地的都是费用最少的最优路径，则29个需求地的运输费用之和就是最少的费用。即运输车走的29个需求地的路径即为总费用最少的路径。再采用“化整为零”的思想，使所有运输车均排成一条长队，依次经过最短路径，当第一辆车运完所装载物资后，即空载撤回，第二辆车接着向下一个需求点运送物资，在经过最短路上相应需求点运送完所装载物资后，也空载撤回，如此类推，直至最后一辆运输车运送完全部所需物资。再次，我们假设运输车行驶的速度与其载重无关（假设1）。 （2）由每个需求点的最小费用转化为求最短路
设运往需求点a i 的费用为p ，p 代表a j 与a i 相连接，且a j 为连向a i 的费用最
ji
ji
少的需求点。即在最短路径上，“超大运输车”先经过a j ，再经过a i 。 运输a i 的费用
p
ji
与该点的物资需求量T i 及该点的地理坐标X , i =
(x , y )成正比例关
i
i
系。对此我们将二者化零为整，将每个需求点的需求量乘以其坐标得到新的坐标。同时也将运输车的载重量乘以它的速度。将二者同时放在花费的角度上（金钱的角度上）进行求解。如此我们求了花费上的最短距离，同时我们设所有的运输车都载重6吨。对得到的最短行程做解，以得到最小的花费。
由上，
p
ji
∞T i ，
p
ji
∞X j, i ，设比例系数分别为k 1, k 2。则
p
p
ji
=(k 1T i )⨯(k 2X i )
i
ji
可表示为：
= k 1k 2
i
T X
=K T (x , y ) =K (T x +T y )
, i
i
i
i
i
i
=K (x '+y ')
i
即此处，将需求点a i 的地理坐标与需求量合成为一个新的坐标(x ', y ')，该坐标表示的是需求点a i 的运输费用坐标。则题目转化为求一条最短路，将所有的29个需求点连接，使总运输费用最小。我们根据原始数据表（表1），将需求量乘入各个需求点的坐标建立一张新的表2。
图二：各需求点花费坐标图
（3）最短路的求法
根据最小生成树及Dijkstra 算法可求得花费位置的最短路径（其中数据表，及Mathematica 程序见附录）。流程图如下：
图三：花费最短路径算法流程图
最后求得使总费用最少的最短路径示意图如下（最短路上两相邻需求点的具体距离见附录四）：
图四：最短路径示意图
（4）将合成坐标转化为地理坐标，确定具体调度方案
根据上文, 我们找出了运输物资的最短路径, 同时求解出了总运营的最低费用. 这样便为我们具体分配调度运输车扫清障碍。但问题一中各需求点的坐标(x ', y ')并非为各需求点的地理坐标，而是求最小费用的需求量与地理位置的合成坐标，即坐标(x ', y ')是各需求点的费用坐标。因而，根据花费最少的最小路径，首先将合成坐标回归为地理坐标。 在如何装载的问题上, 显然有两种情况:
情况一:若每量车均为满载, 即每量发出的车均承载6吨货物. 根据最短路径经过的各站点依次发货, 当第一辆货车v 1所装载物资发完, 第二辆v 2继续前进, 发货到下一个站点, 而此时第一辆v 1便空载撤回, 为下一次的运输做好准备. 也即是我们的”超大运输车”假想思路. 在这里需要提出的是, 有几辆车应该重复使用的(只需保证用时不大于4小时), 因为根据实际情况, 派出一辆车的固定费用远高于一辆车的行驶费用. 具体的调度方案见如下表一：
数。
具体车辆调配见下图五：
图五：满载车辆调配图
图例：
此图例也适用于图六、图七
注:考虑此种方案，目的是简化对车辆的调度。使得可以假想为所有的车辆排成一条长队，当车V i 到j 地时恰好运完所有货物，空载返回，车V j 接着补充，满足j 地的需求量，以此类推，直至满足完第29个需求地的需求量。
情况二:若各辆车按具体需求量装载货物(可以满载, 可以非满载), 比如根据最短路径的连接站点, 如果前3个站点需要总物资为m 吨(m6）, 这样的情况我们可以把第一辆车装载m 吨物资, 那么第一辆车Ｖ１运货到第三个站点恰好运完货物，此时Ｖ１就可以空载撤回，第二辆Ｖ２也再通过计算下几个站点需要的具体物资去装载具体的物资量，完全发配．以此类推，直到最后一个站点运输完毕，即最后一辆车v n 恰好运完，空载撤回．具体的调度方案见如下表二：
注：此处里程数仅为各运输车走完各自调配物资线路的里程数，不包括空载返回的里程数。
图六:非满载车辆调配图
由表一和表二的对比，可以看出虽然满载和非满载两种情况下调配车辆辆数一样，但非满载情况下总运输费用远小于满载情况下总运输费用。原因是满载情况下，当运输车v i 在运完第i 个需求点，此时运输总量m 小于6，即使6-m 很小，6-m 小于最小路线上下一个需求点的需求量, 但v i 必须前往下一个需求点将余下物资卸完，因而会多出行进
x
ij
（需求点i 与需求点j 之间的距离），多运送6-m
吨物资所需的耗费。
（5）问题一进一步的优化
在前面两种情况中，考虑的均是让所有运输车沿着同一条线路运送物资，即花费最短路。事实上，可以让各运输车按最近路径从仓库到达各调配路线的初始需求点，而不是沿花费最短路，使得开往各初始需求点的费用大大减少。返回时则由各调配路线终止点按最近路径返回仓库，而不是按花费最少路径。
根据上述思路，由题意知：运输车的速度为40公里/小时，最大载重量为6吨， 可得车一次最在可运（40公里/小时）×6吨，即对车有最大运量240吨公里/小时。 我们重新定义每个需求点的需求T '为：（需求量T ）*（该需求点的坐标和(x +y )）。数据见表二（见附录2）。
如此我们可求得总需求量∑T '为：
∑T '=T '+T '+T '+T '+
i
1
2
3
4
i =1
29
'， +T 30
由表二我们可求得：∑T '=939.08吨公里
对图六非满载车辆调配图作如下运输车辆调配方案：
我们派出去八辆车，分别开往3，2，12，9，15，26，24，30这八个站点。 第一条路线有：
车载重为5.15吨，其行程为34km ，返回时行驶了11km. ，停留了40分钟， 共用时约为2小时；
'6'+T16'+T5'+T4'）+0.5×11 ； 花费为：2×（T 31+T
第二条路线有：
车载重为6吨，其行程为46km ，返回时行驶了14km ，停留了40分钟， 共用时约为2.5小时了；
'+T8'+T20'+T10'）+0.5×14； 花费为：2×（T 2
第三条路线有：
车载重为5.5吨，其行程为54km ，返回时行驶了27km ，停留了40分钟， 共用时约为3小时了；
'+T11'+T22'+T21'）+0.52×7 花费为：2×（T 12
第四条路线有：
车载重为5.1吨，其行程为50km ，返回时行驶了34km ，停留了30分钟， 共用时约为2.5小时了；
'+T14'+T27'）+0.5×34 花费为：2×（T 9
第五条路线有：
车载重为4.9吨，其行程为49km ，返回时行驶了29km ，停留了30分钟， 共用时约为2.5小时了；
'+T19'+T25'）+0.5×29 花费为：2×（T 15
第六条路线有：
车载重为5.6吨，其行程为73km ，返回时行驶了21km ，停留了30分钟， 共用时约为3小时了；
'+T29'+T13'）+0.5×21 花费为：2×（T 26
第七条路线有：
车载重为5.2吨，其行程为80km ，返回时行驶了44km ，停留了30分钟， 共用时约为3.5小时了；
'+T23'+T28'）+0.5×44 花费为：2×（T 24
第八条路线有：
车载重为5.7吨，其行程为87km ，返回时行驶了24km ，停留了40分钟， 共用时约为3.5小时了；
'+T17'+T7'+T18'）+0.5×24 花费为：2×（T 30
综上：对第一到第八条路线有总花费P （总）= '''）+0.5×11+'+T17'+T7'+T18'）+0.5×24 2×（T 3+（T 30+T41+T6+即 ：花费P （总）=
2⨯∑T i '+0.5⨯（11+14+27+34+29+21+44+24）=T 1'+T 2'+T 3'+T 4'+
i =1
29
'+T 30
+0.5×
（11+14+27+34+29+21+44+24）
求解得：花费P （总）=1980.16元 5.2. 问题二的求解
由问题一的求解已找出使总费用最小的最短路径，因此在问题二中，只需沿着最小路径，具体分配载重量不同的运输车辆。考虑到一辆载重大的运输车每公里的运营费用远大于载重小的运输车，因为在每吨物资每公里均为2元的情况下，载重越多，运营公
里数越多，所需总费用也越多，因此，在分配时，首先应考虑尽量分配大的运输车，先让载重大的运输车前往距离近的运输点。再让载重小一些的运输车前往距离远的运输点，此种情况下使运输费用得到优化。具体分配载重不同的车辆时，原则是尽量用一辆运输车运送最短路上相邻的需求点需求物资。即使最短路上需求点的需求量之和先满足八吨的运输车，再满足六吨的运输车，最后满足四吨的运输车。离仓库越近的需求点，使用的的运输车载重越大。 具体分配情况如表三所示:
对于该方案：
我们派出去七辆车，分别开往3，8，21，27，26，24，30，7这七个站点。
第一条路线有： 8吨的车
车载重为7.65吨，其行程为41km ，返回时行驶了5km. ，停留了60分钟， 共用时约为2小时；
'6'+T16'+T5'+T4'+T2'）+0.5×5 花费为：2×（T 31+T第二条路线有： 8吨的车
车载重为7.6吨，其行程为80km ，返回时行驶了27km. ，停留了60分钟， 共用时约为3.5小时；
'+T10'+T12'+T11'+T22'）+0.52×7 花费为：2×（T 8'+T20
第三条路线有： 6吨的车
车载重为5.5吨，其行程为54km ，返回时行驶了21km. ，停留了30分钟， 共用时约为2.5小时；
'+T9'+T14'）+0.5×21 花费为：2×（T 21
第四条路线有： 6吨的车
车载重为5.9吨，其行程为76km ，返回时行驶了34km. ，停留了40分钟， 共用时约为3.7小时；
'+T15'+T19'+T25'）+0.5×34 花费为：2×（T 27
第五条路线有： 6吨的车
车载重为5.6吨，其行程为73km ，返回时行驶了20km. ，停留了30分钟， 共用时约为2.6小时；
'+T29'+T13')+0.5×20 花费为：2×（T 26
第六条路线有： 6吨的车
车载重为5.2吨，其行程为87km ，返回时行驶了34km. ，停留了30分钟， 共用时约为2.6小时；
'+T23'+T28'）+0.5×34 花费为：2×（T 24第七条路线有：
4吨的车
车载重为3.6吨，其行程为71km ，返回时行驶了18km. ，停留了20分钟， 共用时约为2.5小时；
'+T17'）+0.5×18 花费为：2×（T 30
第八条路线有： 4吨的车（路线七的车）
车载重为3.6吨，其行程为10km ，返回时行驶了24km. ，停留了20分钟， 共用时约为1.3小时；
'+T18'T 7'+T18'）+0.5×24 花费为：2×（T 7
综上：对第一到第八条路线有：
''总花费P （总）=2×（T 31+T6+即 ：花费P （总）=
29
'）+0.5×5++T2'+T18'）+0.5×24 +（T 7
2⨯∑T i '+0.5⨯（5+27+21+34+20+34+18+24）
i =1
=2⨯（T 1'+T 2'+T 3'+T 4'+
'）+T 30+0.5⨯（5+27+21+34+20+34+18+24）
此时求解得：花费P （总）=1969.66元
六、模型结果的分析和检验
1.1. 在研究物资调配问题时，我们忽略了交通，天气等客观因素，大大简化了最短路
径的建立与求解。
1.2. 最初我们便通过“化零为整”思想确立了一条“经济”上最短路径，并在下文求
解最低费用以及运输车的具体调配中深刻落实。这样便最大程度上保证总运输费用最低这一主旨，应该说在落实“最低费用”方面是相当可靠的，也是可行的。并且最终我们利用此方法求解出的低费用，也证明了这一点。但是这个模型也并非最优的，因为此模型没有充分考虑时间这个约束条件。换言之，如果以“最低费用”为主要要求，我们的模型有很高的可行性；如果以“时间”为主要要求，此模型可能会产生较大误差。但是，这个误差并非无法弥补的，我们又可以通过“人工改进调配”，灵活的运用此模型。
1.3. 在第一问中，我们最终选择八辆车非满载的调配方案，并求解出了相对最低的运
输费用。因为在问题中我们已经给出了每辆车要经过的具体路线以及需要的承载 量，于是便可以按着具体的运输方案进行检验，经过多次求解调配，发现每次的 误差并不大，这便一定程度说明此模型的稳定性与可行性；而在第二问中，我们通过同样的方法，结合利用mathematic 软件，计算检验。
1.4 .仓库每天要运送的物资在早上出发时间之前已经全到了，没有到的当天就不运送
这种模型现在已经很成熟，因此采用这种解法应该能够达到减少运费的要求。且总费用控制在了一个较为合理的范围内。但是由于物资调运是一个比较复杂的问题设计到众多的变量，上述模型尚有许多因素没有考虑在内。比如每辆车送完物资，回来再准备第二趟运送这个过程也要花时间，这个时间没有考虑到时间范围内，还有像城市交通不平衡等问题，货物分类等问题。
七、模型的推广
目前 ,物流配送车辆优化调度在国外已广泛运用于生产和生活的各个方面 ,如报纸、 牛奶投递及线路优化 ,工业原材料和成品的运输 ,电话或网络购物的车辆配装及线路设计 ,航运公司轮船经过港口和货物装卸的优化设计 ,连锁商店的送配货等等 ,
并已经取得了极大的经济效益. 如美国沃尔玛特百货有限公司 ,其成为全球零售业霸主的首要因素是拥有了最先进的物流配送指挥系统 ,全球各门店通过卫星实现联网 ,可以最大限度地降低其商品物流成本和增加销售量 ,从而在竞争中始终处于优势地位[56 ] 在我国 ,随着国民经济健康稳定的高速发展 ,市场经济日益发达 ,各种生产经营方式发展得十分迅速. 在生产活动中 ,提出了以零库存为目标的Just2in2time 模式; 而各式连锁经营的便利店和直送业务的蓬勃发展 , 也使零售业物流配送呈现出多频度、 小批次的特点 ,这些都对以运输为中心的物流配送活动提出了更高的要求. 但就目前情况而言 ,我国的VRP 研究仍然有限 ,可以说仍未能满足经济发展的需要. 首先是起步较晚 ,通用理论研究较少; 其次 ,对于具体问题提出的应用研究相对较多 ,但多为对具体算法的部分改进 ,且限于各自的适用条件 ,局限性较强.
八、模型的评价与优化
9.1模型的优缺点分析 9.1.1模型的优点
1、花费最小路的思想。将总费用最小分解为任意两个需求点间费用最小，即若每一需求点到下一需求点的花费最小，则总花费最小。从而由通过计算每两个需求点间费用最小而得到总费用最小。避免了通过穷举法搜索。
2、各需求点经济坐标的合成。将各需求点费用的两个影响因素地理位置与需求量合成一个新的坐标，从而减少了变量的个数，大大简化问题，至此使每个需求点费用直接与总费用相联系。
3、统一所有量的单位。对最小路上个边权的意义的深化。在将各需求点的坐标单位合成为吨·千米后，将运输车载重6吨及速度为40千米/小时合成为240吨·千米/小时，计算时按不是按地理意义上的最短路而是按花费意义上的最短路，对问题的抽象与简化。
4、在研究物资调配问题时，我们忽略了交通，天气等客观因素，大大简化了最短路径的建立与求解。
5、作图表示出最短路具体路径，直观清晰。
6、在最短路的总体思想下，综合考虑时间与运费等客观约束条件，使模型更贴近实际，同时使运输车的调配更加合理清晰。 9.1.2模型的缺点
1、在第一问中要派出八辆车，在第二问中也要派出七辆车，派出的车辆过多，而实际上，新派出一辆车的成本远高于一辆车往返运输的成本。且在本题求解的两问中，各辆车总的运输时间离每天四小时的工作限制还有较大的余地，因此应考虑进一步优化调运方案，减少派出车辆的辆数。
2、虽然我们运用具体模型求解时，完全根据题中所给出的约束条件，但是交通状况，车速变化等客观因素仍然对模型的紧缺度有较大影响。
3、我们虽然通过“化零为整”，“人工优化”等措施最大程度上保证了运输车的最优调配，但是仍然不排除个别站点间最短距离与花费存在误差。 9.1.3模型的优化
由于我们运输车的工作时间没有充分利用，且没有充分考虑实际情况。对劳动力有较大的浪费。因此我们可以假设在行车时有平均耽搁时间为Td ，以及平均损耗为n 元/小时辆，工人的工资q 元/小时，每辆车过收费站的平均花费为w 元/小时对于运送较近的运输车，在影响工作时间不大的情况下可以运输两趟。因此在花费还应加入这些花费。
然后综合考虑，得出符合实际的最优解； 优化模型求解： 设时间为t ；
''则：花费P=（n+q+w）⨯t+ 2⨯（ T 31+T6+同样的道理对于第二问我们有：
'）'+T17'+T7'+T18' ）+0.5⨯11+ +（T 30+0.5⨯24 +T4
''则：花费P=（n+q+w）⨯t+2⨯（T 31+T6+这样我们便可求出真实的解。
' ）+0.5⨯5+ +（T 7'+T18' ）+0.5⨯24 +T2
参考文献
[1]冯小杰，黄力伟，王力勤，尹成义，数学建模原理与案例：P120-P137，北京：科学出版社，2007
[2] 杨弋, 顾幸生, 物流配送车辆优化调度的综述，东南大学学报 (自然科学版):P105-P111,2003
[3]百度百科，Dijkstra 算法，http:// baike.baidu.com/view/7839.htm#783
附件
1. 附件一
附表一29个需求点物资需求量及地理坐标
2. 附件二
用mathematic 表示的29个需求点地理位置的作图程序： a=Import["D://data1.xls"][[1]];
ListPlot[a,PlotStyle→{Red},Filling→Axis] 3附件三
用mathematica 求解最短路以下为（0，0）点到a 1点的确定。此后由a 1确定a 2，由a 2确定a 3及以后的费用最小的需求点的方法与此相同。此处不再重复。
Clear[x,y,i,c];
x=Import["D://data2.xls"][[1,1]]; y=Import["D://data2.xls"][[1,2]];
p={};
For[i=1,i30,i++,
c=Abs[x[[2]]-x[[i]]]+Abs[y[[2]]-y[[i]]];
d=AppendTo[p,c];
e=Min[d];
]
Print[d,e]
Export["D://data3.xls",d]
ListPlot[a,PlotStyle{Red},Filling4附件四:最短路的确定及最短路上任意两点间的距离
1 2 3 4 1 0 12.5 6 13.5 2 12.5 0 6.5 1 3 6 6.5 0 7.5 4 13.5 1 7.5 0 5 13.2 6.1 7.2 5.1 6 6.8 9.3 2.8 8.3 7 18.2 12.9 12.2 11.9 8 19.2 6.7 13.2 5.7 9 34.5 22 28.5 21 10 16.8 8.7 15.2 9.7 11 25.2 22.7 29.2 23.7 12 22 12.9 19.4 13.9 13 54 41.5 48 40.5 14 37.8 25.3 31.8 24.3 15 39.6 27.1 33.6 26.1 16 12.6 6.7 6.6 5.7 17 27 23.5 21 22.5 18 19.2 12.1 13.2 11.1 19 42 29.5 36 28.5 20 24.3 11.8 18.3 10.8 21 39.2 26.7 33.2 25.7 22 32.4 19.9 26.4 18.9 23 37.8 35.3 41.8 36.3 24 50.4 37.9 44.4 36.9 25 54.4 41.9 48.4 40.9 26 55.1 42.6 49.1 41.6 27 37 24.5 31 23.5 28 68 55.5 62 54.5 29 44 31.5 38 30.5 30 86.1 73.6 80.1 72.6 Axis]
5
6 13.2 6.8 6.1 9.3 7.2 2.8 5.1 8.3 0 6.4 6.4 0 6.8 11.4 6 12.4 21.3 27.7 14.8 18 28.8 32 19 22.2 40.8 47.2 24.6 31 26.4 32.8 0.6 5.8 17.4 20.2 6 12.4 28.8 35.2 11.1 17.5 26 32.4 24 27.2 41.4 44.6 37.2 43.6 41.2 47.6 41.9 48.3 23.8 30.2 54.8 61.2 30.8 37.2 72.9
79.3
1 7 2 18.2 3 12.9 4 12.2 5 11.9 6 6.8 7 11.4 8 0 9 8 10 17.3 11 21.6 12 35.6 13 25.8 14 35.8 15 19.6 16 21.4 17 6.2 23 30.8 24 48.2 25 35.6 26 36.2 27 36.9 28 18.8 29 49.8 30 25.8 13 1 54 2 41.5 3 48 4 40.5 5 40.8 6 47.2 7 35.8 8 34.8 9 19.5 10 37.2 11 28.8 12 32 13
0 8 9 19.2 34.5 6.7 22 13.2 28.5 5.7 21 6 21.3 12.4 27.7 8 17.3 0 15.3 15.3 0 13.6 17.7 27.6 18.3 17.8 12.5 34.8 19.5 18.6 3.3 20.4 10.5 6.6 21.9
22.8 13.5 40.2 30.9 31.2 18.3 35.2 19.9 35.9 20.6 17.8 3.9 48.8 33.5 24.8 9.5 15 37.8 39.6 25.3 27.1 31.8 33.6 24.3 26.1 24.6 26.4 31 32.8 19.6 21.4 18.6 20.4 3.3 10.5 21 22.8 19.8 28.8 15.8 19 16.2 25.2 10 11 16.8 25.2 8.7 22.7 15.2 29.2 9.7 23.7 14.8 28.8 18 32 21.6 35.6 13.6 27.6 17.7 18.3 0 14 14 0 5.2 9.8 37.2 28.8 21 19.8 22.8 28.8 15.4
29.4
15.6 7.2 26.6 12.6 33.6 25.2 37.6 31.6 38.3 29.9 20.2 22.2 51.2 42.8 27.2 21.2 16 17 12.6 27 6.7 23.5 6.6 21 5.7 22.5 0.6 17.4 5.8 20.2 6.2 10.6 6.6 18.6 21.9 27.9 15.4 32.2 29.4 46.2 19.6 36.4 41.4 42.6 12 22 12.9 19.4 13.9 19 22.2 25.8 17.8 12.5 5.2 9.8 0 32 15.8 19 19.6
10.4 22.4 28.4 32.4 33.1 15 46 22 18 19.2 12.1 13.2 11.1 6 12.4 1 7.2 16.5 20.8 34.8 25 34.8
14
15 25.2 16 41.4 17 42.6 18 34.8 19 30.6 20 29.7 21 14.8 22 21.6 23 16.2 24 3.6 25 28 26 19.7 27 18.6 28 14 29 17.6 30 32.1 19 1 42 2 29.5 3 36 4 28.5 5 28.8 6 35.2 7 23.8 8 22.8 9 15.9 10 25.2 11 34.2 12 24.4 13 30.6 14 14.4 15 5.4 16 29.4 17 15 18 22.8 19 0 20 17.7 21 23 22 29.4 23 46.8 24 34.2 25 12.4 26
13.1 9 0 25.2 27 26.4 17.4 18.6 20.4 14.4 5.4 13.5 15.3 8.6 17.6 15 24 32.4 41.4 19.8 28.8 16.6 14.8 17.3 15.5 2.4 6.6 30.2 28.4 6.2 7.6 48.3 46.5 20 21 24.3 39.2 11.8 26.7 18.3 33.2 10.8 25.7 11.1 26 17.5 32.4 13.1 24.4 5.1 20 10.2 7.1 8.5 22.4 22.5 14 12.7 17.2 29.7 14.8 13.5 8.6 15.3 17.6 11.7 26.6 23.7 35 12.3 23.6 17.7 23 0 14.9 14.9 0 17.7 6.8 35.1 23.8 26.1 11.2 30.1 20.4 30.8 15.9 27 17.4 0 16.8 16.8 0 6.6 11.4 29.4 15 11.7 23.7 26.6 35 24.6 41.4 42 58.8 37.8 46.2 41.8 27.4 42.5 28.1 24.4 24 55.4 41 31.4 25 73.5 59.1 22 23 32.4 37.8 19.9 35.3 26.4 41.8 18.9 36.3 24 41.4 27.2 44.6 30.8 48.2 22.8 40.2 13.5 30.9 15.6 26.6 7.2 12.6 10.4 22.4 21.6 16.2 15 32.4 24 41.4 24.6 42 41.4 58.8 30 47.4 29.4 46.8 17.7 35.1 6.8 23.8 0 17.4 17.4 0 18 12.6 26.8 44.2 22.7 35.9 20.4 6.6 11.4 0 22.8 12.3 23.6 30 47.4 34.8 35.2 35.9 17.8 48.8 24.8 66.9 24 50.4 37.9 44.4 36.9 37.2 43.6 35.6 31.2 18.3 33.6 25.2 28.4 3.6 19.8 28.8 37.8 46.2 34.8 34.2 26.1 11.2 18 12.6 0 31.6 23.3
28 26 29 13 30 44.1 25 1 54.4 2 41.9 3 48.4 4 40.9 5 41.2 6 47.6 7 36.2 8 35.2 9 19.9 10 37.6 11 31.6 12 32.4 13 28 14 16.6 15 14.8 16 41.8 17 27.4 18 35.2 19 12.4 20 30.1 21 20.4 22 26.8 23 44.2 24 31.6 25 0 26 8.3 27 17.4 28 22.4 29 10.4 30
31.7 43.7 28.8 19.7 10 61.8 46.9 26 27 55.1 37 42.6 24.5 49.1 31 41.6 23.5 41.9 23.8 48.3 30.2 36.9 18.8 35.9 17.8 20.6 3.9 38.3 20.2 29.9 22.2 33.1 15 19.7 18.6 17.3 2.4 15.5 6.6 42.5 24.4 28.1 24 35.9 17.8 13.1 12 30.8 12.7 15.9 11 22.7 17.4 35.9 34.8 23.3 22.2 8.3 17.4 0 18.1 18.1 0 14.1 31 11.1 7 31 49.1 35.6 30.2 16.4 33.8 53.7 48.3 28 29 68 44 55.5 31.5 62 38 54.5 30.5 54.8 30.8 61.2 37.2 49.8 25.8 48.8 24.8 33.5 9.5 51.2 27.2 42.8 21.2 46 22 14 17.6 30.2 6.2 28.4 7.6 55.4 31.4 41 25 48.8 24.8 26 13 43.7 19.7 28.8 10 35.6 16.4 30.2 33.8 17.6 21.2 22.4 10.4 14.1 11.1 31 7 0 24 24 0 18.1 42.1 17.6 21.2 35.7 30 86.1 73.6 80.1 72.6 72.9 79.3 67.9 66.9 51.6 69.3 60.9 64.1 32.1 48.3 46.5 73.5 59.1 66.9 44.1 61.8 46.9 53.7 48.3 35.7 31.7 31 49.1 18.1 42.1 0