数学建模优化

1、 物资配送优化研究摘 要物资配送策略的研究对商品经济发展、人力资源增广有正向推进作用。本文采用改进的递阶遗传算法对物资配送方案进行优化设计。问题一，是针对给定物资配送任务，设计最佳送货方案的多旅行商问题。首先，在数据预处理阶段，采用Floyd算法求解出任意两点最小运输时间；然后，在此基础上，以运输里程最短为唯一目标函数，建立01变量优化模型；最后，利用递阶遗传算法以及启发式算法思想对模型进行分析，并采用Matlab软件编写程序（命令及全部计算机源程序见附件1）得到物流中心应同时出动3台货车，通过指定路径（见图5）给所有客户点送货，使得运行里程达到最短为508km。问题二，需要建立每天最佳送货策

2、略的一般数学模型及相应的求解方法。首先，将问题一有效转化为经典车辆调度（VRP）问题，加入指派车辆数目最少，以及客户满意程度最高为目标函数；然后，建立01变量多目标优化模型，并通过功效系数法，将多目标转换为单目标，由此建立每天最佳送货策略的一般数学模型（模型二）；最后，通过改进的递阶遗传算法（见）对模型进行求解。问题三，就问题二的基础上，考虑客户数量较大的情况。将问题二中的一般优化模型通过四叉树分区思想进行调整，建立分区巡回优化模型。在求解数据精度降低的同时，大大降低求解问题的时间复杂度。最后，利用递阶遗传算法对分区后的TSP模型进行求解，即给出时间复杂度较低的求解方法。最后，在文章结尾，对模

3、型结果进行合理性分析，均得出计算结果合理的结论。并就文章进行优缺点评价。关键词：Floyd算法；递阶遗传算法；多旅行商问题；01变量优化模型；分区巡回优化模型；时间复杂度。一 问题重述1.1 问题的背景物资配送是物资流通企业按照用户的订货需求及其标准，以最经济的货物进行采购、储存、加工、分炼、配装、运输直到把货物交至用户手中的物资流通活动。并且物资配送具有以下特点1（见图1）：图1.物资配送具备特点示意图本题主要针对配送运输过程进行优化研究：需要根据当天客户所需物资的重量、物流中心与各客户以及各客户间的公路里程设定一个最佳的送货方案（方案包括当天出动车辆数、行驶路径、当天总运行里程）在满足客户

4、所提出的时间要求下，使配送中心配送费用最小或总运行里程最短。1.2 问题的提出现有一批物资配送任务及其要求，其中货车载重量为8T、平均速度为50km/h，送货车辆从物流中心出发，为8个客户配送物资。已知，8个客户所需物资的重量、在任意客户处所需要的卸货时间以及物流中心与各客户以及各客户间的公路里程。根据各客户要求送货车辆到达的时间范围需求解：1. 给当日设计一个最佳的送货车辆安排方案（包括出动车辆的台数以及每一台车辆的具体行驶路径），使总运行里程最短；并给出你们实际使用的软件名称、命令和编写的全部计算机源程序。2. 将数据一般化，为物流中心建立一个每天最佳送货策略的数学模型，并给出求解方法。3

5、. 将问题实际化，考虑此物流中心的客户数量较大，建立模型和求解方法将做哪些调整？二 问题分析2.1 问题分析1 问题综述本文主要对物流中心配送物资方案进行优化研究，主要包括三个问题，且三个问题属于层层递进关系。无论约束与目标如何变化，问题最终需求最佳方案均需含有：当天出动车的数量、行驶路径及总运行里程。整体分析问题，需按（图2）流程进行完成。图2.全文主要思维流程图2 具体问题的分析（1） 问题一的分析问题一是为物流中心具体任务设计最佳配送方案。此问题属于组合优化问题，指派多辆货车从同一地点出发，选择一条路线进行货物配送，并让每一客户点能够准时得到所需货物。此类问题可以采用多旅行商问题建立模型

