物资调运问题

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

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

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

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

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

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

7、5 19271410 67 4-42344-20r13J4*2152*381211 1*91022 .0051015202530三. 基本假设模型假设1. 运输车在运行的过程中无红绿灯现象也没有意外的发生，即不花时间2. 运输车中途不停3. 运输车回到仓库的配货时间不计4. 每个物资点只停留一次5. 运输车沿街道方向均平行于坐标轴6. 运输车在中途除了送货之外没有别的时间耽搁7. 本文所用的资料和数据均真实可靠四、符号说明模型符号说明T,站点的物资需求量（i为站点编号，（x,y）为需求点的坐标）M载运输车运输物资的总重费用M空运输车空载的总重费用M运输车运输物资的总费用N运输车运输物资的总次数

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

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

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

11、6吨，但在接下来的点中找不到符合条件的送货点了，所以 只能从最近的路线返回原点。由计算得出所用的时间也在要求之内。4第四条行程中访问了 0-10-11-12-0,是因为在接下来的点中10离原点最近， 接着又找到11点然后12点最后选择最近的道路回来，其中三个货点的货的总璽量为 吨，时间在四小时之内。5第五条路线访问了是因为在接下来的点中16点距离原点最近，该路线的四个送货点的总重量为吨小于6吨，且时间在允许的范围内。6第六条路线访问了 因为在剩下的点中13点距离原点最近，然后14和12 又划为别的路线而且又不满足货物总量的限制要求，所以选择19点然后就是25点， 排除24点之后选择了 26点，

12、这四个点的货物总量为吨，在货物总量的限制范围内。 同样总运输时间也不超过4小时。7.第七条路线访问了 0-22-21-20-23-0,是因为在剩下的点中22距离原点最近, 然后接着选择21,然后20,然后再去23点，这四个点的货物总重量为吨，时间为小 时。&第八条路线访问了 0-27-29-28-0,因为剩下的三个点，总货量为吨总路程为 100公里时间为3小时。符合题目的要求。在这八条路线中1、2条路线合用一辆车，3、4条路线合用一辆车，其余的路线 各配用一辆车。详细的数据见表2和表3:详细流程图如下：找离原点最近的点设为 町且该点的访问标志设 为被访问，该点物资需 求量为肌输出该点我次远点Y

13、找到符合条件的点，且不止一个是选择物资质量最大的那个点，标志设为被访问，输岀该点，赋值给打且wewi+w图21, 找离原该点最近的点A,且该点的访问标志设为被访问，该点需求物资重量为 W,输出该点；2, 找点v最近的点，物资重量为wl,且wl+w28-0根据以上路线，计算。表2线路序 号所经站数最近点所用时 （小时）总载重（T）总路程 （公里）131 (3,2)24252 (1,5)54339 (10,2)384310 (14,0)465416 (2,16)706413 (12,9)747422 (21,0)788327(21,13)310029484然后，根据所经历的时间进行划分，确定运输车

14、数量。在工作时间小于4小时的 前提下，最终只需要六辆运输车，第一条线路和第二条线路由一辆车运送，第三条和 第四条线路由一辆车运送，则各运输车具体情况如下（表4）：表3车辆 序列线路所到需求点已行路程+载重空载 路程11+21342561514335+4+4+6+4+6+7+5+23+498710 11 123612+5+5+14+6+6+35161718243418+6+6+6+46131925263721+6+2+8+57222120233621+6+7+8+682729284434+7+5+根据表，运输车重载运费2元/吨公里，空载费用元/公里，计算运输车的费用为 下表（表4）:表4车辆序号

15、线路非空载总 费用（元）空载费用（元）总费用 （元）11+223+4183517465718682220411102151模型求解结果：第一辆车：0t1t34t0 和 OTTTm第二辆车：0t9t8t7t0和第三辆车：Otttt tO第四辆车：OtttttO 第五辆车：Ot tO 第六辆车：0t27t29t28t0 所花费用为：元模型二的建立与求解：此时运输车的种类有4吨，6吨，8吨，运用问题一的方法：首先选择距离远点 最近的点a,再找距离a点最近的点，假设是b,且Ta+Tb=8,那么就继续寻找距离 点b最近的点，并计算物资总重，比较。继续以上步骤，当总重大于8终止。然后比 较总重相加过程中接

