物流车辆路径算法的优化与设计.doc资源-CSDN文库

版权申诉

201 浏览量 2022-05-30 15:44:34 上传评论收藏 316KB DOC 举报

资源推荐

资源详情

资源评论

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

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

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

％左右，所以降低物流成本首先要从降低物流配送的运输成本开始。

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

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

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

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

机、或以时间规律变化，这正是本文要研究的课题。

【关键词】：物流配送；路径；车辆路径问题；

前言

课题研究背景

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

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

量，增强客户对物流环节的满意度，降低服务商运作成本。因此，自从  年 

和  提出车辆路径问题 !，以来， 便成为近年

来物流领域中的研究热点。

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

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

驶里程限制、时间限制等下，达到一定的目标如路程最短、费用最小、时间尽量少、使

用车辆尽量少等。本文围绕  展开了研究，共包括五章内容。首先，本文收集国内外

关于  研究的文献资料并进行整理、分类，详细介绍了  园内外研究现状，尤其对

不同的估价可以有不同的效果。目前已提出的启发式算法较多，分类也相当多，按 

& 的分类法，主要的启发式算法有以下几类：构造算法、两阶段法、智能化算法。

%%构造算法# /

这类方法的基本思想是：根据一些准则，每一次将一个不在线路上的点增加进线路，直到

所有点都被安排进线路为止。该类算法的每一步把当前的线路构形很可能是不可行的跟

另外的构形也可能是不可行的进行比较并加以改进，后者或是根据某个判别函数例如总

费用会产生最大限度的节约的构形，或是以最小代价把一个不在当前构形上的需求对象插

入进来的构形，最后得到一个较好的可行构形。这类算法中中最著名的是 #* 和

" 在 01 年提出的节约算法。

构造算法最早提出来解决旅行商问题，这些方法一般速度快，也很灵活，但这类方法有时

找到的解离最优解差得很远。

%%%两阶段法)2'

学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进，为此提出了

两阶段法。第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况

下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得

以改进，一直继续到不能再改进目标函数值为止。3 和  于 41 年提出的

)' 算法，#5&、66 和  的算法以及 + 和 7*  的算法

都属于两阶段法。一般第一阶段常用构造算法，在第二阶段常用的改进技术有 %2

'-0，82'9-48和 :2':-40交换法，这是一种在

解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。

一些基于数学规划的算法也属于两阶段法，把问题直接描述成一个数学规划问题，根据其

模型的特殊构形，应用一定的技术如分解进行划分，进而求解己被广泛研究过的子问题

+ 和 7* -;。

在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求

解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断能力，并且根据

知识直感，把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的

可能性。

此方法是目前成果最丰富、应用最多的一类方法。每一种方法讨论的情况不尽一致，适用

范围也不完全相同。

%%8智能化算法<

这类算法以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间。

总体来看，尽管启发式算法能够在有限的时间内求出质量较高的解，但由于其搜索解空间

的能力有所限制，因此经常无法达到预期的要求。% 世纪  年代以来，由于人工智能方

法在解决组合优化问题中的强大功能，不少学者开始将人工智能引入车辆路线问题的求解

中，并构造了大量的基于人工智能的启发式算法智能化启发式算法。智能化启发式算法

从本质上讲仍然属于启发式算法，其基本思想是从一初始解开始，通过对当前的解进行反

复地局部扰乱 !以达到较好的解。目前，最常见的智能化启发式算法包括模

拟退火算法= &、禁忌搜索算法! =、遗传算法3

、蚁群算法#,和神经网络( ()*方法等。

%8 中常见的约束条件

在  中，最常见的约束条件有>

容量约束：任意车辆路径的总重量不能超过该车辆的能力负荷。引出带容量约束的车

辆路径问题#'& !，#。

%优先约束：引出优先约束车辆路径问题 !)

'&#，#。

剩余30页未读，继续阅读

内容反馈

版权申诉

oligaga

粉丝: 50
资源: 2万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip