物资调度问题摘要“运输调度”数学模型是通过运输车运输路线的确定以及运输车调配方案的确定来使运输的花费最小本文首先分析了物资调度中运费、载重量及各站点需求量间相互关系而后，紧抓住总运营费用最小这个目标，找出最短路径，最后完成了每辆运输车的最优调度具体方案问题一： 根据题目及实际经验得出运输车运输物资与其载重量及其行驶的路程成正比例关系， 又运输的价格一定， 再结合题目给出的条件 “运输车重载运费 2 元/ 吨公里” ，其重载运费的单位“元 / 吨公里”给我们的启发于是结合题目给定的表，我们将两个决策变量(载重量，路程)化零为整为一个花费因素来考虑，即从经济的角度来考虑同理我们将多辆车也化零为整，即用一辆“超大运输车”来运输物资根据这样从经济的角度来考虑，于是我们将需求点的需求量乘入需求点的坐标得到一个新的表，即花费经济表，我们再运用数学软件Mathematic作出一个新的坐标，这样可以得到一个花费坐标于是按照从经济花费最少的角度，根据我们所掌握的最短路径及 Dijkstra 算法再结合数学软件 Mathematic ，可求得经济花费坐标上的最短路径具体求法上，采用了Dijkstra 算法结合“最优化原理” ，先保证每个站点的运营费用最小，从而找出所有站点的总运营费用最小，即找出了一条总费用最低的最短路径。
用我们的“超大运输车”走这条最小花费的路线， 我们发现时间这个因素不能满足且计算结果与实际的经验偏差较大于是我们重新分配路线，并且同时满足运输车工作时间这个因素的限制，重新对该方案综合考虑，作出了合理的调整 . 此处我们运用了“化整为零”的思想，将该路线分为八条路径同时也将超大车进行分解，于是派八辆运输车向 29 个需求点运送物资同样的道理我们也将运输车运送物资从经济的角度看，即将运量乘以其速度，又因运输的价格一定，因此便可以将运输车在整体上从经济考虑于是便可以将整体从经济上来考虑将运输最小花费转化从经济方面来考虑比较合理由此可求解出运输车全程的最低费用：29MinS总 MinS去 Min S返 dj j 0石(C C2 C3 L O)i1结合各约束条件求得最低费用为 1980.16 元问题二：由题目知运输车的载重量不同，但由于我们从整体的经济上来考虑运输物资的花费最少问题，因此花费坐标的最短路径仍然不变因此结合运输车工作时间的这个因素， 我们仍用问题一的思路， 运用 “化零为整” ， “化整为零” 的思想来考虑第二问按照这样的的思路我们制定了八条路线，派了七辆运输车来运送物资同样在整体上对问题从经济上来考虑比较合理。
292 Ti +0.5 (5+27+21+34+20+34+18+24 )i12 (T1 T2 T3 T4 L L T30) +0.5 (5 27 21 34 20 34 18 24)结合各约束条件求得最低费用为 1969.66 元，需要 7 辆车关键词：物资调度 最短路线 最优化原理 Dijkstra 算法 0-1 规划一、问题重述1.1. 背景资料与条件某城区有29个物资需求点，需求点的地理坐标和每天物资的需求量见如下表一表 一为原表截取的一部分，原表其余部分见附录一）每天凌晨都要从仓库（第30号站点） 出发将物资运至每个需求点现有已知一种运输车，载重 6吨，运输车平均速度为40 公里/小时，每台车每日工作 4小时，每个需求点需要用10分钟的时间下货运输车 重载运费2元/吨公里，空载费用0.5元/公里；并且街道方向均平行于坐标轴29个需求点物资需求量及地理坐标站点编会需求量T坐标(km) xy站点编p需求量T坐标(km) xy1r 2.50r 3r 2161.5021621.0015170.8061831.5054181.5011174「1.20P 4P 7190.90151250.8508201.4019961.30311211.20225下图为29个需求点的地理坐标示意图:需求点地理坐标252015♦系列110510152025530图一：各需求点地理坐标图1.2. 需要解决的问题问题一：在运输车的载重固定为6吨的情况下，为使运输费用最小，怎样调动运输车（包 括运输车的数量，每台车的运营路线及费用）。
问题二：在运输车的载重分为三类（四吨， 六吨，八吨）的情况下，为使运输费用最小，怎样调动运输车（包括运输车的数量 , 每台车的运营路线及费用）二、问题分析2.1. 问题的重要性分析（社会背景）现代社会经济高速发展，各种信息物资交流频繁，特别是当今，对如何优化物资分配，降低经济成本，时间成本的要求十分迫切研究在使费用最小情况下的物资调度问题，对于满足各地物资需求，优化资源配置，促进经济社会发展具有十分重要的意义2.2. . 有关方面在这个问题上做过的研究[2] 物流配送车辆优化调度问题最早是由学者 Dantzig 和 Ramser 于 1959 年首次 提出的 , 国外一般称之为 vehicle routing problem 或 vehicle scheduling problem.一般以为 , 不考虑时间要求 , 仅根据空间位置安排线路时称为车辆线路安排问题 VRP ;考虑时间要求，安排线路时称为车辆调度问题 VSP目前针对车辆优化调度问题的求解算法可以说是相当丰富 , 根据对这些算法本质的分类研究 , 基本上可以分为精确算法和启发式算法两大类 . 精确算法指可求出最优解的算法 , 主要有分枝定界法、 割平面法、网络流算法和动态规划法 . 精确算法的计算量一般随问题规模的增大而呈指数增长 , 所以多用于规模较小的问题。
启发式算法是指一种基于直观或经验构造的算法 , 目标是在可接受的花费 （ 计算时间、 占用空间等 ） 下得出待解决问题的满意解 , 而不是最优解 . 考虑到VR呢弓虽NP难题,而启发式方法能够比较快地得到满意解 ,这对解决NP难题来说有着不可估量的作用 . 因此大部分文献中专家们主要是在构造各种高质量的启发式算 法2.3. 问题的思路分析仓库物资由运输车进行调运每辆车的工作时间不超过 4 小时，并且每辆车的载重不能超过 6 吨若调运的需求地点已经明确，为了使运费最小，必须用最少的车在允许的工作时间内把需要运送的物资运送到需求地点， 因此选择什么样的调运路线和派遣多少车辆显得尤为重要本论文试图从最短路程和最小花费的角度，建立起满足调运费用最少且调用车辆最少的数学模型，求出仓库派遣的车辆的数量和运送路线问题一的分析：2.3.1. “化零为整”，求最短路本题要求在使总运输费用最小的情况下，安排这 29 个运输点的车辆调度方案先考虑运输车运往各个需求地的总运输最小费用假设从仓库（ 0,0 ）点开始，车先运往i地，此时运费最小；再运往j地，保证从i地到j地的总运费也是最小的；车再运往h地，保证此时地 j 与 h 地的运费仍是最小；即若每两地之间的运输费用都是最小的，那么将所有联通的两个需求地的运费求和仍是最少的运费。
即假设 为 j 地和 i 地的最小运输费用，dj为0-1变量，即两地j与i若联通，则dij为1,若两地不连通，则dj为0在运输车运往个需求点的过程中，总运输最小费用 ?为：29Mg dj ij,j 1 29i1针对 i 地，根据实际情况，其运输费用与该地的需求量及 j 地到 i 地的距离均成正比，故将i地的需求量和地理位置合成一个新量（ x,,y ）,仓库（0）到各个需求点的最短路径即为总运输费用最小的路径2.3.2. 求总最小运输费用在运输车从各个需求点回到仓库的过程中，由于最短路已经确定，因而返回时按每条运输路线上终止需求点到仓库的最短路径， 就可求出整个运输车运送物资与返回全过程的最小费用Min S返 0.5 （C2 cn）即在运输车往返需求点的全过程中的最小费用为29Min S总 Min S去 Min 与 dj j 0.5 6 C2 C Cn）i12.3.3. 化整为零，调度车辆，分配每辆车运输线路根据本文前部分的求解，能求出从仓库到 29 个需求点的最短物资调度线路，则调度车辆要考虑的因素是使总运费最小及使用的车辆尽量少因为在实际物资调度过程中，派出一辆车的固定费用远高于一辆车的行驶费用，因此调度的车辆尽可能少也是优化车辆调度的一个重要考虑因素。
本文在此提供两种方案第一种方案：假设每辆运输车满载，即载重均为6吨，假设运输车丫］在运到第j个运输点时， 将 6 吨货全部卸完， 此时运输到 j 地的物资 m 小于 j 地的需求量 M ， 则 Vi 车返回，Vh车继续往j地送货，满足j地的需求量后继续前进，按此种运输方式运输往各 个需求地的需求量，直至第 29 个需求点即在此过程中，假设有一辆“超级大车” ，载 重了 29 个需求点的全部物资，每到一个需求点，就卸下一部分物资，直至最后一个需求点第二种方案：假设每辆运输车不一定满载，车 V i 在运送完最短路上指定的几个需求点后，即空载返回，车 V h 沿着最短路线，继续运送物资即在此种方案下，每个需求点只有一辆车来运送物资问题二的分析：在第一问已求出最短路的前提下，第二问中提供了三种载重不同的运输车即在这种条件下，能够继续优化调度方案，使载重大的车 （8 吨的车 ），运送离仓库较近的需求地的物资，使这几个需求地的物资总和尽量接近于 8 吨载重越小的车，运往的需求地离仓库越远因为大车的运营成本最高 （大车载重多，因而每公里的运输费用最高 ）思路图：结合本题的实际，为了确保模型求解的准确性和合理性，我们排除了一些位置因素的干扰，提出以下几点假设：3.1 .问题一的假设1 .每辆车载重不同时速度均相等。
2 .忽略运输车加速和制动的速度变化及时间的影响3 .不考虑汽车在红绿灯，堵车，恶劣天气状况时的延误时间4 .每辆车派出的人工成本，装卸货等固定成本忽略不计5 .供应物资的公司能够提供足够多的车辆6 .假设不考虑其他因素，第j个需求点的运费与第j个需求点的需求量及仓库到第j个 需求点的位置均成正比7 .2 .问题二的假设1.本题求解最小费用不考虑实际情况中三种载重不同的运输车的固定成本的差异2、不考虑三种载重不同的运输车速度的不同3.3.本文引用的数据、资料均真实可靠四、符号说明为了便于问题的求解，我们给出以下符号说明： （其他未说明的符号在文中第一次出现时会做详细的说明Vi符号 意义第i辆车ai需求点iXj需求点i和需求点j之间的品EWTi需求点i的物资需求量T i需求量乘位直后需求点i的合成坐标dij0-1变量Pij需求点i和需求点j之间的费用Ci第i辆车的总运输费用T i：注一. 0 当i地与j地连通时. dij 1当i地与j地不连通时注二：Xij xi xj V\ yja，其中xi、y均为题中所给的第i个需求点的横纵坐 标五、模型的建立与求解5.1. 问题一的求解5.1.1 模型一概述Dijkstra 算法[。