物流车辆路径算法的优化与设计.doc

物流车辆路径算法的优化与设计
【摘要】：随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的50％左右，所以降低物流成本首先要从降低物流配送的运输成本开始。
一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化，这正是本文要研究的课题。
【关键词】：物流配送；路径；车辆路径问题(VRP)；MATLAB
1前言
1.1课题研究背景
运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。因此，自从1959年Danting和Ramser提出车辆路径问题(VehicleRoutingProblem，VRP)以来，VRP便成为近年来物流领域中的研究热点。
VRP一般定义为：对一系列发货点和／或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。本文围绕VRP展开了研究，共包括五章内容。首先，本文收集国内外关于VRP研究的文献资料并进行整理、分类，详细介绍了VRP园内外研究现状，尤其对经典VRP、有时间窗的VRP(VRPTW)、动态VRP(DVRP)、带能力约束的VRP(CVRP)国内外研究现状分别展开了介绍：然后通过介绍物流配送在整个物流过程中具有的重要意义及我国物流配送的现状，说明了解决VRP的必要性及现实意义：建立了物流配送中VRP的两种数学模型：利用回路表示的VRP模型和利用运输成本表示的VRP模型；通过表格详细讨论了VRP的基本算法；最后，本文使用自然数编码、构造表示可行线路的染色体、类PMX交叉等方法及对适值函数加入惩罚项对标准遗传算法加以改进，并用MATLAB编程实现了本文提出的算法，以一个VRPTW实例分析证明了该算法的有效性。
1.2车辆路径的概念
车辆路径问题(VRP)一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定问题的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。
目前有关VRP的研究已经可以表示（如图1）为：给定一个或多个中心点（中心仓库，centraldepot）、一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化。

图1VRP示意图
2车辆路径问题算法综述
目前，求解车辆路径问题的方法非常多，基本上可以分为精确算法和启发式算法2大类。
2.1精确算法
精确算法是指可求出其最优解的算法，主要运用线性规划、整数规划、非线性规划等数学规划技术来描述物流系统的数量关系，以便求得最优决策。精确算法主要有：
分枝定界法(BranchandBoundApproach)
割平面法(CuttingPlanesApproach)
网络流算法(NetworkFlowApproach)
动态规划算法(DynamicProgrammingApproach)
总的说来，精确性算法基于严格的数学手段，在可以求解的情况下，其解通常要优于人工智能算法。但由于引入严格的数学方法，计算量一般随问题规模的增大呈指数增长，因而无法避开指数爆炸问题，从而使该类算法只能有效求解中小规模的确定性VRP，并且通常这些算法都是针对某一特定问题设计的,适用能力较差,因此在实际中其应用范围很有限。
2.2启发式算法
由于车辆路径优化问题是NP难题，高效的精确算法存在的可能性不大(除非P=NP)，所以寻找近似算法是必要和现实的，为此专家主要把精力花在构造高质量的启发式算法上。启发式算法是在状态空间中的改进搜索算法，它对每一个搜索的位置进行评价，得到最好的位置，再从这个位置进行搜索直到目标。在启发式搜索中，对位置的估价十分重要，采用不同的估价可以有不同的效