车辆路径问题研究综述

吴姝雨

摘 要：作为现代物流领域的研究前沿，车辆路径问题的求解算法及应用领域一直是学者研究的重点。本文在研读大量文献的基础上介绍了遗传算法的研究现状及其应用情况，并对车辆路径优化在生鲜农产品配送上的应用进行了简单的综述。

关键词：车辆路径问题；遗传算法；生鲜农场品；研究综述

一、引言

车辆路径问题最早在60年代被提出，Dantzig和Ramser首次在交通领域提出该问题就立即引起了社会的广泛关注。发展到现如今，车辆路径问题的应用已经跳出了交通领域，在别的很多领域被使用，如：通讯、工业管理、航空等。

二、遗传算法

1.遗传算法简介

达尔文的生物进化论自被提出以来就一直被科学家们广泛应用到各个领域。60年代时美国科学家结合进化论，提出了遗传算法。跟大自然中生物优胜劣汰的进化过程类似，遗传算法在计算过程中模拟了自然界各种群由简单到复杂，由低级到高级的进化过程，不断进化种群，直至使种群达到包含最优解或接近最优解的状态。

2.遗传算法研究现状

遗传算法作为一种群体随机搜索方法，在车辆路径问题研究中运用很多。很多国内外的研究学者对基础的遗传算法进行了改良，以期达到求解不同约束条件下车辆路径优化问题的目的。通过研究撰写遗传算法的文献发现，研究学者们分别用各种改进遗传算法对车辆路径问题进行了求解，如：免疫遗传算法、小生境遗传算法，以及遗传算法与爬山算法、禁忌搜索算法、蚁群算法相结合的混合算法。

将基础的遗传算法与改进的遗传算法进行对比仿真实验，可以发现经过改良的遗传算法，其各方面能力都更优。罗勇等为了求解更优的物流配送路线，就采用了针对性改进的遗传算法。通过研究发现，改良后的算法不仅收敛速度变快，而且全方位寻优的能力也有很大提高。由此可见改进的遗传算法是能更好的处理物流配送路径问题。基础的遗传算法有容易陷入局部最优和早熟的缺点，为了解决这个问题，周艳聪等设计了基于小生境技术的改进遗传算法，还在改进的遗传算法的基础上求解了物流配送路径的优化问题。不仅如此，还通过对物流配送过程的研究，建立了不带时间窗约束的物流配送优化模型。大规模车场的车辆路径问题是车辆路径优化问题中的一个难点，一直是学者们研究的重点。李波等引入了双层模糊聚类方法，针对基础的遗传算法进行了改进，得到了求解该问题的基本框架。通过随机的实验算例证明，所提出的方法是有效可行的。

三、车辆路径问题在生鲜农产品配送中的应用

对近年来，针对生鲜农产品配送路径问题的研究已经越来越多，人们对绿色食品的质量要求不断提高，是导致该问题备受关注的根本原因。容易腐烂变质，存放不易是大多数生鲜农产品的特点。而在整个销售过程中，生鲜农产品需要经历从农户手中到经销商手中这样一个配送过程，尽可能在配送过程中选择合适的路径，节约时间，保证生鲜农产品的质量，从而保证农户、经销商、消费者的利益就变得越来越重要。

为了保证生鲜农产品的质量、安全，生鲜农产品配送过程中的时效性一直是各个学者研究的关注点，大多数相关文献的模型建立都是以配送时间最短和配送成本最低为目标。王红玲等学者的研究考虑了生鲜农产品的特点构建了以生鲜农产品在途时间最短、配送成本最低为优化目标的农产品配送模型，并采用经过改进后的粒子群算法进行求解。由于生鲜农产品的时效性强的特点，对带时间窗的车辆路径问题的研究也相当多。邱荣祖等在分析了农产品的物流配送模式的基础上，建立了有时限的物流配送路径优化模型，并应用GIS于禁忌搜索算法集成技术进行求解。文献中还选用了具体的数据进行了实验的验证，进行了初步的应用研究。

