车辆路径优化方法研究

车辆路径优化方法研究摘要:车辆路径优化是汽车运输企业提高车辆运营效益,实现物流科学化的重要途径。近年来,车辆路径优化方法一直是国内外研究的热点与难点问题之一。因此,对国内外车辆路径优化方法进行比较分析,改进车辆的优化调度方案,对提高企业核心竞争力具有重要意义。关键词:车辆路径;物流;优化方法;配送一、国外企业车辆路径优化方法概述车辆路径优化问题(VRP)是物流企业关注的热点问题。1959年,著名学者Dantzig和Ramser提出解决企业车辆调度的基本问题可描述为:有一个车场拥有最大载重量为p的车辆171辆,车辆满油行驶的最长时间为71,现有17项运输任务需要完成,已知任务j(j=1,…,17)的货运量Q,决策者要选择满足货运需求且费用最小的车辆路线。国外企业开发的车辆优化调度系统大多采用的是集分割模型,直接考虑可行解集合,并在此基础上进行优化。模型的解法大多采用动态规划算法,需要考虑相当庞大的状态数,只能精确求解规模非常小的问题。而状态空间松弛技术的应用大大减少了状态数,使动态规划算法的性能得到了很大改善。为了实现求解的并行化,按角度和路径重心对原问题的空间进行分割,再用禁忌搜索结合模拟退火对子问题求解。动态车辆路径优化问题的规模较大,不仅追求质量和计算时间,而且要求信息处理简单、具有弹性。从求解策略来看,可分为重新优化策略和局部优化策略两大类。重新优化策略实际上就是动态问题的静态求解,即一旦接收到实时信息,就从头开始寻找最优车辆路径,该方法最多只能解决十个需求的小规模问题。局域优化策略是根据事先已知的信息制定初始路径,当接收到实时信息后,用局域方法改进初始路径。局域优化策略获得的路径计划可能劣于重新优化策略,但能节约大量的计算,更适用于实际的企业车辆路径规划。随着现代物流的发展,许多配送企业的车辆路径规划又面临着对随机信息进行处理的问题。企业随机车辆路径规划针对背景是:每天要访问的客户或节点的数量和位置是固定的,但每个客户每天的需求是不同的,并各自满足一定的可能性分布或随机分布,限于时间或资源的关系,决策者无法等到获得所有信息才作决策。如城市超市的配送车辆每天固定时间对服务区域各分销店的配送服务(每辆配送车所运的货物种类数量不能超过一定限额,这就构成了能力约束)。这类配送企业开发的随机车辆路径规划方法主要采用了机会约束规划模型和惩罚费用模型。机会约束规划模型允许决策在一定程度上不满足约束条件,但该决策应保证约束条件成立的概率不小于某一置信水平。惩罚费用模型的基本思想是,当车辆的实际行驶时间超出车辆每日总行驶时间的上界时,产生惩罚费用,目标是使运输费用与惩罚费用之和最小,以此来解决企业配送车辆的路径优化问题。二、国内车辆路径优化方法概述国内企业车辆路径优化方法的研究起步较晚,西南交通大学的郭耀煌教授从1989年起对该类问题展开了一系列研究,并出版了该领域的第一部专著《车辆优化调度》。企业开发实用系统时针对我国城市建设发展中道路交通阻塞问题,构建具有可变行驶时间的动态车辆调度模型,设计动态环境下车辆路径优化的导向局域搜索算法,建立车辆执行运输任务过程的仿真模型,实现了根据交通网实际情况实时优化车辆路径。另外,GPS、GIS和GSM技术的发展使得提供实时的信息成为可能,这些高新技术在调度方法中的应用对企业实时调度车辆,减少运营成本有重要的作用。此外,由于认识事物的模糊性,车辆路径优化可能具有一定的模糊特征。例如,车辆配送从一个节点到另一个节点大约费时二十分钟(而不是一个准确时间)等,致使企业运输决策者经常会面临模糊信息条件下的车辆路径优化问题。企业开发调度系统时,一般假设可获得的供应量和需求量是模糊的,而各位置间的旅行时间以及相关费用是精确的,每一个顾客都有一个偏好或期望的开始服务时间,都有其特定的起点和终点,由此引入模糊线性规划原则处理模糊输入信息条件下的转运问题。认为模糊转运问题的目标不总是费用最小化,而是参照用模糊集表示的“合理的费用”来安排运输,将每一个新的顾客需求分配给其中一辆车,并重新设计该车辆路径。引入伪出发点和新的聚类判定规则,将聚类和排序有机结合,有效地处理了全局采样和局部搜索之间的矛盾,给出基于可能性分布的2-OPT算法和基于需求上界的2-OPT算法,并用模糊模拟技术进行实验。引入模糊预约时间的概念和决策者主观偏好的概念,提出了解决模糊需求信息条件下车辆调度的一种基于模糊可能性的混合遗传算法,并在最小化车辆使用数与车辆行驶距离的目标下,通过随机模拟研究了决策者的主观偏好对最终决策目标的影响。这种方法目前己经投放市场的路径软件有:武汉测绘科技大学奥发公司的“商业送配货地理信息系统”和北大方正的“路径规划系统”。三、国内外车辆路径优化方法存在的问题尽管国内外对车辆路径优化方法的研究已取得了很多成果,但在企业实际运用中仍存在一些问题,主要表现在以下几个方面:1.现实中企业的需求各异甚至相互冲突。比如,顾客满意度的提高和运作成本的降低就可能是一对矛盾,随着顾客满意度的提高会带来营业收入的增加。当顾客满意度达到一定水平之后,由提高服务满意度带来的营业收入便不能与随之增加的运营成本平衡,导致企业总收入下降。企业运输决策中需要考虑多目标的情况,对服务水平,运营成本,运输时间,运输距离等各方面的因素进行权衡,以达到利润最大化的目标。因此,单目标车辆路径优化方法难以解决实际问题,为了满足企业的实际需要,应该加强多目标车辆路径优化方法的研究,解决多目标车辆调度过程中计算复杂的难题。2.企业车辆配送实际面临的不确定性因素很多且交叉影响,而目前企业开发的车辆调度系统一般只考虑由一个或几个方面(如需求、旅行时间、顾客的不确定性)引起的车辆路径优化问题,未综合考虑车辆、客户、路况等各种不确定性因素,同时对不确定性的研究也只限于单一的随机或模糊形式的不确定性,没有考虑更复杂的粗糙情形或者双重不确定性等形式,即使建立了多因素模型,算法的收敛性和收敛速度问题也难以解决。3.由于车辆路径优化也要由人参与,难免受到决策者主观偏好的影响,而目前对模糊VRP的研究只有寥寥数项,所以基于模糊信息的车辆调度系统开发应该是一个重要研究方向。4.目前只能对各种车辆路径优化方法进行经验评价,很难确定算法的优劣,这给企业选择合适的方法、开发实用系统带来了很大的困难。因此,需要建立统一的算法评估体系,主要包括车辆路径优化算法的复杂性分析和收敛性分析(定界分析),通过算法的复杂性分析,可以为评定算法寻优效率提供依据,为设计更快的算法提供理论依据;收敛性分析为评定算法搜索能力提供衡量标准,可以知道该算法可得到的最好和最差解的范围,为企业选择满足所求问题的搜索精度要求的算法提供依据。四、结束语国内外车辆路径优化方法给我们的启示:1.注重对车辆路径优化问题的描述,建立与实际情况相符合的模型主要体现在配送中心的数量、配送车辆的类型、货物类型以及目标的多样性上,主要包括运输路径最短、成本最少、准时、尽可能少的车辆等方面。2.充分考虑我国道路交通条件的实际及对车辆路径优化问题的影响,设计能够根据道路上的实时交通流信息计算旅行时间进而求得最佳路线的算法,达到节约运输时间,减少交通条件引起的配送延迟问题,提高顾客满意度的目标,保证系统开发的可用性。3.加强模糊信息条件下车辆路径优化方法的研究将模糊理论引入车辆路径优化系统开发当中,运用模糊集概念和模糊评判理论,设计处理模糊特征的多因素影响过程,通过综合考虑车辆行驶费用最小化和顾客满意度最大化两方面的问题,以求有效解决车辆路径优化问题中车辆运行商利益和顾客利益难以兼顾的问题。4.研究快速的车辆路径优化模型算法在一些车辆路径优化规模比较大的场合,现有方法不能满足对车辆进行实时动态调整的需求,鉴于精确算法通常需要较长的计算时间,应用人工智能技术,设计具有较高响应速度的人工智能算法成为重要的研究方向。5.考虑运用新的数理方法解决车辆路径优化建模和算法问题研究支持向量机理论、网格技术、结构方程模型、仿真方法等在本领域的运用:如利用仿真系统得到某策略下系统的性能,从而对不同的策略进行评价:还可以改变系统的一些参数来进行物流系统各参数的灵敏性分析,寻求系统改进途径和最佳运行参数,为企业物流配送系统的决策提供参考。参考文献:[1]DesrosiersJ,LaporteG,SauveM,SoumisF.VehicleRoutingWithFullLoad[J].Computers&OperationsResearch,1988,15(3):219～226.[2]Mosheiov,Gur.VehicleRoutingwithPick-upandDelivery:Tour-partitioningHeuristics[J].Computer&IndustrialEngineering,1998,34(3):669～684.[3]郭耀煌,李军,车辆优化调度问题的研究现状评述。西南交通大学学报,1995,30(4):76～382.[4]谢秉磊,郭耀煌,郭强,动态车辆路径问题现状与展望,系统工程理论方法应用,2002,11(2):116～120.(作者通讯地址:武警工程学院陕西西安710086)