16、近且小于4、6、8时的部分总重的差的绝对值，取绝对值最小的。 例如，1线路：最初计算线路是O-,此时的总重量为，但是在到达3时为4, |4-4|10t11t42-04 05 0-6 6吨运输车8吨运输车8吨运输车8吨运输车各条线路详细情况表5:表5线路序 号所经站数最近点m总载重(T)总路程(公里)131 (3,2)82262 (1, 5)423310 (14,0)46466 (3,11)685616 (2,16)1006513 (12,9)7229410根据工作时间小于4小时划分组合，第一条线路和第七条线路由一辆车运送，因 此总共需要六辆运输车，具体情况如下，表6：运输车编 号线路所到需求点

17、已行路程+载重空载路 程11+71329415+4+32+22254789126+4+5+5+5+5+331011122014+6+6+44615141925182814+7+5+5+2+7+551617242627284418+6+10+7+5+10+6613202321222121+7+8+9+6+表6计算费用为表7表7运输车 编号线路（重）非空 载总费用（元）（M空）空 载费用（元）（M）总费 用（元）11+7223126318331044145522662345832428模型求解结果：第-辆车：0 130 和 0290 第二辆车：0t2t5t4t7t8t9 第三辆车：Ot1Ot11t

18、42tO第四辆车：0T6mm第五辆车：0 第六辆车：0- - 所花费用为：2428元路径为图4：图4将问题一和问题二的运输费用描绘柱状图（附件一图5）,相比较之下，可以发 现在路程较短时，问题二所用运输费用较高；路程较长时，问题一所用运输费用较低。六、模型的分析和检验仓库每天要运送的物资在早上出发时间之前已经全到了，没有到的当天就不运 送，这种模型现在已经很成熟，因此采用这种解法应该能够达到减少运费的要求。但是曲于物资调运是一个比较复杂的问题设计到众多的变量，上述模型尚有许多 因素没有考虑在内。比如每辆车送完物资，回来再准备第二趟运送这个过程也要花时 间，这个时间没有考虑到时间范围内。还有像城

19、市交通不平衡等问题，货物分类等问 题。结果和误差分析：理论上总时间算下来是小时和小时，每辆车平均工作4个小时，因此车数算下来 平均是和4039575辆车，在实际情况中4辆车就能送完所有的物资。七.型的推广该模型广泛运用于物资调度问题，大规模的突发性公共事件如sars危机.印度 洋海啸.冰雪灾害、汶川地震等重大问题，在面临这些问题时釆用多目标动态分析，并且结合图表，这样会很大程度上加快解决问题的速度，减少不必要的损失，节省运 输资金。而且突发事件之后往往伴随着大量的应急物资需求，釆用合理的运输方式. 运输路径和最优的应急物资调度方案，及时的将救援物资送达物资需求点，这直接影 响到整个突发性公共事

20、件救援行动的成效。八、模型的评价与优化模型的优点本文此方案能合理的调度物资、分配物资的运输、怎样调度运输费的最低，使供 货商减小运输过程中的费用，加快运输时间，合理的配装物资，合理的选择运输路线, 从而使供货商增大利润，收利最大。模型的缺点此方案没有考虑运输过程中有红绿灯现象.意外的发生.中途遇某事而停车的现 象等，实际上这些现象和状况是存在的，我们却理想化的去调度物资的运输。理论值 和实际值是相差很大的，这方案还需进行实践的验证才能更好的分配.调运物资。问 题二，我们在考虑到运输成本的最低的前提下，没有用到4吨的运输车，如果用4吨 车必须把路线（1）拆成两部分0-13-0, 0t29t0这样

21、没有直接用8吨车一 次运完便宜。参考文献：1 霍亮，空间物流信息系统，中国测绘出版社：2006, 2（6675）2 郑莉，董渊，张瑞，面向对象的程序设计和C+ （第三版），清华大学出版 社：（369-381）3 张磊。车辆调度问题的混合运算。铁路运输与经济，第三十卷第8附件：1.附件一问题一与问题二总费用对比总费用一总费用二运输车的编号2.附件二计算过程中的部分程序： #include #include #include#define max 1000 using namespace std; struct verint x;int y;int num; float weight;bool v

22、isited30:ver v30;int nextl () int k, min=max, tag=0; float w;for (int i=l;i w)k=i;w=vi weight;tag=l;)if (tag)return k;else return 0;int next2(int k,float w)int min=max, tag=0, m, i;for(i=l;i30i+)if (visitedifalse&fabs(vk. xvi. x) + fabs (vk y-vi y)min&w+vi weight二6) minfabs (vk x-vi x)+fabs(vk y-vi y);111= i;tag=l;if (visitedifalse&fdbs(vk. xvi. x)+fabs (vk y-vi y)二二min&w+vi weightvm weight) m二 i;tagFl;if(tag)return m;else return 0;void way () int k;float w;k=next 1 ();w