随机车辆路径问题研究探讨

熊沂铖，王 杏，李金龙，秦 芃

（西安航空学院，陕西 西安 710077）

随机车辆路径问题研究探讨

熊沂铖，王 杏，李金龙，秦 芃

（西安航空学院，陕西 西安 710077）

文章阐述了随机车辆路径的起源、特性已经发展的状况，对发展过程中遇到的问题进行归纳总结，指出了研究该问题国内外的进展，介绍了运用算法的低效率以及使用时的限制，提出了对算话的改进措施以及运用实际解决问题的思路和建议。

随机车辆路径问题；组合优化；算法

车辆路径问题（Vehicle routing problem，VRP）在现实生活中有着巨大的经济意义。自从学者从1959年提出有关车辆路径的问题开始，后续的学者对其研究也就成了热门的话题。在研究过程中需要经常研究一个问题就是：对于商品或服务提供商提出的要求，运用车辆将货物运送到分布相对分散的某个区域到顾客手中，规定路经顾客只能一次，如何来制定行车的路线以及车辆的多少，来使得运输成本最低。VRP问题的研究分两个方向：动态与静态，文章主要研究的是动态问题中的SVRP，并对其研究取得的成果进行归纳，为后续学者提供借鉴。

1 SVRP的概念和特征

（1）概念。对SVRP的研究如今最火热的要数如下这些运输问题：需要运送货物给顾客，但是顾客的具体要求每天不同，并以顾客为中心呈现随机分布的现象，由于时间相对仓促和自愿分配的不合理，在信息不全的情况下需要制定出配送方案。举一个现实生活中的例子：银行运钞车对分布在市内的各个银行进行取款的操作，中国邮政对各个市县收取包裹的服务等都属于随机车辆路径问题。

（2）特征。SVRP经过多年的发展对比与传统的VRP存在很多方面的转变，其区别在于：①目标函数。对VRP来说，对时间的把握以及资源的分配都有清晰的了解，目标函数的确定相对简单，需要考虑的问题只是如何使得运输路线最短、成本最低等问题。而对于SVRP，在已有信息的基础之上还得考虑是否会有其他新的信息，所以此时的目标函数是由各种分段函数构成，在构建的过程中相对麻烦。②解的特征。VRP中所有的因素都已经固定不变，没有考虑周围环境的改变，其解的针对范围有限。对于SVRP来说，由于对路径的选取和对信息的重视，其解最大的现实意义也更准确。③问题的求解过程。VRP和SVRP的求解过程都归属于排列与组合的问题，从中找到最优解。

2 SVRP的发展与现状

（1）国外研究现状。国外对求解SVRP的算法有很多，整体的思路还是以既定的信息为基础。该方法的开展分为两个步骤：在得到信息不准确的情况下制定好序列的顺序；在获取准确信息的前提下制定策略。两个步骤的选取的原则基于两点：第一步骤的成本与第二阶段的期望值。对先验序列的分类主要是两种，一种考虑约束条件在内，另一种是把可能性因素考虑进去。约束条件的主要思想是保持稳定，把错误率控制在一定的范围，并且对服务不成功而带来的二次成本忽略不计。可能性因素主要说的是：把第二阶段的期望值以及服务不成功带来的二次成本降到最低的情况下，对第一个步骤的行车路线加以制定。后一种分类求解相对复杂，但是其针对的目标函数的实际结果很有意义。

（2）国内的研究现状。对于我国来说，SVRP的发展才刚刚起步。主要的研究方法是将随机问题通过加权处理之后来作为目标函数，并由此引申出了神经网络的求解方法。运用此方法的核心思想是把运输路线的所有服务

点依次通过某种关系映射到神经网络系统中来反应神经元的情况，当网络状态收缩时，神经元的各种因素也就固定不变，如果能够找到符合这种排列规律的算法要求，那么也就找到解决SVRP问题的最佳方案。

3 目前算法的局限性

上文提到的各种算法都有各自的侧重点也各有特色，但是使用的条件有一定的限制。主要是因为：①有些算法要想达到可以使用的情况需要有一定的经验并对算法进行化简，在求解最解的过程中往往找不到正确的方法需要重新计算。而如果服务的区域相对较大，服务点数量增多，需要运算，浪费太多的时间，效率得不到提升。对于构造出来的收敛函数需要在算法经过加权之后并用一定的约束得到的，而这些加权涉及到的因素相对复杂，只能通过慢慢的测试才能得到，在算法实际运用当中很难见到成效，就像之前说到的神经网络解法。②有些算法需要提前给出初始解，造成麻烦的同时也很难找到最优路径的解法。就拿模拟退火算法来说，先是通过整体找到算法的思路，在逐步找寻最优解的两个步骤，显然这种算法很费时，如果只采用第一个步骤又不能很好的反映整体特征。

4 结语

文章研究的SVRP对国内外的学者来说都开始进入起步，还有许多重大的项目与问题留待进一步的商榷和探索。主要体现在：①研究的现象主要集中在VRPSD，对于复杂的动态随机性的问题研究不是很多。而日常经常能碰到的问题大多都属于不确定VRP，确定性VRP都是通过不确定VRP简化得到的。现如今对SVRP的研究水平只能对小区域的随机车辆路径问题加以解答，对于较大区域的效果不是很好。要想解决大区域的SVRP问题，运用的主要方法还是通过计算机的大型运算功能，更加有效率的算法暂时还没有研究出来。所以需要把领域的概念引用进来，根据领域的不同特征结合算法从而找到最优解。②启发式算法的研究需要进一步的加强，来到达设计并解决问题的目标。启发式的运用在现实生活中相对简单，无法应对在动态因素改变的情况下对调度的控制作用，所以需要研发更加快捷的运算方法。如果通过人工的手段对SVRP进行运算，耗费的时间相对较长，在引入计算机的前提下，编辑智能化的软件将数据进行调试，放低对精度的精确才能有效将运算的速度加以提升，此种做好具有现实意义。若是转向对复杂性的挖掘，也能从另一个方面提升响应速度的灵敏性。③加深对开路式VRP的研究。相比于传统VRP算法中车辆需要重回起始点进行运输，开路式极大的缩短了运输的路程。该方法运用的原理是将物流系统中的存储地点进行集中式管理，而且在最近几年开始逐步发展，也取得了一定的成果。由于该种方法的高效性，闭环式VRP可以将此优点进行结合，发展成一种更加便捷的途径。④如何把取得的项目进展成果转化到实际的运用当中，更好的为交通运输的发展和社会的便利贡献出一份力量也是需要探讨的问题。

Exploration on Stochastic Vehicle Routing Problem

XIONG Yi-cheng，WANG Xing，LI Jin-long，QIN Peng
（Xi'an Aviation College，Xi'an，Shaanxi 710077，China）

This paper expounds the origin and characteristics of stochastic vehicle routing and summarizes the problems encountered in the development，points out the research progress both at home and abroad，and introduces low efficiency of the algorithm and constraints，and puts forward improvement measures of calculating words and ideas and suggestions of solving the problems.

stochastic vehicle routing problem；combinatorial optimization；algorithm

U491

A

2095-980X（2016）10-0071-02

2016-09-13

熊沂铖（1988-），男，陕西勉县人，硕士研究生，助教，主要研究方向：发动机工作原理。