6、，并基于遗传算法和计算机仿真模拟对模型进行求解，得出最佳方案。图3.关于问题一的分析流程图（2） 问题二的分析问题二是对问题一的深入思考，拟在建立没有具体的数据的一个每天最佳送货策略的一般数学模型。本题可以采用启发式算法思想，在问题一的基础上，加入派遣车辆数量最少以及客户满意程度为目标。并给出求解此模型的求解方法。（3） 问题三的分析问题三属于问题二的深入理解。在问题二的基础上加入客户数量较大这一条件。从现实入手分析，客户数量较大可能导致客户中心拥有货车数量不够、运输时间过长等结果。选择分区思想，考虑选取一辆车对一个区域的所有客户进行运送货物。并且由于客户数量的增加，考虑物流中心的忙碌程度，可

7、以通过降低计算最短路径的精度，提高方案的时间有效率。3 关键问题的理解（1） 关于两客户点之间路径选择的理解由于要使送货的路径达到最小，合理选择路径是解决此类问题的关键。不难发现，表格中任意两点之间的距离并不为最佳（如：从物流中心直接达到第5个客户处需要200km，而从物流中心途径第一客户处，再转向到第5客户处仅需要经过90km，类似的还有从物流中心到第7客户处、从第3客户处到第8客户处）。（见图4）从时间角度观测，从物流中心到第5个客户处需要经过的时间包括：从物流中心到第5节点处的最短路径行驶过程所消耗时间；在第5节点处卸货所花费的时间。（注：此处并不在中间任意客户点卸货，只是由于最短路径的

8、需要而途径中间节点，故不考虑途径任意节点卸货时间）。图4.特殊点路径选择示意图（2） 关于配送费用最小或总运行里程最短的理解根据题目所设所需求解目标为配送费用最小或运行里程最短。文中考虑物资配送过程中，运输过程占有最为昂贵的费用，那么要合理控制运送费用需要尽可能减少运输的里程数。而运送过程受时间限制，一味追求里程的优化可能造成时间的延迟和不充分利用。由于题目假设车辆以平均速度前行，可思考将文章最终目的转换为寻找运送过程时间最短的优化。（3） 关于早到损失、迟到惩罚的理解配送时间是配送方案的重点考虑对象，到达客户点的快慢对物流中心和客户均会造成影响。由于车辆较早到达会造成资金损失，车辆在规定时间

9、以后到达会降低客户对此物流中心的满意程度。于是针对此关键问题，在基本时间约束的条件下，引入客户满意度函数，综合考虑车辆早到以及迟到所造成的影响，得到最佳方案。（4） 顾客数量较大的理解顾客数量较大会对方案造成一定的影响，数量的增加可能导致时间约束的改变。数量的增加对时间的要求更为严重，所以此情况应该考虑适当的算法降低时间复杂度，减少计算的精度，增加计算的速度，从而得到顾客数量较大情况下的优化模型。三 模型假设1 假设货车在接到任务安排后，同时出发，将货物送至各客户点。2 假设不考虑货运途中突发情况及红绿灯等待时间。3 假设物流中心车辆足够，不会出现运输车辆不足的情况。4 假设同一客户点只需要一

10、辆运货车辆进行物资运送。5 假设物流中心所指派的车辆均只运行一次（及一个回路）。四 模型说明符号含义符号含义从i个客户点到第j个客户点的距离任意两点之间的最短路径从第i客户点到第j客户点的最短时间车辆k是否从第i个客户点到第j个客户点车辆k是否对第i个客户点进行送货z运输货物到指定地点的时间消耗总和物流中心派发车辆总和第i个客户所需货物数量Q货车运货数量上限ei第i个客户点配送终止时间wj在客户j处的起始时间货车行驶过程中的平均速度第i个客户处卸货时间 K物流中心派送出车辆的数目第j个节点是否属于第i个区域是否为第i区中距离物流中心最近的客户点五 数据预处理5.1 建立各段最小运输时间模型根据

