数模论文——露天矿生产的车辆安排

1摘要本文讨论对矿区开采点和加工厂进行物流配送，找出车站位置并求出最佳的车辆安排，是一个典型的车辆路径问题（VRP）。对于第一题，用重心法进行求解。首先通过聚类分析，将开采点分为四个区域，计算每个区域的开采点到所属加工厂的权重之和（权重是距离和产量的乘积），以此作为该加工厂的权重。然后使得车站到四个加工厂的权重之和最小，最终通过Matlab工具箱中的Gatool函数求出车站坐标为（73.95,32.99），几乎与S2重合，因此直接把S2作为车站位置。对于第二题，即对车辆路径进行安排。首先将实际问题用数学规划模型抽象表示出来，然后通过综合运用扫描法和遗传算法相结合，并在第一问的基础上，对于已经分好的四个区域中的某些点做出调整，满足题设的各项条件，得出每个区域各个行车路径。最终得出结论，在保证总路程最小（1085.04㎞）的情况下，至少需要3辆车参与运输便可按时完运输成任务。对于第三题，即通过加大加工厂的日加工量以提高运输效率。首先我们定义了评估运输效率的指标，包括行程利用率β，载重量利用率γ以及运输效率。在不调整平均聚类点的基础上，用第二题的方法计算出车辆路径的安排。得到至少需要3辆车跑完全程的1032.30㎞。最后计算上述的运输效率指标，增加S2，S3加工厂的最大日加工量，平均运输效率相对提高5.47%，明显提高了运输效率。关键字：车辆路径问题（VRP）重心法线性规划扫描法运输效率一、问题重述2某矿区有4个加工厂，65个开采点，（单位：km）。各加工厂每天有最大加工量，各开采点每天的开采量确定。矿区位于一个平原地带，任意两点均可连通，它们之间的距离为几何距离。现将这个矿区从开采点到加工厂的运输任务交给某运输队，运输队首先要根据运输任务大小及加工厂和开采点的分布确定一个车站位置，并建设车站的基础设施。该车队所用运输车型最大载重量100t，行驶速度31km/h。每天上午八点，运输车从车站出发，到达各个开采点并将开采点前一天开采的矿石运往加工厂。晚上八点之前，所有前一天开采的矿石都需要被运往加工厂，运输车则要回到车站进行加油保养等处理。现在，请根据给定的数据，回答以下问题：1.给出车站的位置。2.运输车耗油量很大，因此希望在完成每天的运输任务前提下，使所有运输车行驶的总路程最小。此时至少需要多少车辆参与运输，试给出每辆车的运输路线和工作时间，求出各车辆每天行驶的总距离。3.加大哪些加工点的最大日加工量可以明显提高运输效率。二、模型假设与符号说明模型假设：1.假设汽车在行走过程中，以均匀的速度行驶，且不会出现故障。2.假设汽车在开采点装货的时间和在加工厂卸货的时间可以忽略不计。3.假设汽车掉头，排队的时间可以忽略不计。4.假设每个开采点可被多次运送。符号说明：由于符号较多，这里给出本文中主要的一些符号说明，其余的在后文再作补充，如下所示：1,2,3,4iSi----表示4个加工厂，(,)iixy表示其坐标；jV----表示开采点，用(,)jjxy表示其坐标；j----表示每个开采点每天的开采量；ijd----加工厂到开采点的欧式距离，22()()ijijijdxxyy；0,vxy----车站的位置坐标；3v----车队的行驶速度，已知为31km/h；iQ----每辆运输车的最大载重量，已知为100t；M----加工厂的每天最大加工量，已知为500t；三、问题分析与模型建立本题是一个典型的车辆路径问题（VRP），即对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定问题的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。对于第一题，要找出车站的位置，考虑到题目满足如下条件：1.运输费用只与车站与开采点和加工厂的直线距离有关，不考虑交通状况；2.选择车站时，不考虑所处地理车站位置的地产价格；3.运输费率与运输距离和运输量呈线性关系；4.各开采点的产量已知并且确定。因此我们采用重心法来求车站的位置，重心法是将物流系统中的需求点和资源点看成是分布在某一平面范围内的物流系统，各点的需求量和资源量分别看成是物体的重量，物体系统的重心作为物流网点的最佳设置点，利用求物体系统重心的方法来确定物流网点的位置。具体做法如下：首先通过聚类的方法把每个加工厂需要加工的开采点聚为一类，再通过调整，使得每个加工厂的日加工量小于500t，且每一类开采点从属于一个加工厂，这样就把平面上的点分为四类。然后，计算每个加工厂1,2,3,4iSi的权重i:1niijijjd（1）式中ij表示从属于加工厂iS的开采点的开采量，n表示这一类开采点的个数。最后满足车站0,vxy到四个加工厂的权重之和最小，即满足目标函数4221min()()iiiixxyy（2）求出车站的位置坐标0,vxy。4为了描述第二个问题，设,GVE，012,,,,,nVvvvvs为顶点集，其中0v表示车站，n为开采点数量，S表示加工厂。,|,,ijijijEevvvvVij为边集。1jjn表示每个开采点每天的开采量，共有m辆运输车,每辆车的最大载重量为iQ,每辆车的最大行驶距离为kL。(1km)kR为第k辆车的运行路线，kir表示表示开采点kir在地k条路径的顺序为i,规定0kr=0。(k1,2,,m)kn表示第k辆车经过开采点的个数，0kn表示未使用该车。(1)0(1)01111111min()(3)(4)(5)..(6)(7)|1,2,,,1,2,,(8)kkikiknkkkkikiknkkkinmrrrrkinmjijinrrrrkinrkikkikkikikFeeQeeLstQnnRrrnin其中:式(3)为目标函数,要求配送车辆行驶路径最短，式(4)限制加工厂的总加工量不大于车辆的总运输能力。式(5)式限制每条配送路径长度不大于负责运输的车辆的最大行驶距离（将对时间的限制转化为路程的限制）。式(6)限制每辆车每次的运输量不大于该车的最大载重量。式(7)和式(8)保证每个开采点的货物均被送完且可以有不止一辆车为之服务。这就将该VRP问题用规划模型表示了出来。5针对第三问，涉及到汽车的运输效率问题，本文以车辆实际完成的运输周转量与汽车载总行程中载重量得以充分利用时所能完成的运输周转量之比（见公式12）作为运输效率。下面介绍一些名词指标：行程利用指标或行程利用率β统计期内车辆的载重行程inL（km）与总行程nL(km)的比值in100%nnLL　（9）载重量利用指标1．载重量利用率γ，表示车辆实际完成运输周转量与载重行程额定载重量得以充分利用时所能完成的运输量之比。n(L)P100%100%LinooqPq　（）（10）ΣP—统计期内实际完成运输周转量之和（t·km）；Σpo—统计期内，载重行程额定载重量充分利用所能完成的运输周转量（t·km）；q—车辆的实际载重量（t）qo—车辆的额定载重量（t）运输效率0n100%innqLqL（11）n()100%%innoqLqLβ100（）（12）根据题意，由于对各个加工厂的日加工量不做限制，因此通过自然聚类则对整体散点图重新进行自然聚类（第一问因为有最大加工量的限制，所以聚类之后进行了调整），然后通过计算比较各个指标的关系，找出需要提高产量的加工厂。四、模型的求解与结果分析(1)问题一：车站的位置对于问题一的求解，首先通过聚类分析得出初步分类，再通过调整使得每个区域满足加工厂的日加工量小于500t，得出结果如下图图1：6图1：聚类分区图然后对每个区域从属于加工厂iS的开采点按照（1）式求解加工厂iS的权重i1niijijjd（1）得到各个区域的权重结果以及开采总量如下表：表1：各区域的开采总量和权重区域开采总量500()t权重i一区域470(t)16367二区域353(t)27145三区域493(t)38683四区域451(t)47836.6最后满足车站0,vxy到四个加工厂的权重之和最小，即求解目标函数4221()()iiiixxyy的最小值，通过调用Matlab工具箱中的Gatool函数（见下图），得出车站的位置坐标为73.95x,32.99y。我们求得的车站坐标与S2的距离为0.0194km,即19.4m，发现车站的位置几乎与加工厂2S重合，这7里直接把S2作为车站位置，即车站位置为S2.如图1所示。图2：Matlab工具箱中的Gatool求解结果(2)问题二：车辆路径的规划方案问题二很明显是一个规划问题，求解规划问题的方法有很多种，包括分枝定界法、割平面法、网络流算法以及动态规划算法等方法，但是总的说来，精确性算法是基于严格的数学手段，在可以求解的情况下，其解通常要优于人工智能算法。但由于引入严格的数学方法，计算量一般随问题规模的增大呈指数增长，因而无法避开指数爆炸问题。鉴于此问题的特殊性，我们选择从各区域（各区域的划分见图1）单独考虑，设每个区域的总开采量为i吨，则将区域可分为/100is个小圈，每个圈由每辆车走一遍便可完成装载任务，通过扫描法和遗传算法相结合，类似于破圈，在保证不超过车辆载重上限的情况下，在第一问的基础上，对于已经分好的四个区域中的某些点做出调整，最终得到每个区域各个小圈，且这些小圈的距离和是最小的。如下列各个图表所示（区域路线图表示该区域的行车路线图，上面对应点的数字表示改开采点开采量，表格对应于图中线路相应的数据）。8路线线路总距离（km）线路总货量(100t)A55.569980B26.93464C28.051999D53.860592E75.367297F24.844839S1总加工量470区域总距离264.626图3：一区域的行车路线图表路线线路总距离线路总货量(100t)A64.314695B74.4957100C98.951187S2总加工量477区域总距离237.76149图4：二区域的行车路线图表路线线路总距离线路总货量(100t)A49.938999B33.50986C84.327596D86.597797E26.704998F17.284449S3总加工量439区域总距离298.3624图5：三区域的行车路线图表路线线路总距离线路总货量(100t)A74.28197B77.7358810C28.8221100D48.570677E55.0214489S4总加工量381区域总距离284.4301图6：四区域的行车路线图表通过计算和比较得出，每个区域可以只派一辆车只需要派一辆车即可。因为从车站派一辆车道每个区域完成任务再回到车站，其路程总和不会超过车辆每天能够行使的距离上限，即可以在保证完成任务的前提下，能够回到车站来。结果如下表所示区域车辆数（辆）工作时间（12h）各车辆每天行驶的总距离（km）总路程（km）一18.5363264.6261085.04二17.6697237.761三19.6246298.362四19.1752284.430图7：4辆车的各区域派车情况下面探讨，从整体出发，是否可以减少车辆数，即少于四辆。假设在保证上述最小总路程的情况下，车辆数少于4辆，设总路程为S，因为速度v=31km/h,则每辆车每天最多可行驶t=12h,所以至少需要车辆数为：1085.04N2.923112svt（辆），因此，至少可以需要三辆车。假设在保证路程最小的情况下三辆车能够完成任务。则应该是三辆车分别往一、三、四这三个区域，然后回来完成二区域的任务，则每辆车必须至少是要走S2区域内的一个圈，而区域二内恰好被划分为三个圈。车辆123所行使区域一三四路程（km）264.626298.36228