物资调运问题2

摘 要

如今物资调度问题普遍存在于生活的每个角落，利用有效的方法解决该问题会给我们的工作生产带来许多便利，也会带来可观的利益。本文在确定了物资需求地点和每个需求地点的需求量提下，用什么样的调度方案使所需的运费最少，来达到题目的要求。

本文主要从最省费用的角度来考虑问题的，这样我们不妨把每个地点都放到直角坐标系中，每个地点都有自己的固定坐标，设发货点为坐标原点，每条街道都与坐标轴平行，更具题目的要求我们可以得出：每两个点之间的距离就是两点横坐标之差的绝对值和纵坐标之差的绝对值之和。如A（x1,y1）,B(x2,y2)两点，他们之间的运输距离为S=x2x1y2y1，而且必须满足每辆车运输时间的条件，所以对于问题一，由于要求费用最省，根据图形每辆车从原点出发到最近的点送货，在满足各项条件的前提下，用多目标动态规划求解。并可以得出需要用6辆6吨的车，最省费用为2151.00元。对于问题二，与问题一类似，只是具体要求不同，最后求得所花费用为2428元。将问题一和问题二的运输费用描绘柱状图（附录一图4），相比较之下，可以发现在路程较短时，问题二所用运输费用较高；路程较长时，问题一所用运输费用较低。

关键词：物资调度 最优化 图形求解 多目标动态规划

一、 问题重述

1.1. 背景资料与条件

某城区有29个物资需求点，需求点的地理坐标和每天物资的需求量见下表。每天凌晨都要从仓库（第30号站点）出发将物资运至每个需求点。现有一种载重 6吨的运输车，运输车平均速度为40公里／小时，每台车每日工作 4小时，每个需求点需要用10分钟的时间下货，运输车重载运费2元/吨公里，空载费用0.5元/公里；并且假定街道方向均平行于坐标轴。 1.2.需要解决的问题

1. 为了使得总运营费用最少，运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）？

2.如果有载重量为4吨，6吨，8吨的三种运输车，又应该如何调度，失踪营运费用最少？

二、问题分析

2.1.问题的重要性分析（社会背景）

近年来，大规模的突发性公共事件如sars危机、印度洋海啸、冰雪灾害、汶川地震等在世界各国频有发生，这些突发事件造成的巨大损失，给人们留下了难以忘怀的惨痛记忆。现代社会正处在高速发展的过程中，与此同时，人口、资源、环境、公共卫生等方面的问题日益严重，这导致各类突发事件爆发的频率加快，影响范围扩大，危害程度加剧。我国当前正处在突发性公共事件高发时期，随着城镇化进程的加快，这种形势还在加剧，因此研究应急物流和应急物资调度问题具有非常重要的现实意义。突发事件之后往往伴随着大量的应急物资需求，采用合理的运输方式、运输路径和最优的应急物资调度方案，及时的将救援物资送达物资需求点，这直接影响到整个突发性公共事件救援行动的成效。 2.2.问题的思路分析

问题一：从仓库开出一辆车，到任意未配送的需求点，然后将这辆车开往最近的未服务的需求点范围之内的邻居，并使运输时间小于4小时，各车所运物资的总重量不超过6T。继续上述指派，直到各点总重量超过6T，或者运输时间大于4小时。最后车辆返回仓库，记录得到的可行行程（即路线）。对另一辆车重复上述安排，直到没有未服务的需求点。对得到的可行的行程安排解中的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的车辆的顺序，最小化运输总距离。得到可行解的行程安排解后退出。

问题二：车辆有4吨、6吨、8吨，同理运输时间小于4小时，各线路所运物资最大不能超过8T。在计算过程中，确定具体使用哪种类型的运输车。对得到的可行的行程安排解中的每一条路径，计算所花费用，最后与问题一比较。

