随着物流业向全球化、信息化及一体化发展,配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统,运输费用占整体物流费用的50%左右,所以降低物流成本首先要从降低物流配送的运输成本开始。其中,运输线路是否合理直接影响到配送速度、成本和效益,特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径,可以加快对客户需求的响应速度,提高服务质量,增强客户对物流环节的满意度,降低服务商运作成本。因此,自从1959年Danting和Ramser提出车辆路径问题(Vehicle Routing Problem,VRP)以来,VRP便成为近年来物流领域中的研究热点。 VRP一般定义为:对一系列发货点和/或收货点,组织适当的行车路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。本文围绕VRP展开了研究,共包括五章内容。首先,本文收集国内外关于VRP研究的文献资料并进行整理、分类,详细介绍了VRP国内外研究现状,尤其对经典VRP、有时间窗的VRP(VRPTW)、动态VRP(DVRP)、带能力约束的VRP(CVRP)国内外研究现状分别展开了介绍;然后通过介绍物流配送在整个物流过程中具有的重要意义及我国物流配送的现状,说明了解决VRP的必要性及现实意义:建立了物流配送中VRP的两种数学模型:利用回路表示的VRP模型和利用运输成本表示的VRP模型;通过表格详细讨论了VRP的基本算法;最后,本文使用自然数编码、构造表示可行线路的染色体、类PMX交叉等方法及对适值函数加入惩罚项对标准遗传算法加以改进,并用MATLAB编程实现了本文提出的算法,以一个VRPTW实例分析证明了该算法的有效性。 本文在认真分析国内外VRP研究的基础上,对VRP进行数学分析,通过MATLAB实现,说明本文的算法可以有效地求得VRPTW的优化解,是求解VRP的一个较好方案。这对物流配送企业实现配送线路优化、降低成本和提高物流经营管理水平、更快的响应顾客、最终增加企业的竞争力具有重要的参考价值。