物资调运问题2

1、物资调运问题摘要如今物资调度问题普遍存在于生活的每个角落，利用有效的方法解决该问题会给 我们的工作生产带来许多便利，也会带来可观的利益。本文在确定了物资需求地 点和每个需求地点的需求量提下，用什么样的调度方案使所需的运费最少，来达 到题目的要求。本文主要从最省费用的角度来考虑问题的，这样我们不妨把每个地点都放到直角 坐标系中，每个地点都有自己的固定坐标，设发货点为坐标原点，每条街道都与 坐标轴平行，更具题目的要求我们可以得出：每两个点之间的距离就是两点横坐标之差的绝对值和纵坐标之差的绝对值之和。如A（x ,y）,B（x ,y ）两点， 1122他们之间的运输距离为S=,七|+ |七七|，而且必

2、须满足每辆车运输时间的条 件，所以对于问题一，由于要求费用最省，根据图形每辆车从原点出发到最近的 点送货，在满足各项条件的前提下，用多目标动态规划求解。并可以得出需要用 6辆6吨的车，最省费用为2151.00元。对于问题二，与问题一类似，只是具体 要求不同，最后求得所花费用为2428元。将问题一和问题二的运输费用描绘柱 状图（附录一图4），相比较之下，可以发现在路程较短时，问题二所用运输费 用较高；路程较长时，问题一所用运输费用较低。关键词：物资调度最优化图形求解多目标动态规划问题重述背景资料与条件某城区有29个物资需求点，需求点的地理坐标和每天物资的需求量见下表。每 天凌晨都要从仓库（第30

3、号站点）出发将物资运至每个需求点。现有一种载重6 吨的运输车，运输车平均速度为40公里/小时，每台车每日工作4小时，每个 需求点需要用10分钟的时间下货，运输车重载运费2元/吨公里，空载费用0.5 元/公里；并且假定街道方向均平行于坐标轴。需要解决的问题为了使得总运营费用最少，运输车应如何调度（需要投入多少台运输车，每 台车的调度方案，运营费用）？如果有载重量为4吨，6吨，8吨的三种运输车，又应该如何调度，失踪营运 费用最少？二、问题分析问题的重要性分析（社会背景）近年来，大规模的突发性公共事件如sars危机、印度洋海啸、冰雪灾害、汶川地 震等在世界各国频有发生，这些突发事件造成的巨大损失，给

4、人们留下了难以忘 怀的惨痛记忆。现代社会正处在高速发展的过程中，与此同时，人口、资源、环 境、公共卫生等方面的问题日益严重，这导致各类突发事件爆发的频率加快，影 响范围扩大，危害程度加剧。我国当前正处在突发性公共事件高发时期，随着城 镇化进程的加快，这种形势还在加剧，因此研究应急物流和应急物资调度问题具 有非常重要的现实意义。突发事件之后往往伴随着大量的应急物资需求，采用合 理的运输方式、运输路径和最优的应急物资调度方案，及时的将救援物资送达物 资需求点，这直接影响到整个突发性公共事件救援行动的成效。问题的思路分析问题一：从仓库开出一辆车，到任意未配送的需求点，然后将这辆车开往最近的 未服务的

5、需求点范围之内的邻居，并使运输时间小于4小时，各车所运物资的总 重量不超过6T。继续上述指派，直到各点总重量超过6T，或者运输时间大于4 小时。最后车辆返回仓库，记录得到的可行行程（即路线）。对另一辆车重复上 述安排，直到没有未服务的需求点。对得到的可行的行程安排解中的每一条路径， 求解一个旅行商问题，决定访问指派给每一条行程的车辆的顺序，最小化运输总 距离。得到可行解的行程安排解后退出。问题二：车辆有4吨、6吨、8吨，同理运输时间小于4小时，各线路所运物资 最大不能超过8T。在计算过程中，确定具体使用哪种类型的运输车。对得到的 可行的行程安排解中的每一条路径，计算所花费用，最后与问题一比较。

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

7、02017122.70146272.002113131.80129281.002420141.801012292.102516150.60714300.0000将表1的30个点绘在坐标系上。图1三、基本假设3.1.模型假设运输车在运行的过程中无红绿灯现象也没有意外的发生，即不花时间运输车中途不停运输车回到仓库的配货时间不计每个物资点只停留一次运输车沿街道方向均平行于坐标轴运输车在中途除了送货之外没有别的时间耽搁本文所用的资料和数据均真实可靠四、符号说明4.1.模型符号说明T i站点的物资需求量（i为站点编号，（x ,y）为需求点的坐标）M载运输车运输物资的总重费用M空运输车空载的总重费用M运输