表1给出了各个需求点的需求量，为了完成任务，在工作时间范围内，每辆运输车可以承担两条甚至更多的线路。表中给出了需求点序号，编号，需求物资量T，以及需求点的直角坐标。 表1

坐标（km） 坐标（km） 站点编号 需求量T 站点编号 需求量T x y x y 1 2.50 3 2 16 1.50 2 16 2 1.00 1 5 17 0.80 6 18 3 1.50 5 4 18 1.50 11 17 4 1.20 4 7 19 0.90 15 12 5 0.85 0 8 20 1.40 19 9 6 1.30 3 11 21 1.20 22 5 7 1.20 7 9 22 1.80 21 0 8 2.30 9 6 23 1.40 27 9 9 1.40 10 2 24 1.60 15 19 10 1.80 14 0 25 1.90 15 14 11 1.10 17 3 26 1.00 20 17 12 2.70 14 6 27 2.00 21 13 13 1.80 12 9 28 1.00 24 20 14 15 1.80 0.60 10 7 12 14 29 30 2.10 0.00 25 0 16 0 将表1的30个点绘在坐标系上。

图1

三、基本假设

3.1.模型假设

1. 运输车在运行的过程中无红绿灯现象也没有意外的发生，即不花时间 2. 运输车中途不停

3. 运输车回到仓库的配货时间不计 4. 每个物资点只停留一次

5. 运输车沿街道方向均平行于坐标轴

6. 运输车在中途除了送货之外没有别的时间耽搁 7. 本文所用的资料和数据均真实可靠

四、符号说明

4.1.模型符号说明 Ti （x,y）站点的物资需求量（i为站点编号，为需求点的坐标） iiM载 M空 M N K Nj 运输车运输物资的总重费用 运输车空载的总重费用 运输车运输物资的总费用 运输车运输物资的总次数 运输车的总辆量 第j个运输车的次数 运输车在站点编号为i的需求点所送物资时为1 运输车在站点编号为i的需求点未送物资时为0 第m条线路选择站点编号为i的需求点是最远点时为1 第m条线路选择站点编号为i的需求点是最近点时为0 1 0 bi1 bi0 五、模型的建立与求解

5.1.模型一的建立与求解：

本模型考虑用多目标动态规划求解。由于问题中只要求给出一个合理的方案，故只要满足条件——运输车的工作时间上限是4个小时以及每条路线的最大载重量不大于6T即可，本模型中追加两个目标——路程最短和车辆最少。可以通过以下方法实现：每一个行程的第一个需求点是距离仓库最近的未服务的需求点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。整理作图，即可得到最优化结果。本模型中以满足需求的费用最小的车辆行驶路径,且使用尽量少的运输车，即， 具体操作：

1.第一条行程中访问了节点0-1-3-4-0，是因为1距离原点最近，因此由1出发，3是距离1点最近的点，而且两处物资量之和为4，小于每辆最大负重量，可以继续指配。接着，4是距离3最近的点，而且三处物资量之和为5.2，仍小于6,还可以继续指配。在剩下的未服务送货点中，再继续扩充，发现就会超出“6”这个上限，因此选择返回，所以0-1-3-4-0就为第一条路线所含有的需求点。 2.第二条行程中访问了节点0-2-5-6-15-14-0，是因为在剩下的未服务送货点中，2距离原点最近，因此由,2出发，5是距离2点最近的点，而且两处物资量之和为1.85，小于每辆最大负重量，可以继续指配。接着，6是距离5最近的点，而且三处物资量之和为2.15，仍小于6,还可以继续指配。在剩下的未服务送货点中，15距离6最近，总物资量之和为3.75。再继续扩充，14距离15最近，总物资量之和为5.55吨。再继续扩充，发现就会超出“6”这个上限，因此选择返回，所以0-2-5-6-15-14-0就为第二条路线所含有的送货点。

