《物流车辆路径算法的优化与设计》.pdfVIP

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

【摘要】：随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得

越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的50％

左右，所以降低物流成本首先要从降低物流配送的运输成本起先。

一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物

不能超过它的容量。起初车辆都在中心点，顾客在空间随意分布，车把货物从车库运输到每

一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最终返回车库，

每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以

时间规律变更，这正是本文要探讨的课题。

【关键词】：物流配送；路径；车辆路径问题(VRP)；MATLAB

1前言

1.1课题探讨背景

运输线路是否合理干脆影响到配送速度、成本和效益，特殊是多用户配送线路的确定是一项

困难的系统工程。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，

增加客户对物流环节的满足度，降低服务商运作成本。因此，自从1959年Danting和Ramser

提出车辆路径问题(VehicleRoutingProblem，VRP)以来，VRP便成为近年来物流领域中的

探讨热点。

VRP一般定义为：对一系列发货点和／或收货点，组织适当的行车路途，使车辆有序地通

过它们，在满足肯定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行

驶里程限制、时间限制等)下，达到肯定的目标(如路程最短、费用最小、时间尽量少、运用

车辆尽量少等)。本文围绕VRP绽开了探讨，共包括五章内容。首先，本文收集国内外关于

VRP探讨的文献资料并进行整理、分类，具体介绍了VRP园内外探讨现状，尤其对经典V

RP、有时间窗的VRP(VRPTW)、动态VRP(DVRP)、带实力约束的VRP(CVRP)国内外探讨

现状分别绽开了介绍：然后通过介绍物流配送在整个物流过程中具有的重要意义及我国物流

配送的现状，说明白解决VRP的必要性及现实意义：建立了物流配送中VRP的两种数学模

型：利用回路表示的VRP模型和利用运输成本表示的VRP模型；通过表格具体探讨了VRP

的基本算法；最终，本文运用自然数编码、构造表示可行线路的染色体、类PMX交叉等方

法及对适值函数加入惩处项对标准遗传算法加以改进，并用MATLAB编程实现了本文提出

的算法，以一个VRPTW实例分析证明白该算法的有效性。

1.2车辆路径的概念

车辆路径问题(VRP)一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车辆

有序地通过它们，在满足肯定的约束条件(如货物需求量、发送量、交发货时间、车辆容量

限制、行驶里程限制、时间限制等)下，达到肯定问题的目标(如路程最短、费用最少、时间

尽量少、运用车辆数尽量少等)。

目前有关VRP的探讨已经可以表示（如图1）为：给定一个或多个中心点（中心仓库，central

depot）、一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，

所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间随意分布，车把货物从车

库运输到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最终

返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或

随机、或以时间规律变更。

图1VRP示意图

2车辆路径问题算法综述

目前，求解车辆路径问题的方法特别多，基本上可以分为精确算法和启发式算法2大类。

2.1精确算法

精确算法是指可求出其最优解的算法，主要运用线性规划、整数规划、非线性规划等数学规

划技术来描述物流系统的数量关系，以便求得最优决策。精确算法主要有：

分枝定界法(BranchandBoundApproach)

割平面法(CuttingPlanesApproach)

网络流算法(NetworkFlowApproach)

动态规划算法(DynamicProgrammingApproach)

总的说来，精确性算法基于严格的数学手段，在可以求解的状况下，其解通常要优于人工智

能算法。但由于引入严格的数学方法，计算量一般随问题规模的增大呈指数增长，因而无法

避开指数爆炸问题，从而使该类算法只能有效求解中小规模的确定性VRP，并且通常这些

算法都是针对某一