物资配送优化研究
摘 要
物资配送策略的研究对商品经济发展、人力资源增广有正向推进作用。本文采用改进的递阶遗传算法对物资配送方案进行优化设计。
问题一，是针对给定物资配送任务，设计最佳送货方案的多旅行商问题。首先，在数据预处理阶段，采用Floyd算法求解出任意两点最小运输时间；然后，在此基础上，以运输里程最短为唯一目标函数，建立0—1变量优化模型；最后，利用递阶遗传算法以及启发式算法思想对模型进行分析，并采用Matlab软件编写程序（命令及全部计算机源程序见附件1）得到物流中心应同时出动3台货车，通过指定路径（见图5）给所有客户点送货，使得运行里程达到最短为508km。
问题二，需要建立每天最佳送货策略的一般数学模型及相应的求解方法。首先，将问题一有效转化为经典车辆调度（VRP）问题，加入指派车辆数目最少，以及客户满意程度最高为目标函数；然后，建立0—1变量多目标优化模型，并通过功效系数法，将多目标转换为单目标，由此建立每天最佳送货策略的一般数学模型（模型二）；最后，通过改进的递阶遗传算法（见）对模型进行求解。
问题三，就问题二的基础上，考虑客户数量较大的情况。将问题二中的一般优化模型通过四叉树分区思想进行调整，建立分区巡回优化模型。在求解数据精度降低的同时，大大降低求解问题的时间复杂度。最后，利用递阶遗传算法对分区后的TSP模型进行求解，即给出时间复杂度较低的求解方法。
最后，在文章结尾，对模型结果进行合理性分析，均得出计算结果合理的结论。并就文章进行优缺点评价。
关键词：Floyd算法；递阶遗传算法；多旅行商问题；0—1变量优化模型；分区巡回优化模型；时间复杂度。
一 问题重述
1.1 问题的背景
物资配送是物资流通企业按照用户的订货需求及其标准，以最经济的货物进行采购、储存、加工、分炼、配装、运输直到把货物交至用户手中的物资流通活动。并且物资配送具有以下特点[1]（见图1）：
配送是从物流据点至用户的中转型送货形式。配送在物资运输的整个、活动中处于“支线输送”“终端输送”的位置。物资配送特点配送是送货上门式的服务性供应，直接将物资送到用户指定地点配送不单是运送活动，还包括大量的分货，配货、配装等工作配送多定时、定线，距离短，批量小，品种多。
图1.物资配送具备特点示意图
本题主要针对配送运输过程进行优化研究：需要根据当天客户所需物资的重量、物流中心与各客户以及各客户间的公路里程设定一个最佳的送货方案（方案包括当天出动车辆数、行驶路径、当天总运行里程）在满足客户所提出的时间要求下，使配送中心配送费用最小或总运行里程最短。 1.2 问题的提出
现有一批物资配送任务及其要求，其中货车载重量为8T、平均速度为50km/h，送货车辆从物流中心出发，为8个客户配送物资。已知，8个客户所需物资的重量、在任意客户处所需要的卸货时间以及物流中心与各客户以及各客户间的公路里程。根据各客户要求送货车辆到达的时间范围需求解：
1. 给当日设计一个最佳的送货车辆安排方案（包括出动车辆的台数以及每一台车辆的具体行驶路径），使总运行里程最短；并给出你们实际使用的软件名称、命令和编写的全部计算机源程序。
2. 将数据一般化，为物流中心建立一个每天最佳送货策略的数学模型，并给出求解方法。
3. 将问题实际化，考虑此物流中心的客户数量较大，建立模型和求解方法将做哪些调整？
1
二 问题分析
2.1 问题分析 1
问题综述
本文主要对物流中心配送物资方案进行优化研究，主要包括三个问题，且三个问题属于层层递进关系。无论约束与目标如何变化，问题最终需求最佳方案均需含有：当天出动车的数量、行驶路径及总运行里程。整体分析问题，需按（图2）流程进行完成。
数据预处理阶段：求解任意两点之间行驶的最短时间。问题一：根据题目特定情况建立最佳方案优化模型指派车辆数目程度最高意满户客、最少为目标函数问题二：数据一般化，建立改进后最佳方案优化模型考虑分区运算精度提高送、并降低计综合时效问题三：问题实际化，建立推广后最佳方案优化模型 图2.全文主要思维流程图
2 具体问题的分析
（1） 问题一的分析
问题一是为物流中心具体任务设计最佳配送方案。此问题属于组合优化问题，指派多辆货车从同一地点出发，选择一条路线进行货物配送，并让每一客户点能够准时得到所需货物。此类问题可以采用多旅行商问题建立模型，并基于遗传算法和计算机仿真模拟对模型进行求解，得出最佳方案。
根据题目已知条件找到决策变量、约束条件和目标函数合多旅行商问题M建立运行里程最短的优化模型TSP求解此优化模型并找到最优解遗传算根据求解结果分析找到物资配送最佳方案结图3.关于问题一的分析流程图
2
基于法进行求解（2） 问题二的分析
问题二是对问题一的深入思考，拟在建立没有具体的数据的一个每天最佳送货策略的一般数学模型。本题可以采用启发式算法思想，在问题一的基础上，加入派遣车辆数量最少以及客户满意程度为目标。并给出求解此模型的求解方法。 （3） 问题三的分析
问题三属于问题二的深入理解。在问题二的基础上加入客户数量较大这一条件。从现实入手分析，客户数量较大可能导致客户中心拥有货车数量不够、运输时间过长等结果。选择分区思想，考虑选取一辆车对一个区域的所有客户进行运送货物。并且由于客户数量的增加，考虑物流中心的忙碌程度，可以通过降低计算最短路径的精度，提高方案的时间有效率。 3
关键问题的理解
（1） 关于两客户点之间路径选择的理解
由于要使送货的路径达到最小，合理选择路径是解决此类问题的关键。不难发现，表格中任意两点之间的距离并不为最佳（如：从物流中心直接达到第5个客户处需要200km，而从物流中心途径第一客户处，再转向到第5客户处仅需要经过90km，类似的还有从物流中心到第7客户处、从第3客户处到第8客户处）。（见图4） 从时间角度观测，从物流中心到第5个客户处需要经过的时间包括：从物流中心到第5节点处的最短路径行驶过程所消耗时间；在第5节点处卸货所花费的时间。（注：此处并不在中间任意客户点卸货，只是由于最短路径的需要而途径中间节点，故不考虑途径任意节点卸货时间）。
200km5将前行路径转化为50km040km1090km15（不进行卸货，只考虑途中经过）
图4.特殊点路径选择示意图
（2） 关于配送费用最小或总运行里程最短的理解
根据题目所设所需求解目标为配送费用最小或运行里程最短。文中考虑物资配送过程中，运输过程占有最为昂贵的费用，那么要合理控制运送费用需要尽可能减少运输的里程数。而运送过程受时间限制，一味追求里程的优化可能造成时间的延迟和不充分利用。由于题目假设车辆以平均速度前行，可思考将文章最终目的转换为寻找运送过程时间最短的优化。
（3） 关于早到损失、迟到惩罚的理解
配送时间是配送方案的重点考虑对象，到达客户点的快慢对物流中心和客户均会造成影响。由于车辆较早到达会造成资金损失，车辆在规定时间以后到达会降低客户对此
3
物流中心的满意程度。于是针对此关键问题，在基本时间约束的条件下，引入客户满意度函数，综合考虑车辆早到以及迟到所造成的影响，得到最佳方案。 （4） 顾客数量较大的理解
顾客数量较大会对方案造成一定的影响，数量的增加可能导致时间约束的改变。数量的增加对时间的要求更为严重，所以此情况应该考虑适当的算法降低时间复杂度，减少计算的精度，增加计算的速度，从而得到顾客数量较大情况下的优化模型。
三 模型假设
[1] 假设货车在接到任务安排后，同时出发，将货物送至各客户点。 [2] 假设不考虑货运途中突发情况及红绿灯等待时间。 [3] 假设物流中心车辆足够，不会出现运输车辆不足的情况。 [4] 假设同一客户点只需要一辆运货车辆进行物资运送。 [5] 假设物流中心所指派的车辆均只运行一次（及一个回路）。
四 模型说明
符号 含义 从i个客户点到第j个客户点的距离 从第i客户点到第j客户点的最短时间 车辆k是否对第i个客户点进行送货 物流中心派发车辆总和 货车运货数量上限 在客户j处的起始时间 第i个客户处卸货时间 第j个节点是否属于第i个区域 符号 含义 任意两点之间的最短路径 车辆k是否从第i个客户点到第j个客户点 运输货物到指定地点的时间消耗总和 第i个客户所需货物数量 第i个客户点配送终止时间 货车行驶过程中的平均速度 物流中心派送出车辆的数目 是否为第i区中距离物流中心最近的客户点 aij tij dij xijk z qi ei v K yki m Q wj si hij ri 五 数据预处理
5.1 建立各段最小运输时间模型
根据题目中所给数据（表2），根据任意两点之间的距离，绘制出任意两点间的网络赋权图。并建立距离的邻接矩阵，形如：
其中
A??aij?n?n (1)
aij表示：从i个客户点到第j个客户点的距离。
然后，由关键问题分析，明确任意两点之间的距离并不是任意两点之间的最小路径。 下面就任意两点之间的最短距离进行求解：
4