物质配送优化设计

1、 物资配送优化研究摘 要物资配送策略的研究对商品经济发展、人力资源增广有正向推进作用。本文采用改进的递阶遗传算法对物资配送方案进行优化设计。问题一，是针对给定物资配送任务，设计最佳送货方案的多旅行商问题。首先，在数据预处理阶段，采用Floyd算法求解出任意两点最小运输时间；然后，在此基础上，以运输里程最短为唯一目标函数，建立01变量优化模型；最后，利用递阶遗传算法以及启发式算法思想对模型进行分析，并采用Matlab软件编写程序（命令及全部计算机源程序见附件1）得到物流中心应同时出动货车，通过指定路径给所有客户点送货，使得运行里程达到最短为。问题二，需要建立每天最佳送货策略的一般数学模型及相应的求解方法。首先，将问题一有效转化为经典车辆调度（VRP）问题，加入指派车辆数目最少，以及客户满意程度最高为目标函数；然后，建立01变量多目标优化模型，并通过功效系数法，将多目标转换为单目标，由此建立每天最佳送货策略的一般数学模型（模型二）；最后，通过改进的递阶遗传算法（见）对模型进行求解。问题三，就问题二的基础上，考虑客户数量较大的情况。将问题二中的一般优化模型通过四叉树分区思想进行调整，建立分区

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

3、量、在任意客户处所需要的卸货时间以及物流中心与各客户以及各客户间的公路里程。根据各客户要求送货车辆到达的时间范围需求解：1. 给当日设计一个最佳的送货车辆安排方案（包括出动车辆的台数以及每一台车辆的具体行驶路径），使总运行里程最短；并给出你们实际使用的软件名称、命令和编写的全部计算机源程序。2. 将数据一般化，为物流中心建立一个每天最佳送货策略的数学模型，并给出求解方法。3. 将问题实际化，考虑此物流中心的客户数量较大，建立模型和求解方法将做哪些调整？二 问题分析2.1 问题分析1 问题综述本文主要对物流中心配送物资方案进行优化研究，主要包括三个问题，且三个问题属于层层递进关系。无论约束与目标如何变化，问题最终需求最佳方案均需含有：当天出动车的数量、行驶路径及总运行里程。整体分析问题，需按（图2）流程进行完成。图2.全文主要思维流程图2 具体问题的分析（1） 问题一的分析问题一是为物流中心具体任务设计最佳配送方案。此问题属于组合优化问题，指派多辆货车从同一地点出发，选择一条路线进行货物配送，并让每一客户点能够准时得到所需货物。此类问题可以采用多旅行商问题建立模型，并基于遗传算法和计算机

4、仿真模拟对模型进行求解，得出最佳方案。图3.关于问题一的分析流程图（2） 问题二的分析问题二是对问题一的深入思考，拟在建立没有具体的数据的一个每天最佳送货策略的一般数学模型。本题可以采用启发式算法思想，在问题一的基础上，加入派遣车辆数量最少以及客户满意程度为目标。并给出求解此模型的求解方法。（3） 问题三的分析问题三属于问题二的深入理解。在问题二的基础上加入客户数量较大这一条件。从现实入手分析，客户数量较大可能导致客户中心拥有货车数量不够、运输时间过长等结果。选择分区思想，考虑选取一辆车对一个区域的所有客户进行运送货物。并且由于客户数量的增加，考虑物流中心的忙碌程度，可以通过降低计算最短路径的精度，提高方案的时间有效率。3 关键问题的理解（1） 关于两客户点之间路径选择的理解由于要使送货的路径达到最小，合理选择路径是解决此类问题的关键。不难发现，表格中任意两点之间的距离并不为最佳（如：从物流中心直接达到第5个客户处需要200km，而从物流中心途径第一客户处，再转向到第5客户处仅需要经过90km，类似的还有从物流中心到第7客户处、从第3客户处到第8客户处）。（见图4）从时间角度观测，从物