8、车运输物资的总费用N运输车运输物资的总次数K运输车的总辆量N j第j个运输车的次数1运输车在站点编号为i的需求点所送物资时为10运输车在站点编号为i的需求点未送物资时为0b = 1第m条线路选择站点编号为i的需求点是最远点时为1b = 0第m条线路选择站点编号为i的需求点是最近点时为0五、模型的建立与求解模型一的建立与求解：本模型考虑用多目标动态规划求解。由于问题中只要求给出一个合理的方案，故 只要满足条件运输车的工作时间上限是4个小时以及每条路线的最大载重 量不大于6T即可，本模型中追加两个目标一一路程最短和车辆最少。可以通过 以下方法实现：每一个行程的第一个需求点是距离仓库最近的未服务的需

9、求点。 用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。整理作图， 即可得到最优化结果。本模型中以满足需求的费用最小的车辆行驶路径,且使用 尽量少的运输车，即，具体操作：第一条行程中访问了节点0-1-3-4-0，是因为1距离原点最近，因此由1出发，3是距离1点最近的点，而且两处物资量之和为4,小于每辆最大负重量，可以 继续指配。接着，4是距离3最近的点，而且三处物资量之和为5.2，仍小于6, 还可以继续指配。在剩下的未服务送货点中，再继续扩充，发现就会超出“ 6” 这个上限，因此选择返回，所以0-1-3-4-0就为第一条路线所含有的需求点。第二条行程中访问了节点0-2-5-6-1

10、5-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就为第二条路线所含有的送货点。第三条行程中访问了 0-9-8-7-0,是因为在第二条形成以后剩下的为服务的送 货点中，9点距离原点最近，

11、然后8是离9最近的点，7是离8最近的点，而且 三个点的总货重量为5.9吨，小于6吨，但在接下来的点中找不到符合条件的送 货点了，所以只能从最近的路线返回原点。由计算得出所用的时间也在要求之内。第四条行程中访问了 0-10-11-12-0，是因为在接下来的点中10离原点最近， 接着又找到11点然后12点最后选择最近的道路回来，其中三个货点的货的总重 量为5.6吨，时间在四小时之内。第五条路线访问了 0-16-17-18-24-0，是因为在接下来的点中16点距离原点 最近，该路线的四个送货点的总重量为5.4吨小于6吨，且时间在允许的范围内。第六条路线访问了 0-13-19-25-26-0，因为在剩

12、下的点中13点距离原点最近， 然后14和12又划为别的路线而且又不满足货物总量的限制要求，所以选择19 点然后就是25点，排除24点之后选择了 26点，这四个点的货物总量为5.6吨， 在货物总量的限制范围内。同样总运输时间也不超过4小时。第七条路线访问了 0-22-21-20-23-0，是因为在剩下的点中22距离原点最近， 然后接着选择21，然后20，然后再去23点，这四个点的货物总重量为5.8吨， 时间为2.6167小时。第八条路线访问了 0-27-29-28-0，因为剩下的三个点，总货量为5.1吨总路 程为100公里时间为3小时。符合题目的要求。在这八条路线中1、2条路线合用一辆车，3、4

13、条路线合用一辆车，其余的路线 各配用一辆车。详细的数据见表2和表3:详细流程图如下:找离原点最近的点设为A,且该点的访问标志设， 为被访问，该点物资需- 求量为队输出该点找次远点NY找点撬近的点，物资 重量为粗，且Wl+W6,找到符合条件的点，且不_lt 一个是选择物资质量最大的那个点，标志设为被访问，输出该点，赋值给A,且WW1+W图2找离原该点最近的点A,且该点的访问标志设为被访问，该点需求物资重量为 w,输出该点；找点v最近的点，物资重量为w,且wl+w6,当其不成立时找次远点；找到符合条件的点，且不止一个时选择物资重量最重的那个点，访问标志设 为被反问，并输出该点，赋值给V,且w=w+

14、wl；执行Y。找不到符合条件的点时 执行N。用该算法得到的各路线为：Or15r 14(3)Ot IOt 11- 12-0Or 16t 17t 18240Or 13r 19252600t22t21t20t23t002729280根据以上路线，计算。图3表2线路序 号所经站 数最近点所用时 （小时）总载重（T）总路程（公里）131（3,2）1.15.224252（1,5）2.18335.5554339（10,2）1.454.9384310（14,0）1.655.6465416（2,16）2.41675.4706413（12,9）2.51675.6747422（21,0）2.61675.878832

