《物资调运问题》由会员分享，可在线阅读，更多相关《物资调运问题（18页珍藏版）》请在金锄头文库上搜索。
1、物资调运问题摘 要如今物资调度问题普遍存在于生活的每个角落，利用有效的方法解决该问题会给我们的工作生产带来许多便利，也会带来可观的利益。本文在确定了物资需求地点和每个需求地点的需求量提下，用什么样的调度方案使所需的运费最少，来达到题目的要求。本文主要从最省费用的角度来考虑问题的，这样我们不妨把每个地点都放到直角坐标系中，每个地点都有自己的固定坐标，设发货点为坐标原点，每条街道都与坐标轴平行，更具题目的要求我们可以得出：每两个点之间的距离就是两点横坐标之差的绝对值和纵坐标之差的绝对值之和。如A（x,y）,B(x,y)两点，他们之间的运输距离为S=，而且必须满足每辆车运输时间的条件，所以对于问题一
2、，由于要求费用最省，根据图形每辆车从原点出发到最近的点送货，在满足各项条件的前提下，用多目标动态规划求解。并可以得出需要用6辆6吨的车，最省费用为2151.00元。对于问题二，与问题一类似，只是具体要求不同，最后求得所花费用为2428元。将问题一和问题二的运输费用描绘柱状图（附录一图4），相比较之下，可以发现在路程较短时，问题二所用运输费用较高；路程较长时，问题一所用运输费用较低。关键词：物资调度 最优化 图形求解 多目标动态规划一、 问题重述1.1. 背景资料与条件某城区有29个物资需求点，需求点的地理坐标和每天物资的需求量见下表。每天凌晨都要从仓库（第30号站点）出发将物资运至每个需求点。
3、现有一种载重 6吨的运输车，运输车平均速度为40公里小时，每台车每日工作 4小时，每个需求点需要用10分钟的时间下货，运输车重载运费2元/吨公里，空载费用0.5元/公里；并且假定街道方向均平行于坐标轴。1.2.需要解决的问题1. 为了使得总运营费用最少，运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）？2.如果有载重量为4吨，6吨，8吨的三种运输车，又应该如何调度，失踪营运费用最少？二、问题分析2.1.问题的重要性分析（社会背景）近年来，大规模的突发性公共事件如sars危机、印度洋海啸、冰雪灾害、汶川地震等在世界各国频有发生，这些突发事件造成的巨大损失，给人们留下了难以忘怀
4、的惨痛记忆。现代社会正处在高速发展的过程中，与此同时，人口、资源、环境、公共卫生等方面的问题日益严重，这导致各类突发事件爆发的频率加快，影响范围扩大，危害程度加剧。我国当前正处在突发性公共事件高发时期，随着城镇化进程的加快，这种形势还在加剧，因此研究应急物流和应急物资调度问题具有非常重要的现实意义。突发事件之后往往伴随着大量的应急物资需求，采用合理的运输方式、运输路径和最优的应急物资调度方案，及时的将救援物资送达物资需求点，这直接影响到整个突发性公共事件救援行动的成效。2.2.问题的思路分析问题一：从仓库开出一辆车，到任意未配送的需求点，然后将这辆车开往最近的未服务的需求点范围之内的邻居，并使
5、运输时间小于4小时，各车所运物资的总重量不超过6T。继续上述指派，直到各点总重量超过6T，或者运输时间大于4小时。最后车辆返回仓库，记录得到的可行行程（即路线）。对另一辆车重复上述安排，直到没有未服务的需求点。对得到的可行的行程安排解中的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的车辆的顺序，最小化运输总距离。得到可行解的行程安排解后退出。问题二：车辆有4吨、6吨、8吨，同理运输时间小于4小时，各线路所运物资最大不能超过8T。在计算过程中，确定具体使用哪种类型的运输车。对得到的可行的行程安排解中的每一条路径，计算所花费用，最后与问题一比较。表1给出了各个需求点的需求量，为了完成任
6、务，在工作时间范围内，每辆运输车可以承担两条甚至更多的线路。表中给出了需求点序号，编号，需求物资量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.002017122.70146272.0021
7、13131.80129281.002420141.801012292.102516150.60714300.0000将表1的30个点绘在坐标系上。图1三、基本假设1.3.1.模型假设1. 运输车在运行的过程中无红绿灯现象也没有意外的发生，即不花时间2. 运输车中途不停3. 运输车回到仓库的配货时间不计4. 每个物资点只停留一次5. 运输车沿街道方向均平行于坐标轴6. 运输车在中途除了送货之外没有别的时间耽搁7. 本文所用的资料和数据均真实可靠四、符号说明2.4.1.模型符号说明站点的物资需求量（i为站点编号，为需求点的坐标）M载运输车运输物资的总重费用M空运输车空载的总重费用M运输车运输物资的
8、总费用N运输车运输物资的总次数K运输车的总辆量第j个运输车的次数1运输车在站点编号为i的需求点所送物资时为10运输车在站点编号为i的需求点未送物资时为0第m条线路选择站点编号为i的需求点是最远点时为1第m条线路选择站点编号为i的需求点是最近点时为0五、模型的建立与求解3.5.1.模型一的建立与求解：本模型考虑用多目标动态规划求解。由于问题中只要求给出一个合理的方案，故只要满足条件运输车的工作时间上限是4个小时以及每条路线的最大载重量不大于6T即可，本模型中追加两个目标路程最短和车辆最少。可以通过以下方法实现：每一个行程的第一个需求点是距离仓库最近的未服务的需求点。用这种方法，即可得到一组运行路
9、线，总的运行公里数，以及总费用。整理作图，即可得到最优化结果。本模型中以满足需求的费用最小的车辆行驶路径,且使用尽量少的运输车，即，具体操作：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，是因为在剩下的未服务送货点中
10、，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最近的点，而且三个点的总
11、货重量为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又划为别的路线而
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:详
13、细流程图如下： 图21,找离原该点最近的点A，且该点的访问标志设为被访问，该点需求物资重量为w，输出该点；2，找点v最近的点，物资重量为w1，且w1+w6，当其不成立时找次远点；3，找到符合条件的点，且不止一个时选择物资重量最重的那个点，访问标志设为被反问，并输出该点，赋值给v，且w=w+w1；执行Y。找不到符合条件的点时执行N。用该算法得到的各路线为：（1）01340（2）（3）09870（4）（5）（6）（7）（8）根据以上路线，计算。图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.8788327（21,13）35.11002916.933443.15484然后，根据所经历的时间进行划分，确定运输车数量。在工作时间小于4小时的前提下，最终只需要六辆运输车，第一条线路和第二条线路由一辆车运送，第三条和第四条线路由一辆车运送，则各运输车具体情况如下(表4)： 表3车辆序列线路所到需求点已行路程+载重空载路程11+21342561514335+5.24+2.74+1.26+5.