5、流中心到第5个客户处需要经过的时间包括：从物流中心到第5节点处的最短路径行驶过程所消耗时间；在第5节点处卸货所花费的时间。（注：此处并不在中间任意客户点卸货，只是由于最短路径的需要而途径中间节点，故不考虑途径任意节点卸货时间）。图4.特殊点路径选择示意图（2） 关于配送费用最小或总运行里程最短的理解根据题目所设所需求解目标为配送费用最小或运行里程最短。文中考虑物资配送过程中，运输过程占有最为昂贵的费用，那么要合理控制运送费用需要尽可能减少运输的里程数。而运送过程受时间限制，一味追求里程的优化可能造成时间的延迟和不充分利用。由于题目假设车辆以平均速度前行，可思考将文章最终目的转换为寻找运送过程时间最短的优化。（3） 关于早到损失、迟到惩罚的理解配送时间是配送方案的重点考虑对象，到达客户点的快慢对物流中心和客户均会造成影响。由于车辆较早到达会造成资金损失，车辆在规定时间以后到达会降低客户对此物流中心的满意程度。于是针对此关键问题，在基本时间约束的条件下，引入客户满意度函数，综合考虑车辆早到以及迟到所造成的影响，得到最佳方案。（4） 顾客数量较大的理解顾客数量较大会对方案造成一定的影响，数量

6、的增加可能导致时间约束的改变。数量的增加对时间的要求更为严重，所以此情况应该考虑适当的算法降低时间复杂度，减少计算的精度，增加计算的速度，从而得到顾客数量较大情况下的优化模型。三 模型假设1 假设货车在接到任务安排后，同时出发，将货物送至各客户点。2 假设不考虑货运途中突发情况及红绿灯等待时间。3 假设物流中心车辆足够，不会出现运输车辆不足的情况。4 假设同一客户点只需要一辆运货车辆进行物资运送。5 假设物流中心所指派的车辆均只运行一次（及一个回路）。四 模型说明符号含义符号含义从i个客户点到第j个客户点的距离任意两点之间的最短路径从第i客户点到第j客户点的最短时间车辆k是否从第i个客户点到第j个客户点车辆k是否对第i个客户点进行送货z运输货物到指定地点的时间消耗总和物流中心派发车辆总和第i个客户所需货物数量Q货车运货数量上限ei第i个客户点配送终止时间wj在客户j处的起始时间货车行驶过程中的平均速度第i个客户处卸货时间 K物流中心派送出车辆的数目第j个节点是否属于第i个区域是否为第i区中距离物流中心最近的客户点五 数据预处理5.1 建立各段最小运输时间模型根据题目中所给数据（表2），

7、根据任意两点之间的距离，绘制出任意两点间的网络赋权图。并建立距离的邻接矩阵，形如：(1)其中表示：从i个客户点到第j个客户点的距离。然后，由关键问题分析，明确任意两点之间的距离并不是任意两点之间的最小路径。下面就任意两点之间的最短距离进行求解：算法选择：其中Floyd算法又称为弗洛伊德算法2，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。要找到各段之间的最小运输时间，可以利用最短路径进行等效转换。对于最短路径的求解，采用Floyd算法较为简单、方便。算法步骤：step 1：从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。step 2：对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短。如果是更新它。step 3：将求解得到的任意两点之间的最短路径写入表格，得出结论。算法结果：利用Matlab软件（见附件1），求解出任意两点之间的最短路径（见表1）：表1.任意两点间的最短路径表格01234567800406075909010013580140065401005075110100260650751001007

8、575753754075010050909012549010010010001007575100590501005010007090756100757590757007010071351107590759070010088010075125100751001000并将上述结果，通过矩阵进行表示，可写作：(2)那么，根据物流中心派发货运车队的车辆的平均速度可以求解到：从第i客户点到达第j客户点的最短时间：(3)根据任意两点之间运输的最短时间，可以得到关于运输过程最短时间的矩阵，形如：(4)将矩阵用表格的形式表示出来，可写作（见表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.8222021.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 problem,MTSP)3：是指M个旅行商从同一个城市(或不同城市)出发,分别走一条旅行路线,使得每个城市有且仅有一个旅行商经过(出发城市除外),且总路程最短。有关TSP的研究在现实问题中有很大的使用价值,诸如交通运输、管道铺设、路线的选择、计算机网络的拓扑设计

《物质配送优化设计》由会员ni****g分享，可在线阅读，更多相关《物质配送优化设计》请在金锄头文库上搜索。