11、题目中所给数据（表2），根据任意两点之间的距离，绘制出任意两点间的网络赋权图。并建立距离的邻接矩阵，形如：其中表示：从i个客户点到第j个客户点的距离。然后，由关键问题分析，明确任意两点之间的距离并不是任意两点之间的最小路径。下面就任意两点之间的最短距离进行求解：算法选择：其中Floyd算法又称为弗洛伊德算法2，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。要找到各段之间的最小运输时间，可以利用最短路径进行等效转换。对于最短路径的求解，采用Floyd算法较为简单、方便。算法步骤：step 1：从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。s

12、tep 2：对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短。如果是更新它。step 3：将求解得到的任意两点之间的最短路径写入表格，得出结论。算法结果：利用Matlab软件（见附件1），求解出任意两点之间的最短路径（见表1）：表1.任意两点间的最短路径表格012345678004060759090100135801400654010050751101002606507510010075757537540750100509090125490100100100010075751005905010050100070907561007575907570070100713

13、51107590759070010088010075125100751001000并将上述结果，通过矩阵进行表示，可写作：那么，根据物流中心派发货运车队的车辆的平均速度可以求解到：从第i客户点到达第j客户点的最短时间：根据任意两点之间运输的最短时间，可以得到关于运输过程最短时间的矩阵，形如：将矩阵用表格的形式表示出来，可写作（见表2）：表2.运输过程中各点之间行驶的最小时间（单位：小时）012345678000.81.21.51.81.822.71.610.801.30.8211.52.2221.21.301.5221.51.51.531.50.81.50211.81.82.541.82220

14、21.51.5251.8121201.41.81.5621.51.51.81.51.401.4272.72.21.51.81.51.81.40281.621.52.521.5220六 模型建立与求解6.3 运行里程最短的优化模型（问题一）6.1.1 多旅行商（MTSP）问题旅行商问题(traveling salesman problem,TSP)：是一个典型的组合优化难题,它在许多领域都有着广泛的应用,已被证明属于NP问题。所谓TSP是指有N个城市,要求旅行商到达每个城市各一次,且仅一次,并回到起点,且要求旅行路线最短。多旅行商问题(multiple traveling salesman pr

15、oblem,MTSP)3：是指M个旅行商从同一个城市(或不同城市)出发,分别走一条旅行路线,使得每个城市有且仅有一个旅行商经过(出发城市除外),且总路程最短。有关TSP的研究在现实问题中有很大的使用价值,诸如交通运输、管道铺设、路线的选择、计算机网络的拓扑设计、邮递员送信等,都可抽象成TSP或MTSP。6.1.2 多旅行商问题选择理由解决此类组合优化问题并不容易，再得到物资配送任务之后，物流中心会派出公司的车辆分别对不同地点客户进行送货。那么，物流公司将指派一定数量的车（从客户所需求的货物总量与每辆车载重量进行比较，可以确定指派车辆不止一辆），可以看作多旅行商问题中的旅行商。而根据数据预处理阶

16、段所做工作，将要求问题等效转换为每个客户点有且仅有一辆指派车辆经过，且所消耗时间最短，此为一组组合优化问题，故求解问题选择使用多旅行商问题。6.1.3 物资配送过程时间最短的优化模型建立1. 决策变量定义车辆k是否从第i个客户点到第j个客户点为：并且，定义车辆k是否对第i个客户点进行送货：2. 目标函数根据题目要求，需要通过设计一个较为优化的方案，使得配送中心的配送费用最小或总运行里程最短。问题一意在追求总运行里程最短。那么，在公司所使用的运输货车的平均速度相等的情况，考虑行驶里程最小转化为花费时间最短：其中，z表示：公司指派的m辆车，运输货物到指定地点的时间消耗。3. 约束条件从运输的一次性

