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