物流配送线路优化Matlab算法研究

刘亚娟+木仁

[摘 要]“最后一公里”的配送问题属于物流配送车辆路径优化问题。针对物流配送线路选取过程中所缺乏的可嵌入系统的简易优化算法的缺陷，提出了基于逐点调整法、双点交换法的综合算法。该方法通过对单个节点进行位置调整和任意调整两个节点位置的综合运用，不仅可取得较优的配送线路，且在算法的可推广应用方面具备较强优势。

[关键词]线路优化；最短路线；综合算法；Matlab

[DOI]10.13939/j.cnki.zgsc.2016.32.041

1 引 言

“最后一公里”的派件问题属于物流配送车辆路径优化问题。物流配送车辆路径优化问题（Vehicle Routing Problem，VRP）是以最少车辆数、最小车辆总行程完成货物的配送任务，从而达到成本最小或时间最短等目标。[1]它最早是由Dantizg和Ramser[2]于1959年首次提出的。由于VRP问题是一个NP难问题，采用精确优化算法对其进行求解，计算量与问题的规模呈指数增加关系，因此当规模增大时，计算机计算复杂度相当大，实际中其应用范围比较有限。[3]

在国外，Vinicius W.C.Morais，Geraldo R.Mateus，Thiago F.Noronha（2014）[4]发现大多数的作品在研究VRPCD问题时是基于禁忌搜索，而他们并没有局限于禁忌搜索，而是只探索可行的空间解决方案。由于没有计算努力花在不可行解决方案上的时间，从而使得运算结果更有效。Fatma Pinar Goksal，Ismail Karaoglan和Fulya Altiparmak（2013）[5]提出了一种基于离散粒子群优化（PSO）和变邻域搜索算法的混合搜索算法来解决同时派件和收件的车辆路径问题，其具有很好的优化能力，但是，当节点较多时，算法运行却是一个相当耗费时间的过程。Mohamed Cheikh，Mustapha Ratli，Omar Mkaouar，Bassem Jarboui（2015）[6]提出了一种基于四个不同的领域结构的变邻域搜索算法来找到合适的旅行路线。邻域结构1和3旨在最小化旅行路线和时间，邻域结构2和4旨在最小化时间。结果表明，此算法给出的运算结果质量较高。

在国内，陈韦志（2007）[7]从考虑最短的运输路径与最少的运输费用两个角度建立车辆路径规划（VRP）模型。构造出最大——最小蚁群算法，避免了传统蚁群算法易陷入局部最优解、求解速度较慢的缺陷，体现了改进蚁群算法的相对优越性。但是，其研究的VRP对于时间上的要求并不是很高，而且所考虑的客户点规模并不是特别大。张红艳（2005）[8]建立了考虑线路安排的物流配送方案模型，并提出了求解该问题的一种自适应遗传算法，模拟结果表明改进的遗传算法明显增强了群体演化的质量，提高了算法的收敛速度，求得了问题的优良解。许国平、叶效锋、鲍立威（2004）[9]将模拟退火和遗传算法相结合的进化算法用于解决车辆路径问题。避免了遗传算法中存在的早熟收敛问题，增强了算法的全局收敛性，并且提高了算法的收敛速度。王华东、李巍（2012）[10]指出传统算法搜索最优路线时间长，难以找到最优配送路线，导致物流配送成本高。针对此缺陷，提出了一种动态的惯性权值ω非线性变化PS粒子群算法，提高了物流配送路径优动态的化成功率。

针对物流派件线路选取过程中所缺乏的简易优化方法的缺陷，同时满足调度需求越快越好的要求，在此提出了基于逐点调整法和双点交换法的综合算法。该算法不仅简单，优化效果较好，而且稳定性较强。在录入一定的业务量、车辆数量和区域信息后，会快速地规划出合理的派送路线，应急有效，比传统的凭人工经验选择路线要好很多，且在算法的可推广应用方面具备较强优势。

2 相关算法概述

目前比较常用的简单而有效的算法主要有：穷举法、改进穷举法、随机穷举法、二次逐边修正法、逐点调整法、两点交换法和综合法。

2.1 穷举法

在Matlab中通过perms命令可以生成指定向量的所有可能的排列，而每一组排列可对应一个可能的派件方案，在所有这些排列中一定存在一组排列的总派件里程是最短的，从而我们就可以找到最优派件方案。

2.2 改进穷举法

在Matlab中通过perms命令至多可以生成向量长度不超过9的全排列，因此当节点个数多于9个节点时利用perms命令将无法直接获取到最优解。届时考虑到对于节点进行合并后再利用穷举法。节点的合并原则如下：