15、7（21,13）35.11002916.933443.15484然后，根据所经历的时间进行划分，确定运输车数量。在工作时间小于4小时的 前提下，最终只需要六辆运输车，第一条线路和第二条线路由一辆车运送，第三 条和第四条线路由一辆车运送，则各运输车具体情况如下（表4）:表3车辆序列线路所到需求点已行路程+载重空载路程11+21342561514335+5.24+2.74+1.26+5.554+4.556+3.77+2.45+1.823+49871011123612+4.95+3.55+1.214+5.66+3.86+2.735161718243418+5.46+3.96+3.16+1.64613

16、1925263721+5.66+3.82+2.98+1.057222120233621+5.86+4.07+2.88+1.4682729284434+5.17+3.15+1.0根据表1.3,运输车重载运费2元/吨公里，空载费用0.5元/公里，计算运输车 的费用为下表（表4）：表4车辆序号线路非空载总 费用（元）空载费用（元）总费用（元）11+2282.216.5298.723+4399.418417.435297.617314.646308.418.5326.957353.218371.268400.222422.220411102151模型求解结果：第一辆车：0 T 1 T 3 T 4 T

17、0 和 0 T 2 T 5 T 6 T 15 T 14 T 0第二辆车：0 T 9 T 8 T 7 T 0 和 0 T 10 T 11 T 12 T 0第三辆车： 0 T 16 T 17 T 18 T 24 T 0第四辆车： 0 T 13 T 19 T 25 T 26 T 0第五辆车：0 T 22 T 21T 20 T 23 - 0 第六辆车： 0 27 29 28 0 所花费用为：2151.00元5.2.模型二的建立与求解：此时运输车的种类有4吨，6吨，8吨，运用问题一的方法：首先选择距离远点 最近的点a，再找距离a点最近的点，假设是b，且Ta+Tb=8，那么就继续寻找 距离点b最近的点，并

18、计算物资总重，比较。继续以上步骤，当总重大于8终止。 然后比较总重相加过程中接近且小于4、6、8时的部分总重的差的绝对值，取绝 对值最小的。例如，1线路：最初计算线路是0-1-3-4-6-5-0，此时的总重量为 7.35，但是在到达3时为4，|4-4|8-7.35|,所以第一条线路只需到达3即可 返回。重复以上步骤，得到下列7条线路：0 1 3 29 04吨运输车0 2 5 4 7 8 98 吨运输车0 T 10 T 11 T 12 T 06 吨运输车0 T 6 T 15 T 14 T 19 T 25 T 18 T 08 吨运输车0 T 16 T 17 T 24 T 26 T 27 T 28

19、T 08 吨运输车0 T 13 T 20 T 21T 22 T 23 T 08 吨运输车各条线路详细情况表5:表5线路序 号所经站 数最近点所用时 间（小 时）总载重（T）总路程（公里）131（3,2）2.556.182262（1，5）2.057.95423310（14,0）1.655.646466（3,11）2.77.9685616（2,16）3.57.91006513（12,9）2.63337.6722915.083343.05410根据工作时间小于4小时划分组合，第一条线路和第七条线路由一辆车运送，因 此总共需要六辆运输车，具体情况如下，表6：运输车编 号线路所到需求点已行路程+载重空载

20、路 程11+71329415+6.14+3.632+2.122254789126+7.954+6.955+6.15+4.95+3.75+1.4331011122014+5.66+3.86+2.744615141925182814+7.97+6.65+6.05+4.22+3.37+1.4551617242627284418+7.96+6.410+5.67+4.05+3.010+1.06613202321222121+7.67+5.88+4.49+3.06+1.8表6计算费用为表7表7运输车 编号线路（重）非空载总费用（元）（M空）空 载费用 （元）（M）总费 用（元）11+7224.220.52

21、44.722312631833234.810244.844448.414462.455579.222601.266546.410.5556.9-2345832428模型求解结果：第一辆车：0 T 1T 3 T 0 和 0 T 29 T 0第二辆车：0 T 2 T 5 T 4 T 7 T 8 T 9第三辆车： 0 T 10 T 11 T 12 T 0第四辆车：0T 6T 15T 14T 19T 25T 18- 0 第五辆车： 0 16 17 24 26 27 28 0 第六辆车： 0 13 20 23 21 22 0 所花费用为：2428元路径为图4：图4将问题一和问题二的运输费用描绘柱状图（附

22、件一图5）,相比较之下，可以发 现在路程较短时，问题二所用运输费用较高；路程较长时，问题一所用运输费用 较低。六、模型的分析和检验仓库每天要运送的物资在早上出发时间之前已经全到了，没有到的当天就不运送， 这种模型现在已经很成熟，因此采用这种解法应该能够达到减少运费的要求。 但是由于物资调运是一个比较复杂的问题设计到众多的变量，上述模型尚有许多 因素没有考虑在内。比如每辆车送完物资，回来再准备第二趟运送这个过程也要 花时间，这个时间没有考虑到时间范围内。还有像城市交通不平衡等问题，货物 分类等问题。结果和误差分析：理论上总时间算下来是16.6084小时和16.1583小时，每辆车平均工作4个小时

