物流配送线路优化Matlab算法研究［摘要］“最后一公里”的配送问题属于物流配送车辆路径优化问题。针对物流配送线路选取过程中所缺乏的可嵌入系统的简易优化算法的缺陷，提出了基于逐点调整法、双点交换法的综合算法。该方法通过对单个节点进行位置调整和任意调整两个节点位置的综合运用，不仅可取得较优的配送线路，且在算法的可推广应用方面具备较强优势。［关键词］线路优化；最短路线；综合算法；Matlab［D0l］10.13939/j.cnki.zgsc.2016.32.0411引言“最后一公里”的派件问题属于物流配送车辆路径优化问题。物流配送车辆路径优化问题(VehicleRoutingProblem,VRP)是以最少车辆数、最小车辆总行程完成货物的配送任务，从而达到成本最小或时间最短等目标。[1]它最早是由Dantizg和Ramser[2]于1959年首次提出的。由于VRP问题是一个NP难问题，采用精确优化算法对其进行求解，计算量与问题的规模呈指数增加关系，因此当规模增大时，计算机计算复杂度相当大，实际中其应用范围比较有限。[3]在国外，ViniciusW.C.Morais,GeraldoR.Mateus，ThiagoF.Noronha(2014)[4]发现大多数的作品在研究VRPCD问题时是基于禁忌搜索，而他们并没有局限于禁忌搜索而是只探索可行的空间解决方案。由于没有计算努力花在不可行解决方案上的时间，从而使得运算结果更有效。FatmaPinarGoksal,IsmailKaraoglan和FulyaAltiparmak(2013)[5]提出了一种基于离散粒子群优化(PSO)和变邻域搜索算法的混合搜索算法来解决同时派件和收件的车辆路径问题，其具有很好的优化能力，但是，当节点较多时，算法运行却是一个相当耗费时间的过程。MohamedCheikh,MustaphaRatli,OmarMkaouar,BassemJarboui(2015)[6]提出了一种基于四个不同的领域结构的变邻域搜索算法来找到合适的旅行路线。邻域结构1和3旨在最小化旅行路线和时间，邻域结构2和4旨在最小化时间。结果表明，此算法给出的运算结果质量较高。在国内，陈韦志(2007)[7]从考虑最短的运输路径与最少的运输费用两个角度建立车辆路径规划(VRP)模型。构造出最大------最小蚁群算法，避免了传统蚁群算法易陷入局部最优解、求解速度较慢的缺陷，体现了改进蚁群算法的相对优越性。但是，其研究的VRP对于时间上的要求并不是很高，而且所考虑的客户点规模并不是特别大。张红艳(2005)[8]建立了考虑线路安排的物流配送方案模型，并提出了求解该问题的一种自适应遗传算法，模拟结果表明改进的遗传算法明显增强了群体演化的质量，提高了算法的收敛速度，求得了问题的优良解。许国平、叶效锋、鲍立威(2004)[9]将模拟退火和遗传算法相结合的进化算法用于解决车辆路径问题。避免了遗传算法中存在的早熟收敛问题，增强了算法的全局收敛性，并且提高了算法的收敛速度王华东、李巍(2012)[10]指出传统算法搜索最优路线时间长，难以找到最优配送路线，导致物流配送成本高。针对此缺陷，提出了一种动态的惯性权值o非线性变化PS粒子群算法，提高了物流配送路径优动态的化成功率。针对物流派件线路选取过程中所缺乏的简易优化方法的缺陷，同时满足调度需求越快越好的要求，在此提出了基于逐点调整法和双点交换法的综合算法。该算法不仅简单，优化效果较好，而且稳定性较强。在录入一定的业务量、车辆数量和区域信息后，会快速地规划出合理的派送路线，应急有效比传统的凭人工经验选择路线要好很多，且在算法的可推广应用方面具备较强优势。2相关算法概述目前比较常用的简单而有效的算法主要有：穷举法、改进穷举法、随机穷举法、二次逐边修正法、逐点调整法、两点交换法和综合法。2.1穷举法在Matlab中通过perms命令可以生成指定向量的所有可能的排列，而每一组排列可对应一个可能的派件方案，在所有这些排列中一定存在一组排列的总派件里程是最短的，从而我们就可以找到最优派件方案。2.2改进穷举法在Matlab中通过perms命令至多可以生成向量长度不超过9的全排列，因此当节点个数多于9个节点时利用perms命令将无法直接获取到最优解。届时考虑到对于节点进行合并后再利用穷举法。节点的合并原则如下：定义1在一个城区交通网络布局下派件节点集合X中的两个节点a和b称为可合并的，如果X中不存在任何节...