17、考虑，每个客户点只需要有物流中心的配送车辆运送货物一次即可，而从物流中心发出的车辆的总和应该为m：任意一个送货点有且仅有一个起点和终点与之相连，形如：第k辆车运送给客户货物的总量不应该超过该车载重总量，即是：当然，客户对货物接收的时间有较强的要求，需要在一定时间范围将货物送达。现定义：第i个客户点配送终止时间（从物流中心到该点时间与在该点卸货时间的总和）ei，以及在客户j处的起始时间wj，若存在xijk=1，则有：H是支路消去约束5消去构成不完整路线的解，应该满足：综上所述建立优化模型为：6.1.4 物资配送过程时间最短的优化模型求解6.2 数据一般化最佳方案优化模型（问题二）6.2.1 模型

18、准备从物流中心角度进行分析，在得到客户订购的任务后，物流中心将根据客户需求时间、客户需求数量以及运送点距离等因素对物流中心已有的货运车队进行派遣，属于物资配送车辆调度问题(VRP问题)。采用多旅行商问题思路可以解决本小问，文章为追求形式多样性，将采用不同于问题一的思想，对本小问进行模型建立与求解。由于此题为第三问的基础，考虑客户数量并不会太多。于是假设：每辆车只出发一次且每辆车只到达一个节点。6.2.2 模型建立物流服务中心有m辆相同的车辆，给n个应急点提供货物。令G=(V，E)为一无向图，其中为顶点集，为边集。顶点为物流服务中心，为客户点的集合。以及车辆集1. 决策变量定义车辆k是否从第i个

19、客户点到第j个客户点为决策变量：2. 目标函数目标一：与问题一类似，首先将行驶过程总花费时间最短定义为目标函数：目标二：另外，由于此问题要考虑所花费的费用最小，需要要求公司所派遣的车辆数目达到最小，即是：将此目标进行转化，可将派遣车辆数目最少等价为车辆所装载货物数量无限接近车辆的在载重。亦是车辆准载量与实际载货量差值综合最小：目标三：要让车辆安排合理，需要提高客户对配送过程的满意程度。若设定M1（M2）分别表示车辆在期望时间之前（之后）到达，单位时间处以的惩罚值。那么，客户满意程度最大可表示为：采用多目标转化为单目标思想对三个目标综合为一个目标：3. 约束条件公司派出运货车辆的数目应该不超过公

20、司储备车辆的总数：根据关键问题分析中的结论，将不卸货的节点看作路径的一部分，那么需要满足每个应急点有且仅有一辆车进行访问。即是：现认为客户数量并不太多，考虑每辆车只出发一次，则有：当然，从物流中心出发的车辆必须保证最后能够回到物流中心，于是，需要满足：接着，还需要保证第i个客户点的需求量不超过车辆的载重量：跟问题一类似，还是需要有时间的约束以及第k辆车载重量不能超过准重量，即是满足问题一中（11）、（12）式。最后，还需要满足整数约束，也就是：综上所述，建立问题二的数据一般化最佳方案优化模型：6.2.3 模型求解针对此类多旅行商问题的求解过程是相当复杂的，被认为是NP问题。而选择算法也是相对困

21、难的。遗传算法是：模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化的概率搜索算法，是解决此类问题的必要选择。1. 遗传算法设计（1） 遗传算法思想遗传算法46的基本思想是将求解问题的一些可行解进行编码，这些已编码的解即被当作群体中的个体(染色体)；个体对环境适应能力的评价函数就是问题的目标函数；模拟遗传学中的变异、复制来设计遗传算子，用优胜劣汰的自然选择法则来指导学习和确定搜索方向。对由个体组成的群体进行演化来产生具有更高平均适应值和更好个体的群体，经过若干代后，选出适应能力最好的个体，它就是问题的最优解或近似最优解。（2） 算法步骤Step1：在一定编码方案下，随机产生一个初始