3.第三条行程中访问了0-9-8-7-0，是因为在第二条形成以后剩下的为服务的送货点中，9点距离原点最近，然后8是离9最近的点，7是离8最近的点，而且三个点的总货重量为5.9吨，小于6吨，但在接下来的点中找不到符合条件的送货点了，所以只能从最近的路线返回原点。由计算得出所用的时间也在要求之内。 4.第四条行程中访问了0-10-11-12-0，是因为在接下来的点中10离原点最近，接着又找到11点然后12点最后选择最近的道路回来，其中三个货点的货的总重量为5.6吨，时间在四小时之内。

5.第五条路线访问了0-16-17-18-24-0，是因为在接下来的点中16点距离原点最近，该路线的四个送货点的总重量为5.4吨小于6吨，且时间在允许的范围内。 6.第六条路线访问了0-13-19-25-26-0，因为在剩下的点中13点距离原点最近，然后14和12又划为别的路线而且又不满足货物总量的限制要求，所以选择19点然后就是25点，排除24点之后选择了26点，这四个点的货物总量为5.6吨，在货物总量的限制范围内。同样总运输时间也不超过4小时。 7.第七条路线访问了0-22-21-20-23-0，是因为在剩下的点中22距离原点最近，然后接着选择21，然后20，然后再去23点，这四个点的货物总重量为5.8吨，时间为2.6167小时。

8.第八条路线访问了0-27-29-28-0，因为剩下的三个点，总货量为5.1吨总路程为100公里时间为3小时。符合题目的要求。

在这八条路线中1、2条路线合用一辆车，3、4条路线合用一辆车，其余的路线各配用一辆车。详细的数据见表2和表3:

详细流程图如下：

图2

1,找离原该点最近的点A，且该点的访问标志设为被访问，该点需求物资重量为w，输出该点；

2，找点v最近的点，物资重量为w1，且w1+w<6，当其不成立时找次远点； 3，找到符合条件的点，且不止一个时选择物资重量最重的那个点，访问标志设为被反问，并输出该点，赋值给v，且w=w+w1；执行Y。找不到符合条件的点时执行N。 用该算法得到的各路线为： （1）01340

（2）025615140 （3）09870

（4）01011120 （5）0161718240 （6）0131925260 （7）0222120230 （8）02729280 根据以上路线，计算。

图3

表2 线路序号 1 2 3 4 5 6 7 8 所经站数 3 5 3 3 4 4 4 3 29 最近点 1（3,2） 2（1,5） 9（10,2） 10（14,0） 16（2,16） 13（12,9） 22（21,0） 27（21,13） 所用时总载重(小时) （T） 1.1 5.2 2.1833 5.55 1.45 4.9 1.65 5.6 2.4167 5.4 2.5167 5.6 2.6167 5.8 3 5.1 16.9334 43.15 总路程(公里) 24 54 38 46 70 74 78 100 484 然后，根据所经历的时间进行划分，确定运输车数量。在工作时间小于4小时的前提下，最终只需要六辆运输车，第一条线路和第二条线路由一辆车运送，第三条和第四条线路由一辆车运送，则各运输车具体情况如下(表4)： 表3 车辆线路 序列 1 2 所到需求点已行路程+载重 空载路程 33 1 3 4 2 5 6 15 14 1+2 5+5.2 4+2.7 4+1.2 6+5.54+4.56+3.7 7+2.4 5+1.8 5 5 3+4 9 8 7 10 11 12 36 3 4 5 6 5 6 7 8 12+4.9 5+3.5 5+1.2 14+5.6 6+3.8 6+2.7 16 17 18 24 18+5.4 6+3.9 6+3.1 6+1.6 13 19 25 26 21+5.6 6+3.8 2+2.9 8+1.0 22 21 20 23 21+5.8 6+4.0 7+2.8 8+1.4 27 29 28 34+5.1 7+3.1 5+1.0 34 37 36 44 根据表1.3，运输车重载运费2元/吨公里，空载费用0.5元/公里，计算运输车