定义1 在一个城区交通网络布局下派件节点集合X中的两个节点a和b称为可合并的，如果X中不存在任何节点与a或b之间的距离小于2倍的a与b之间的距离。

改进穷举法基本思想：为了增加利用穷举法派件过程中的节点个数，利用上述定义可对节点进行合并，在未合并节点及合并节点集合个数总和不超过9，且每个合并节点集合中的节点个数不超过10的前提下继续使用穷举法生成一个优化派件顺序。具体步骤如下：

（a）利用穷举法生成节点及合并节点集合的优化派件顺序，在这里我们从所有合并节点集合中任意选择一个节点并与未合并节点构成集合后穷举获得派件顺序。

（b）根据在（a）中所获得的优化派件顺序确定临近派件顺序并确定合并节点集合中的节点派件顺序。

2.3 随机穷举法

在利用穷举法或改进穷举法依然无法计算获得优化派件顺序时，可通过Maltab中的随机实验来获取较优结果。其基本思想是利用Matlab中随机排列生成命令randperm生成一个随机排列，并通过不断的优胜劣汰的方式获取到较优派件顺序，当实验次数充分多时就可以获取到较优派件结果。

2.4 二次逐边修正法

当节点个数较多时利用随机穷举法所获取到的结果与最优派件结果之间的差距依然巨大，甚至都没有基于临近派件原则（每次总找到最近的未派件节点进行派件）获取到了结果好。为了获取到更好的派件结果，需要对随机穷举法获取到的每次派件结果进行进一步的优化，目前较常用的优化方法是二次逐边修正法。

2.5 逐点调整法

通过利用二次逐边法优化出的派件结果不仅受初始派件顺序的影响，同时也与各节点的交换顺序存在较强关系。在很多情况下利用二次逐边修正法所能够优化的里程并不多，因此为了更进一步进行优化，考虑对每个节点进行逐个调整。算法基本思路就是对已有派件线路中的各节点进行位置调整，如果节点调整位置后总派件距离得到改进，则新位置将替代原位置并进行不断的循环改进，直到对所有节点的位置调整均不能改进总派送距离为止。

2.6 两点交换法

鉴于二次逐边修正法仅能调整邻近节点位置的缺陷，利用穷举法可调整任意两个节点的位置，从而优化结果能够更加全面。

2.7 综合法

通过交替使用逐点调整法及两点交换法，可不断对派件线路进行优化，进一步为了获取到更优的派件结果，可添加节点插入及交换随机因子，以保证穷举的全面性。

3 结 论

“最后一公里”的派件问题实际上归属于行遍性问题，即派件员派件时，从配送中心出发，经过他所派送范围内的所有客户节点，然后返回配送中心。相关学者虽然提出了蚁群算法、遗传算法、模拟退火等方法，但是此类算法迭代速度过缓、耗费时间长，可推广性不强。针对此类缺陷，本文提出了基于逐点调整法和双点交换法的综合算法。采用此种方法进行优化，大大增强了获取最优解的可能性。同时，既解决了现有算法存在的缺陷，又大大提高了派件速度，具有很强的现实应用价值。

参考文献：

[1]袁庆达，闫昱，周再玲.TabuSearch算法在优化配送路线问题中的应用[J].计算机工程，2001（11）：86-89.

[2]Dantzig G B，Ramser J H.The Truck Dispatching Problem[J].Management Science，1959，6（1）：80-91.

[3]程明辉，齐名军.基于粒子群算法的物流配送路径优化问题研究[J].中国外资，2008（8）：254.

[4]Morais V W C，Mateus G R，Noronha T F.Iterated Local Search Heuristics for the Vehicle Routing Problem with Cross-Docking[J].Expert Systems with Applications，2014，41（16）.

[5]Goksal F P，Karaoglan I，Altiparmak F.A Hybrid Discrete Particle Swarm Optimization for Vehicle Routing Problem with Simultaneous Pickup and Delivery[J].Computers & Industrial Engineering，2013，65（1）： 39-53.

[6]Cheikh M，Ratli M，Mkaouar O，et al.A Variable Neighborhood Search Algorithm for the Vehicle Routing Problem with Multiple Trips[J].Electronic Notes in Discrete Mathematics，2015，47： 277-284.

[7]陈韦志.配送中心的运输路径优化研究[D].武汉：武汉理工大学，2007.

[8]张红艳.关于物流配送中心车辆路径优化问题的研究[D].大连：东北财经大学，2005.

[9]许国平，叶效锋，鲍立威.基于模拟退火遗传算法的车辆路径问题研究[J].工业控制计算机，2004（6）：49-50.

[10]王华东，李巍.粒子群算法的物流配送路径优化研究[J].计算机仿真，2012（5）：243-246.