当前位置:白金会官网 > 所有分类 > 工程科技 > 信息与通信 > 车辆路径问题优化算法
免费下载此文档侵权投诉

车辆路径问题优化算法

车辆路径算法

车辆路径问题优化算法

美国物流管理学会(Council of Logistics Management,CLM)对物流所作的定义为:“为符合顾客的需要,对原料、制造过程中的存货与制成品以及相关信息,从其起运点至最终消费点之间,做出的追求效率与成本效果的计划、执行与控制过程。”

而有关资料显示,物流配送过程(包含仓储、分拣、运输等)的成本构成中,运输成本占到52%之多。因此,如何在满足客户适当满意度的前提下,将配送的运输成本合理地降低,成为一个紧迫而重要的研究课题,车辆路径问题正是基于这一需求而产生的。

2.1车辆路径问题的定义

车辆路径问题可以描述为:给定一组有容量限制的车辆的集合、一个物流中心(或供货地)、若干有供货需求的客户,组织适当的行车路线,使车辆有序地通过所有的客户,在满足一定的约束条件(如需求量、服务时间限制、车辆容量限制、行驶里程限制等)下,达到一定的目标(如路程最短、费用极小、时间尽量少、使用车辆数尽量少等)。[4]

因此研究车辆的路径问题,就是要研究如何安排运输车辆的行驶路线,使运输车辆依照最短的行驶路径或最短的时间费用,依次服务于每个客户后返回起点,总的运输成本实现最小。

车辆路径问题已被证明是NP-Hard问题,因此求解比较困难。然而,由于其在现实生活中应用非常广泛,使得它无论在理论上还是在实践上都有极大的研究价值。

Penousal Machado等人[5]指出车辆路径问题(vehicle routing problem,简称VRP)是一个复杂的组合优化问题,是古老的旅行商问题和背包问题的综合。实际上,车辆路径问题通常可被分解或转化成一个或几个已经研究过的基本问题,再采用相应比较成熟的基本理论和方法,以得到最优解或满意解。

这些与车辆路径问题相关的常用基本问题有;旅行商问题、运输问题、背包问题、最短路问题、最小费用最大流问题、中国邮路问题、指派问题等。

旅行商问题可被描述为:一个推销员欲到n个城市推销商品,每2个城市之间的距离是已知的。如何选择一条路径使推销员依次又不重复地走遍每个城市后,回到起点且所走的路径最短。

运输问题关心的是(确实的或是比喻的)以最低的总配送成本把供应中心(称为出发地,sources)的任何产品运送到每一个接受中心(称为目的地,

destinations)。运输问题需要的数据仅仅是供应量、需求量和单位成本。 背包问题是指有一只固定容量的背包和若干体积、重量不等的物品,背包的容量不允许装下这所有的物品,那么如何选择适当的物品装入背包,使得背包的装载量(所装物品的重量之和)最大。

最短路径问题解决的是在一个网络中,如何寻找两点之间的最短路径。这两点之间通常没有直接的通路可达,但可经由若干中间结点相通。

最小费用流问题主要解决如何以最小成本在一个配送网络中运输货物。最小费用流问题又称为网络配送问题。

最大流问题和最小费用流问题一样,也与网络中的流有关。但是它们的目标不同,最大流问题不是使得流的成本最小化,而是寻找一个流的方案,使得通过网络的流量最大。

中国邮路问题是由我国管梅谷同志在1962年首先提出的,它可描述为:一个邮

第1页

免费下载Word文档免费下载:车辆路径问题优化算法

(下载1-9页,共9页)

我要评论

返回顶部