的费用为下表（表4）： 表4 车辆序号 1 2 3 4 5 6 线路 1+2 3+4 5 6 7 8 非空载总空载费用总费用费用(元) （元） （元） 282.2 399.4 297.6 308.4 353.2 400.2 2041 16.5 18 17 18.5 18 22 110 298.7 417.4 314.6 326.9 371.2 422.2 2151 模型求解结果：

第一辆车：01340 和025615140

第二辆车：09870和01011120 第三辆车：016171824 0 第四辆车：0131925260 第五辆车：0222120230 第六辆车：02729280 所花费用为：2151.00 元 5.2.模型二的建立与求解：

此时运输车的种类有4吨，6吨，8吨，运用问题一的方法：首先选择距离远点最近的点a，再找距离a点最近的点，假设是b，且Ta+Tb<=8，那么就继续寻找距离点b最近的点，并计算物资总重，比较。继续以上步骤，当总重大于8终止。然后比较总重相加过程中接近且小于4、6、8时的部分总重的差的绝对值，取绝对值最小的。例如，1线路：最初计算线路是0-1-3-4-6-5-0，此时的总重量为7.35，但是在到达3时为4，|4-4|<|8-7.35|,所以第一条线路只需到达3即可返回。重复以上步骤，得到下列7条线路：

1 013290 4吨运输车 2 0254789 8吨运输车

3 01011120 6吨运输车

4 0615141925180 8吨运输车 5 01617242627280 8吨运输车 6 013202122230 8吨运输车 各条线路详细情况表5: 表5 线路序号 1 2 3 4 5 6 所经站数 3 6 3 6 6 5 29 最近点 1（3,2） 2（1，5） 10（14,0） 6（3,11） 16（2,16） 13（12,9） 所用时总载重间（小（T） 时） 2.55 6.1 2.05 7.95 1.65 5.6 2.7 7.9 3.5 7.9 2.6333 7.6 15.08343.05 3 总路程(公里) 82 42 46 68 100 72 410

根据工作时间小于4小时划分组合，第一条线路和第七条线路由一辆车运送，因此总共需要六辆运输车，具体情况如下,表6： 运输车编线号 路 1 1+7 空载路程 41 所到需求点已行路程+载重 1 5+6.1 3 4+3.6 29 32+2.1 2 2 2 6+7.95 3 4 3 4 5 5 6 6 5 4 7 8 9 4+6.95+6.1 5+4.5+3.5+1.4 5 9 7 10 11 12 14+5.6 6+3.8 6+2.7 6 15 14 19 25 18 14+7.9 7+6.6 5+6.0 5+4.2+3.7+1.4 2 3 16 17 24 26 27 28 18+7.9 6+6.4 10+5.7+4.5+3.10+1.0 6 0 0 13 20 23 21 22 21+7.6 7+5.8 8+4.9+3.4 0 6+1.8 12 20 28 44 21 表6

计算费用为表7 表7 运输车编号 1 2 3 4 5 6 -- 线路 (重)非空载总费用(元) 224.2 312 234.8 448.4 579.2 546.4 2345 (M空)空载费用（元） 20.5 6 10 14 22 10.5 83 (M)总费用（元） 244.7 318 244.8 462.4 601.2 556.9 2428 1+7 2 3 4 5 6 -- 模型求解结果： 第一辆车：0130 和 0290 第二辆车：0254789 第三辆车：01011120

第四辆车：0615141925180 第五辆车：01617242627280 第六辆车：013202321220 所花费用为：2428元 路径为图4：

图4

将问题一和问题二的运输费用描绘柱状图（附件一图5），相比较之下，可以发现在路程较短时，问题二所用运输费用较高；路程较长时，问题一所用运输费用较低。

六、模型的分析和检验