22、种群；Step2：用相应的解码方法，将编码后的个体转化成问题空间的决策变量，并求得个体的适应值。Step3：按照个体适应性的大小，从种群中选出适应值较大的一些个体构成交配池。Step4：由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代种群。Step5：反复执行步骤24，直至满足收敛判据为止。（3） 算法实现6.3 客户数量较多情况下建立分区运输优化模型（问题三）由于问题实际化可能发生客户数量较多的情况，根据模型一、二方法求解可能导致物流中心周转降低的情况。就这情况而言，可以考虑将客户点进行分区处理，由一辆货车运送一个区域。分区原理：采用四叉树栅格索引的方法，选取地理上相对集中的

23、客户点，构造候选区位；使候选区位内各客户点的需求量综合接近车辆的运送能力，对候选区位进行优化并确定结果分区。分区方法（见图5）。图5.客户数量较多情况下的分区模拟图分区运输优化模型：此优化模型将距离物流中心最近的客户点作为重点考虑对象，于是规定01决策变量为：与此同时，将第j个结点是否被分配到第i个区域也设定为决策变量：分区后要追求的目标是：所有区域货车行驶的里程总和达到最小，也就是：其中，表示：本区域中距离物流中心最近的客户点到物流中心的距离；表示：节点j到本分区距离物流中心最近的客户点的距离。当然，根据分区原理，文中设定将一辆车指派到一个区域进行货物运输。那么，每一分区的需求总量均不超过运

24、输容量：另外，任意客户点j都只能被选中一次，且只属于一个区域：而且，分区i和结点j之间还应满足关系：根据分区原理，建立关于分区的优化模型，如：分区后，确定巡回路径：在不同的分区中，采用TSP问题的解决算法在各分区确定巡回路线；对求得解进行适度性优化。根据TSP问题准则，以及模型一、二的确立可以建立分区后巡回路径的优化模型，形如：6.3.1 分区优化模型求解分区算法选择理由：旅行商问题是一个NP难题，其时间复杂度为。而遗传算法的时间复杂度为（n为城市的个数）。当客户数量（n）相当大时，时间复杂度增加较多。文章采用四叉树的方法进行分区处理，将物资配送作为空间点线关系进行处理，具有简洁快速的技术优势

25、，大大降低了计算过程的时间复杂度。分区过程的算法思想及步骤：四叉树将地理空间进行不断四等分，成的网格。Step1：高斯平面坐标系建立Step2：四叉树的生成，检索客户点中最大的绝对值。作为建立四叉树的最大网格边长。Step3：确定候选分区：（分区基准：四叉树网格包含的客户点需求总量等于或接近车辆载重）选择距离供给点最远端的四叉树网格，延逆时针方向进行网格中需求点的扩充。扩充条件：如果本网格的总需求量等于车辆载重，则不进行扩充；小于，则延逆时针方向以最近原则选择相邻一定等级的网格内的需求点扩充，使得配送区位的总需求量等于或接近车辆载重。所选择的需求点从原从属网格中剔除，将无需求点的网格剔除，形成

26、非四叉树形式的配送区位。Step4：重复Step3使每个需求点仅一次被选入一个配送区位。Step5：将以上操作确定的配送区位代入分区配送的数学模型中，进行目标函数求解。如果求解值小于原目标函数求解值，则该配送区位设定为新的候选区位。循环上述操作，经过限定次数计算，进行配送区位优化。七 模型检验7.1 模型结果合理性检验检验模型计算结果的合理性，即，检验模型结果是否符合常识。1. 一般情况下，TSP问题总运行时间高于mTSP问题总运行时间；但耗费的成本则不同，TSP问题的运行成本较低于mTSP问题。对于模型一，本文通过建立利用改进的递阶遗传算法，求得 。通过比较：计算得到的结果比较符合实际，即，本文建立的模型一和使用的方法是合理的。2. 问题二则是多目标多旅行商问题，通过将多目标转化为单目标，运用模型一中的数据，同样利用改进的递阶遗传算法，求得 。通过分析发现，结果影响不大，比较符合实际。说明模型