车辆路线问题自1959年提出以来,一直是网络优化问题中最基本的问题之一,由于其应用的广泛性和经济上的重大价值,一直受到国内外学者的广泛关注。车辆路线问题可以描述如下:

设有一个起始站,共有  辆货车,车辆容量为 ,有 位顾客,每位顾客的需求量为 。车辆从场站出发对客户进行配送服务最后返回场站,要求所有顾客都被配送,每位顾客一次配送完成,且不能违反车辆容量的限制,目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。

2  车辆路径问题的难点与解决方法

2.1  车辆路径问题的难点

对于解决车辆路径问题有一个难题,那就是NP完全问题,NP问题是世界七大数学难题之一。NP问题是指可以在多项式的时间里猜出一个解的问题,简单来说就是多项式复杂程度的非确定性问题。NP问题通常有个算法,它不可以直接告诉你答案是什么,但是能告诉你,某个可能的结果是正确的还是错误的。这个能告诉你“猜算”的答案正确与否的算法,如果可以在多项式时间内算出来,就可以叫做多项式非确定性问题。但如果这个问题的所有可能性答案,都是能够在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题。 

    完全多项式非确定性问题可以用穷举法得到答案,一个一个的检验下去,最终能够得到结果。但是这样算法的复杂程度是指数关系,因此计算的时间随着问题的复杂程度成指数的增长,很快便变得不可以计算了。而车辆路径问题就属于一种NP问题。

2.2  车辆路径问题的方法

综合过去有关车辆路线问题的求解方法,可以分为精确算法与启发式解法,其中精密算法有分支界限法、分支切割法、集合涵盖法等;启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚁群算法等。1995年,Fisher曾经将求解车辆路线问题的算法分成三个阶段。第一阶段是从1960年到1970年,属于简单启发式方式,包括各种局部改善启发式算法和贪婪法等;第二阶段是从1970年到1980年,属于一种以数学规划为主的启发式解法,包括指派法、集合分割法和集合涵盖法;第三阶段是1990年开始至今,属于较新的方法,包括利用严谨启发式方法、人工智能方法等 。 

精确算法顾名思义就是可以求出最优解的方法。它是一种基于严格要求的数学手段,但是随着规模的扩大,算法也不可避免的变得复杂。所以精确算法只能求解小规模的车辆路径问题。

启发式算法是一个基于直观或经验构造的算法,在可以接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计。

由于车辆路径问题是NP-hard问题,很难用精确算发求解,启发式算法是求解车辆运输问题的最主要的方法,多年来许多学者对车辆运输问题进行了研究,提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法 。

    下面就来介绍一下解决车辆路径问题的方法。

2.2.1  分支界限法

分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就可以一次性产生其所有儿子结点。在这些儿子结点中,导致非可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一个结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。源'自:优尔`!论~文'网www.youerw.com

上一篇:C#+Sqlserver在线五子棋的设计+源代码
下一篇:基于C语言的字符串处理研究

电子商务环境下鲜活农产...

互联网时代背景下對以农...

交通运输网路的最短路算法的优劣讨论

交通运输网络的最短路线问题

ARM单片机+CAN总线工程车辆...

android智能小车及蓝牙车辆状态监控APP开发

企业员工的信息安全意识及其培养路径探析

C#学校科研管理系统的设计

国内外图像分割技术研究现状

志愿者活动的调查问卷表

10万元能开儿童乐园吗,我...

中国学术生态细节考察《...

公寓空调设计任务书

承德市事业单位档案管理...

医院财务风险因素分析及管理措施【2367字】

AT89C52单片机的超声波测距...

神经外科重症监护病房患...