仓库每天要运送的物资在早上出发时间之前已经全到了，没有到的当天就不运送，这种模型现在已经很成熟，因此采用这种解法应该能够达到减少运费的要求。 但是由于物资调运是一个比较复杂的问题设计到众多的变量，上述模型尚有许多因素没有考虑在内。比如每辆车送完物资，回来再准备第二趟运送这个过程也要花时间，这个时间没有考虑到时间范围内。还有像城市交通不平衡等问题，货物分类等问题。 结果和误差分析：

理论上总时间算下来是16.6084小时和16.1583小时，每辆车平均工作4个小时，因此车数算下来平均是4.1521和4..039575辆车，在实际情况中4辆车就能送完所有的物资。

七、模型的推广

该模型广泛运用于物资调度问题，大规模的突发性公共事件如sars危机、印度洋

海啸、冰雪灾害、汶川地震等重大问题，在面临这些问题时采用多目标动态分析，并且结合图表，这样会很大程度上加快解决问题的速度，减少不必要的损失，节省运输资金。而且突发事件之后往往伴随着大量的应急物资需求，采用合理的运输方式、运输路径和最优的应急物资调度方案，及时的将救援物资送达物资需求点，这直接影响到整个突发性公共事件救援行动的成效。

八、模型的评价与优化

8.1.模型的优点

本文此方案能合理的调度物资、分配物资的运输、怎样调度运输费的最低，使供货商减小运输过程中的费用，加快运输时间，合理的配装物资，合理的选择运输路线，从而使供货商增大利润，收利最大。

8.2.模型的缺点

此方案没有考虑运输过程中有红绿灯现象、意外的发生、中途遇某事而停车的现象等，实际上这些现象和状况是存在的，我们却理想化的去调度物资的运输。理论值和实际值是相差很大的，这方案还需进行实践的验证才能更好的分配、调运物资。问题二，我们在考虑到运输成本的最低的前提下，没有用到4吨的运输车，如果用4吨车必须把路线（1）拆成两部分0130，0290 这样没有直接用8吨车一次运完便宜。

参考文献：

[1] 霍亮，空间物流信息系统，中国测绘出版社 ：2006，2(66—75)

[2] 郑莉，董渊，张瑞，面向对象的程序设计和c++（第三版），清华大学出版社：2005.9(369-381)

[3] 张磊。车辆调度问题的混合运算。铁路运输与经济，第三十卷第8

附件：

1. 附件一

问题一与问题二总费用对比700600500总费用40030020010001234运输车的编号56总费用一总费用二

图5

2. 附件二

计算过程中的部分程序： #include #include #include #define max 1000

using namespace std; structver{ int x; int y; intnum;

float weight; };

bool visited[30]; ver v[30];

int next1(){

intk,min=max,tag=0; float w;

for(int i=1;i<30;i++){

if(visited[i]==false&&v[i].x+v[i].yw=v[i].weight; tag=1; }

if(visited[i]==false&&v[i].x+v[i].y==min&&v[i].weight>w){ k=i;

w=v[i].weight; tag=1; } }

if(tag)return k; else return 0; }

int next2(intk,float w){ int min=max,tag=0,m,i; for(i=1;i<30i++){

if(visited[i]==false&&fabs(v[k].x-v[i].x)+fabs(v[k].y-v[i].y)min=fabs(v[k].x-v[i].x)+fabs(v[k].y-v[i].y); m=i; tag=1; }

if(visited[i]==false&&fabs(v[k].x-v[i].x)+fabs(v[k].y-v[i].y)==min&&w+v[i].weight<=6&&v[i].weight>v[m].weight){ m=i;tag=1; }

}

if(tag)return m; else return 0; }