23、， 因此车数算下来平均是4.1521和4.039575辆车，在实际情况中4辆车就能送 完所有的物资。七、模型的推广该模型广泛运用于物资调度问题，大规模的突发性公共事件如sar诡机、印度洋 海啸、冰雪灾害、汶川地震等重大问题，在面临这些问题时采用多目标动态分析， 并且结合图表，这样会很大程度上加快解决问题的速度，减少不必要的损失，节 省运输资金。而且突发事件之后往往伴随着大量的应急物资需求，采用合理的运 输方式、运输路径和最优的应急物资调度方案，及时的将救援物资送达物资需求 点，这直接影响到整个突发性公共事件救援行动的成效。八、模型的评价与优化模型的优点本文此方案能合理的调度物资、分配物资的运输

24、、怎样调度运输费的最低，使供 货商减小运输过程中的费用，加快运输时间，合理的配装物资，合理的选择运输 路线，从而使供货商增大利润，收利最大。模型的缺点此方案没有考虑运输过程中有红绿灯现象、意外的发生、中途遇某事而停车的现 象等，实际上这些现象和状况是存在的，我们却理想化的去调度物资的运输。理 论值和实际值是相差很大的，这方案还需进行实践的验证才能更好的分配、调运 物资。问题二，我们在考虑到运输成本的最低的前提下，没有用到4吨的运输车， 如果用4吨车必须把路线（1）拆成两部分0T 1T 3T 0，0T 29T 0这样没有 直接用8吨车一次运完便宜。参考文献：霍亮，空间物流信息系统，中国测绘出版社

25、：2006, 2(66-75)郑莉，董渊，张瑞，面向对象的程序设计和c+ (第三版)，清华大学出版 社：2005.9(369-381)张磊。车辆调度问题的混合运算。铁路运输与经济，第三十卷第8附件：1.附件一问题一与问题二总费用对比图52.附件二计算过程中的部分程序：#include#include#include#define max 1000using namespace std;structver(int x;int y;intnum;float weight;bool visited30;ver v30;int next1()(intk,min=max,tag=0;float w;fo

26、r(int i=1;i30;i+)(if(visitedi=false&vi.x+vi.yw)k=i;w=vi.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;i30i+)(if(visitedi=false&fabs(vk.x-vi.x)+fabs(vk.y-vi.y)min&w+vi.weight=6)min=fabs(vk.x-vi.x)+fabs(vk.y-vi.y);m=i;tag=1;if(visitedi=false&fabs(vk.x

27、-vi.x)+fabs(vk.y-vi.y)=min&w+vi.weightvm.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;visitedk=true;w=vk.weight;distance=vk.x+vk.y;time=(vk.x+vk.y)/40.0;cout0vk.num;tag二next2(k,w);while(tag!=0)num_of_station

28、+;visitedtag=true;coutvtag.num;w=w+vtag.weight;time=time+(fabs(vk.x-vtag.x)+fabs(vk.y-vt ag.y)/40.0;if(time+(vtag.x+vtag.y)/40.0+(num_of_station+ 1)/6.0=4)(distance二distance+fabs(vk.x-vtag.x)+fabs(vk .y-vtag.y);k=tag;tag二next2(tag,w);else(time二time-(fabs(vk.x-vtag.x)+fabs(vk .y-vtag.y)/40.0;break;ti

29、me=time+(vk.x+vk.y)/6.0+(num_of_station+1)/4.0;distance二distance+vk.x+vk.y;cout0timedistancekmwendl;k=next1();int main()(int i;ifstreaminfile(1.txt)；cout各站点的坐标及相关信息是：endl;for(i=0;ivi.numvi.xvi.yvi.weight;coutvi.num(vi.x,vi.y)：vi.weigh tt;coutendl;coutn各条送快递的线路所用时间该线路总路程endl;way();return 0;2(181(15I-q421-17T十t1!2a*11J_QJAJ16尸15-q5-1-十d747oTTJP171226K730jPA_Q_-|3-65q81q1Q1P11Q19(-2012345678 9 1011121314151617181920212223242526272829300,1,30About:有向图的Dijkstra算法实现Author: Tanky WooBlog: HYPERLINK http:/www.WuTianQ www.WuTianQ#include usingnamespace std;constint maxn