纳金网

标题: VRP (Vehicle Routing Problem)车辆路径问题 [打印本页]

作者: 彬彬 时间: 2011-8-3 09:41
标题: VRP (Vehicle Routing Problem)车辆路径问题
车辆路线问题（VRP）是现代物流配送中心末端送货线路研究的一项重要内容，由Dantzig和Ramser于1959年首次提出。

　　它是指在一定的约束下，根据已知的待服务客户的网点布局、物流配送中心的位置、车辆的最大负荷等信息，为车队组织出适当的行车路线分送货物。使得在满足客户的需求的同时，实现诸如路程最短、成本最小、耗费时间最少等目标。

　　最基本的车辆路径问题是从一个服务中心向离散分布在某一区域的n个客户派遣m辆车辆来提供货物，要求确定各车辆的行走路线使总的运输成本最小，并保证每个服务需求点只被其中的一辆车辆访问过一次。

　　TSP（旅行商问题）是由一辆车来串联多个派货点，以完成派送任务，而VRP是由一个车队来完成。所以TSP只是VRP的一个特例。而Gaery已经证明了TSP是NP问题（全名：NP完全问题），所以VRP问题自然也是NP问题，而且还是比TSP更加复杂的NP问题。Savelbergh和Solomon也指出带时间窗的车辆路优化问题（VRPTW：Vehicle Routing Problem with Time Window）是NP问题，并且比一般的VRP更加复杂。

　　但是，人们非但没有因为这个问题的复杂性而放弃对他的研究，更是由于其使用范围的广泛性和问题的复杂性，更多的人将目光投注在他的身上。并且，VRP被进一步的实例化，更多的算法也被提了出来。

　　例如带能力约束的车辆路径问题、带时间窗的车辆路径问题、追求最佳服务时间的车辆路径问题、多车种车辆路径问题、车辆多次使用的车辆路径问题等。

　　被提出的算法大致可以分为两类：精确算法和启发式算法。精确算法顾名思义就是可以求出精确的最优解的算法。然而，对于比TSP还要复杂的VRP来说，目前为止，最有效的精确算法最多也只能包含50个派送点。因此，人们把主要的精力还是集中在了启发式算法上。启发式算法是基于直观或者经验构造出来的算法，且一般不要求将问题描述成标准的数学模型，在可以接受的计算量之内，他得出结果的具有很强的不可预知性，不能保证得到的解就是最优解。其中启发式算法有分为经典启发式算法和通用启发是算法，经典启发式算法一般用于商业软件之中。而通用启发式算法诸如：模拟退火算法、禁忌搜索算法、遗传算法、蚁群算法和神经网络算法等都是研究的热点。

作者: 菜刀吻电线 时间: 2012-1-29 23:19
对你的思念象袅袅的轻烟不绝如缕，对你的祝福是潺潺的小溪叮咚作响。或许岁月将往事褪色，或许空间将彼此隔离。但值得珍惜的依然是你给我的情谊。再次对你说声：新年快乐！

作者: 奇 时间: 2012-2-16 23:28
很经典，很实用，学习了!

作者: C.R.CAN 时间: 2012-4-15 23:24
既来之，则看之！

作者: tc 时间: 2012-5-6 23:19
此地無銀。。。

作者: 晃晃 时间: 2012-5-25 23:19
路过、路过、快到鸟，列位请继续...ing

作者: 菜刀吻电线 时间: 2012-8-11 00:08
很有心,部分已收录自用,谢谢

作者: C.R.CAN 时间: 2012-9-25 23:23
心中有爱，爱咋咋地

作者: 晃晃 时间: 2012-10-13 23:29
先垫一块，再说鸟

作者: 晃晃 时间: 2012-10-31 23:27
不错哦,顶一下......

作者: 奇 时间: 2013-2-11 23:27
你们都躲开，我来顶

欢迎光临纳金网 (http://go.narkii.com/club/)