void way(){ int k;

float w; k=next1(); while(k!=0){

float time;

intnum_of_station=0,distance,tag; visited[k]=true; w=v[k].weight;

distance=v[k].x+v[k].y; time=(v[k].x+v[k].y)/40.0;

cout<<'0'<<\"->\"<\"; tag=next2(k,w); while(tag!=0){

num_of_station++; visited[tag]=true;

cout<\"; w=w+v[tag].weight;

time=time+(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/40.0;

if(time+(v[tag].x+v[tag].y)/40.0+(num_of_station+1)/6.0<=4){

distance=distance+fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y);

k=tag;

tag=next2(tag,w); }else{

time=time-(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/40.0;

break; } }

time=time+(v[k].x+v[k].y)/6.0+(num_of_station+1)/4.0; distance=distance+v[k].x+v[k].y;

cout<<'0'<<\" \"<int main(){ int i;

ifstreaminfile(\"1.txt\");

cout<<\"各站点的坐标及相关信息是：\"<visited[i]=false;

infile>>v[i].num>>v[i].x>>v[i].y>>v[i].weight;

cout<cout<cout<<\"\\n各条送快递的线路\"<<\" \"<<\"所用时间\"<<\" \"<<\"该线路总路程\"<return 0; }

20 2819 2418 1717 18 2616 16 291514 15 2513 2712 14 1911 6109 7 13 20 238 57 46 8 125 2 214 33 112 1 910 10 2201234567891011121314151617181920212223242526272829300,1,30

/*************************************** * About: 有向图的Dijkstra算法实现 * Author: Tanky Woo * Blog: www.WuTianQi.com

***************************************/

#include

usingnamespacestd;

constintmaxnum = 100; constintmaxint = 999999;

voidDijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum]) {

bool s[maxnum]; // 判断是否已存入该点到S集合中 for(int i=1; i<=n; ++i) {

dist[i] = c[v][i];

s[i] = 0; // 初始都未用过该点 if(dist[i] == maxint) prev[i] = 0; else

prev[i] = v; }

dist[v] = 0; s[v] = 1;

// 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中

// 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度 for(int i=2; i<=n; ++i) {

inttmp = maxint; int u = v;

// 找出当前未使用的点j的dist[j]最小值 for(int j=1; j<=n; ++j) if((!s[j]) &&dist[j]u = j; // u保存当前邻接点中距离最小的点的号码 tmp = dist[j]; }

s[u] = 1; // 表示u点已存入S集合中

// 更新dist

for(int j=1; j<=n; ++j) if((!s[j]) && c[u][j]intnewdist = dist[u] + c[u][j]; if(newdistdist[j] = newdist;

prev[j] = u; } } } }

voidsearchPath(int *prev,int v, int u) {

intque[maxnum]; int tot = 1; que[tot] = u; tot++;

inttmp = prev[u]; while(tmp != v) {

que[tot] = tmp; tot++;

tmp = prev[tmp]; }

que[tot] = v;

for(int i=tot; i>=1; --i) if(i != 1)

cout< \"; else

cout<int main() {

freopen(\"input.txt\ // 各数组都从下标1开始

intdist[maxnum]; // 表示当前点到源点的最短路径长度 intprev[maxnum]; // 记录当前点的前一个结点

int c[maxnum][maxnum]; // 记录图的两点间路径长度 int n, line; // 图的结点数和路径数

// 输入结点数 cin>> n; // 输入路径数 cin>> line;

int p, q, len; // 输入p, q两点及其路径长度

// 初始化c[][]为maxint for(int i=1; i<=n; ++i)

for(int j=1; j<=n; ++j) c[i][j] = maxint;

for(int i=1; i<=line; ++i) {

cin>> p >> q >>len; if(len< c[p][q]) // 有重边 {

c[p][q] = len; // p指向q

c[q][p] = len; // q指向p，这样表示无向图 } }

for(int i=1; i<=n; ++i) dist[i] = maxint; for(int i=1; i<=n; ++i) {

for(int j=1; j<=n; ++j) printf(\"%8d\printf(\"\\n\"); }

Dijkstra(n, 1, dist, prev, c);

// 最短路径长度