生鲜农产品作为日常生活的必须品，在运输的过程中需要考虑时效性和顾客的满意度情况。顾客的满意度是一个软时间窗，可以应用模糊隶属度函数来表示。邵举平等考虑了生鲜农产品时效性强的特点，以顾客满意度和配送总成本为目标，建立了路径优化模型，选用符合研究问题的智能算法，并用改算法对算例进行验证。生鲜农产品的配送大多具有三层配送网络结构，为了提高在此网络配送中的配送效率，曹倩等以成本最小和顾客满意度最大为目标建立了数学模型，而且利用惩罚函数对模型进行约束，针对遗传算法进行改进，并使用改进后的遗传算法对模型进行求解。

除了考虑生鲜农产品的时效性特点以外，一些学者还从很多其他方面对其进行了研究。生鲜农产品的易腐特性就是学者们比较关注的而一个点。吕俊杰等针对生鲜农产品在冷链物流中配送的问题进行了研究。该研究是站在物流配送商的角度，考虑冷链配送车辆的成本，建立了物流配送车辆的路径优化模型，采用MATLAB工具和启发式算法对算例进行验证，验证的结果说明考虑冷链配送车辆成本的路径模型能找到更优的配送路径。除了易腐性以外，生鲜农产品还具有市场需求的模糊不确定性、时变性。朱佳翔等考虑了农产品的这些性质，以“最早出发”与“多供应点选择”为目标建立了优化模型。还以现实案例进行了模型的验证分析，结果表明所建立的生鲜农产品配送模型具有可行性和科学性。食品安全问题是人们关注的焦点，针对这个问题张瑜等从生鲜食品物流配送模式出发，以上海联华超市股份有限公司为例，根据联华超市现有的生鲜食品物流配送模式，分析其问题，从供应链角度提出优化模式及实施建议。

四、总结

通过对上述车辆路径问题的研究，本文得出以下几点总结：（1）国内外对于车辆路径问题的研究比较多，但是对于动态车辆路径问题的研究仍属于起步阶段。求解车辆路径问题单单使用一种算法不容易得出最优解，可以考虑多种算法想结合的方式求解问题。（2）针对动态车辆路径问题的研究，虽然已有很多文献考虑了时变网络下车辆速度等因素的变化，但大多数没有结合实际交通路网，尽管引入了实时路线更新的概念，但未考虑车辆在行驶过程中经过的每条路段和每个路网节点。（3）生鲜农产品运输的车辆路径研究大多是在静态网络的状态下进行的，可见，目前对生鲜农产品运输的车辆路径问题研究主要局限在静态网络中，时变网络条件下的VRP研究比较少。针对上述情况，结合实际的城市配送体系，本文认为可以研究生鲜农产品在时变网络条件下的车辆运输路径问题。

参考文献：

[1]Dantzig G B. Ramser J H. The truck dispatching problem[J]. Management science， 1959， 6（1）： 80-91.

[2]罗勇，陈治亚.基于改进遗传算法的物流配送路径优化[J].系统工程，2012，08：118-122.

[3]周艳聪，孙晓晨，余伟翔.基于改进遗传算法的物流配送路径优化研究[J].计算机工程与科学，2012，10：118-122.

[4]李波，邱红艳.基于双层模糊聚类的多车场车辆路径遗传算法[J].计算机工程与应用，2014，05：261-264+270.

[5]王红玲，郑纲，何剑锋.基于改进粒子群算法的生鲜农产品配送路径优化研究[J].安徽农业科学，2010，（31）.

[6]邱荣祖，钟聪儿，修晓虎.基于GIS和禁忌搜索集成技术的农产品物流配送路径优化[J].数学的实践与认识，2011，（10）.

[7]邵举平，曹倩，沈敏燕，孙延安.生鲜农产品配送中带时窗的VRP模型与算法[J].工业工程与管理，2015，01：122-127+134.

[8]曹倩，邵举平，孙延安.基于改进遗传算法的生鲜农产品多目标配送路径优化[J].工业工程，2015，01：71-76.

[9]吕俊杰，孙双双.基于鲜活农产品冷链物流配送的车辆路径优化研究[J].广东农业科学，2013，09：178-181.

[10]朱佳翔，江涛涛，蔡建飞，田刚，毛良虎.考虑市场时变需求的生鲜农产品配送模糊多目标决策研究[J].软科学，2015，11：135-139.

[11]张瑜，陈华艳.生鲜食品物流配送模式的问题及优化研究--以上海联华超市股份有限公司为例[J].中国商论，2015，11：81-84.