基于改进蚁群算法的物流配送复杂路径优化问题研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于改进蚁群算法的物流配送复杂路径优化问题研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

［摘 要］对物流配送中这类有装卸混合和任务组合的复杂路径优化问题,建立了考虑实际载重量的动态费用计算模型,并在基本蚁群算法基础上,改变了常用的以地点为基础的编码方式,取之以具体作业作为编码基础,既简化了这类复杂路径问题的算法设计,也便于算法的编程实现,并在局部作业路径搜索时根据问题特点设计了相应的启发式算法,并通过编程运行实验,证明了该算法的有效性。

［关键词］物流配送;路径优化;蚁群算法;动态费用系数;装卸混合

［中图分类号］TP18 ［文献标识码］A ［文章编号］1005-6432（2011）28-0006-03

1 引 言

物流配送是物流企业日常经营管理中一个非常重要的内容,其效率高低直接影响物流企业的运作效益。物流配送中的路径优化问题是物流企业需要关注的常态性问题,配送路径是否合理,对加快配送速度、降低配送成本、提高服务质量及增加总体经济效益影响较大,故采用科学合理的方法确定配送线路是配送业务中一项非常重要的工作。

在日常的物流配送活动中,物流企业可能要面对这样一类多品种、少批量、多批次的配送问题。对这样一类问题,即可以描述为：货物运输的每一项任务的运量都不超过车辆的载重量,且都有各自的装卸载点,物资可以共同配载。此类问题即为NP-hard问题,很难找到此问题的精确解,特别在现实配送过程中,在装卸载点和任务项较多时,对这类问题的解一般都通过启发式算法或生物进化算法来求解。本文拟用蚁群算法求解此类路径问题,并针对问题的特殊性对基于TSP的基本蚁群算法进行改进,从而可以较好地解决配送的复杂路径优化问题。

2 问题提出

本文的路径优化问题可描述为：有l项货物配送任务r,表示为r=1,…,l,每项任务r的装卸载点分别为Rrs和Rrt,任务量为gr,装卸载作业时间分别为Trs和Trt。保障任务由物流企业车场发出的vn台同型车辆来完成,其载重量为q,单车工作时间tk不超过T,工作里程Sk不超过S,任务完成后回至企业车场。已知gr=q(r=1,…,l),且单项任务完成时间不超过T,里程也不超过S,任务可以组合不能拆分。确定所需车数vn以及所有车辆的配送任务和行驶线路,使路径最优。

如果所有任务量都满足0.5q

3 模型建立

为构造数学模型的方便,将企业编号为0,任务r编号为1,…,l,企业及装卸点均以点i(i=0,1,…,n)来表示。定义变量如下：

α――载重量的费用转换系数。

式(1-1)表示车辆从企业车场出发至装货点的费用,包括固定费用和空驶费用；式(1-2)表示车辆从点i至点j的空驶费用；式(1-3)表示车辆载重行驶的费用,在空驶费用的基础上根据实际载重量增加相应的运行费用。

对于式(1)中参数c0、c1、α,不同的取值决定了不同的路径优化策略。

①当c0较大,则路径优化目标是使派车的数量尽量少；

②当c1较大,则路径优化目标是尽量减少空驶的里程；

③当α较大,则在车辆实施混合装载运输时,要尽量减少车辆重载的绕行距离,即尽可能使重载车辆直接驶向卸载点,减少无效的周转量。在一些文献中,费用定义并没有考虑载重时的费用增加问题,这在实际问题中会产生无效的周转量,即重载绕行。

针对参数实际意义,依据具体运输环境和费用消耗,通过设置具体的参数值,使路径优化策略的目标达到费用最小。本文论述的是在车辆容量、工作时间和里程的约束下,在极小化出行车数的基础上,再极小化空驶里程和无效周转量。

3.2 配送式保障路径优化的数学模型

建立动态费用配送式保障路径优化的数学模型如下：

其中,式(2)表示费用极小的优化目标；式(3)表示车辆的运载量不超过车辆的容量；式(4)表示车辆工作时间的约束；式(5)表示车辆工作里程的约束；式(6)表示一项任务只能由一辆车完成；式(7)表示所有车辆自企业车场出发；式(8)表示所有车辆任务完成后返回企业车场；式(9)与式(10)为变量的取值约束。

4 算法设计

4.1 蚁群算法简介

蚁群算法(又称人工蚁群算法)是受到对真实蚁群行为研究的启发而提出来的。仿生学家经过大量细致观察研究后发现,蚂蚁个体之间是通过一种称为激素的物质进行信息传递的。蚂蚁能够在经过的路径上留下该种物质,并在运动过程中能感知这种物质,以此指导运动方向。故由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多,则后者选择该路径的概率就越大。

4.2 改进蚁群算法设计

此问题与经典的TSP问题有很大的不同,①不同任务的装卸载点可能重合,导致一个点必须要经过多次；②不同任务要进行组合,致使蚂蚁路径并不是从装载点直达对应卸载点；③在里程和时间的约束下,蚂蚁必须先回至企业车场再重新出发；④在载重量的约束下,蚂蚁下一步的选择是以任务为准则,并结合时间和里程约束。

因此,为了在算法中清晰地表示每一步的动作(所到达的地点,执行的任务,装载或(和)卸载),笔者将所有任务的装卸载操作进行编号,l项任务,共有2l个操作编号,再加上车场的0编号,共2l+1个编号。在算法中蚂蚁是依次经过各操作,进而形成编号的序列(同时也就决定了空间路径,蚂蚁回到车场一次则在序列中加入车场编号0一次)。由于在路径中间蚂蚁要回至车场,则完成一次循环的最大时间为3l(当每完成一项任务回一次车场时)。

为了模拟实际蚂蚁的行为,令m表示蚁群中蚂蚁的数量；cij(i,j=0,1,2,…,2l)表示从i操作至j操作的费用；tij(nc)表示程序循环nc次后在ij操作连线上残留的信息量。在初始时,设tij(0)=C(C为常数),各条路径上信息量相等。蚂蚁k(k=1,2,…,m)在运动过程中,根据各路径(任务排列和地点排列)上的信息量决定转移方向。pkij(t)表示在t时刻蚂蚁由操作i转移到操作j的概率：

其中,allowed(k)表示蚂蚁k下一步允许选择的操作,只可能是已经过上位操作的下位操作(即卸载),或没有经过的上位操作(即装载)；用now(k)记录蚂蚁k当前趟次已经走过的操作；用before(k)记录蚂蚁k前面趟次已经走过的操作；用next(k)记录需要蚂蚁k在下一趟次执行的操作。ηij(t)表示t时刻由操作i转移到操作j的期望程度,依据具体的启发式算法确定：若操作j是没有经过的上位操作,则依据约束确定此任务能否加入路径,若能加入,则局部排序后增加费用小的期望程度较大,若不能加入,则记录在next(k)中；若操作j为蚂蚁k已经过操作的下位操作,则j为其必经之操作,多个下位操作之间只存在局部排序问题(具体排序是在时间和里程约束下依据费用进行确定,根据局部排序规模确定方法,由于车辆正在执行的任务数量不会太大,笔者采用历遍来实现下位点排序,排序靠前则期望程度较大),不存在选择问题。α,β分别表示蚂蚁在运动中所积累的信息和启发式因子在路径选择中所起的不同作用。

其中Q是常数,Ck表示蚂蚁k在本次循环中经过路径的总费用。

对所涉及的参数m,α,β,ρ,C,Q的取值,是在借鉴已有研究成果的基础上,再通过编程在计算机上运行实验,不断比较和调整并最终确定具体的取值。停止条件可以用固定循环次数或当进化趋势不明显时便停止计算。

4.3 算法实现

在算法原理的基础上,具体的算法实现可依据如下的算法流程：

(1)初始化。给各参数赋初值；若连续循环max次没有优化,则退出；循环计数nc=0；将m只蚂蚁置于编号为0的车场,并且都随机地选择l项任务的上位操作；将蚂蚁k所处的初始上位操作放到now(k)中,同时确定allowed(k)和next(k)；时刻t=1。

(2)判断jilu是否等于max。若是,则得到最佳路径,输出结果并结束；若小于,则转步骤(3)。

(3)在allowed(k)中,对蚂蚁k计算概率pkij(t),选择下一个操作j,将蚂蚁移至此操作并将其加入到now(k)中,t=t+1,同时修改allowed(k)和next(k)。若allowed(k)为空,则表示本趟任务结束,蚂蚁需回至车场；若next(k)同时也为空,则表示所有任务均已执行；若next(k)不为空,则表示蚂蚁回至车场后需要再执行任务一趟(下一趟路径的开始操作依据随机(无信息量数据时)或路径信息量确定)。反复此步骤直至所有蚂蚁均完成全部任务项。nc=nc+1。

(4)计算Ck,Δtkij,Δtij,tij(nc),更新当前最优路径,以及各路径上的信息量。最优路径更新,则jilu=0；最优路径没有更新,则jilu=jilu+1。

(5)所有蚂蚁自车场根据路径信息量以相应概率选择初始上位操作,更新now(k),同时更新allowed(k)和next(k)；时刻t=1,转步骤(2)。

从输出的结果中可以得到所优化的最终操作路径以及对应的费用,进一步即可得到任务排序、空间路径和使用车辆的数量(由蚂蚁回车场次数确定)。

5 实验结果与分析

为验证本文设计的蚁群算法的有效性,本文以具体物流配送的路径优化实例为例,并与遗传算法和TSP问题的基本蚁群算法的求解结果进行比较。

有9项配送任务r,编号分别为1,…,9,车辆容量q为5t,运行车速50km/h,单车工作时间上限T为6h,每次装卸作业时间均为20min；日工作里程上限S为200km；c0值为200元/台,c1值为10元/千米,α值为20元/吨千米；各点之间依据坐标求直线距离。配送任务的具体情况,如表1所示，车场及各装载点、卸载点编号和坐标如表2所示。

最终的优化方案为：车数为3台；第一条路线为081280,任务为7,9,总行程129.6km,对应载重量依次为0,3.7,2.1,0,总工作时间为3.93h；第二条路线为07345110,任务为6,2,4,5,总行程154.8km,对应载重量依次为0,1,4.9,3.2,2.7,0,总工作时间为5.76h；第三条路线为092136100,任务为8,1,3,总行程123.6km,对应载重量依次为0,2.5,3.4,0.9,4.9,0.9,0,总工作时间为4.47h。

在此参数取值下,本文所设计的蚁群算法具有较强的寻优能力,在此类问题上能够获得比遗传算法和TSP问题的基本蚁群算法更高的搜索效率和更好的优化结果,如表3所示。

6 结 论

本文针对这类具有装卸混合和任务组合特点的配送路径优化问题,建立了更切合实际的考虑实际载重量的动态费用计算模型,并在经典TSP问题的基本蚁群算法的基础上,通过改变传统的编码方式,以具体操作作为算法编码的基础,在节点转移时根据具体问题设计相应的启发式算法,使算法更符合这类问题,并通过编程运行,实验证明了该算法的有效性。

当然,目前蚁群算法还缺乏坚实的数学基础和严密的分析方法,各项参数的选取更多的是依赖于实验或经验,还没有形成相关的理论来确定,这些都有待于进一步的研究。而且对于配送时所涉及的复杂路径优化问题,高效的精确算法很难设计出来,因此寻找近似算法是必要的,也是更为现实的。

参考文献:

［1］李军.有时间窗的车辆路线安排问题的启发式算法［J］.系统工程,1996,14(5)：45-50.

［2］谢秉磊,李军,郭耀煌.有时间窗的非满载车辆调度问题的遗传算法研究［J］.系统工程学报,2000,15(3)：290-294.

［基金项目］中国物流学会课题支持,项目名称“应急物资配送中心开设研究”,项目编号2009CSLKT012。

［作者简介］赵勇(1981―),男,辽宁大连人,后勤指挥学院博士研究生,参谋,研究方向：军事物流,军事交通运输；曾勇(1980―),男,湖北大悟人,后勤指挥学院博士研究生,讲师,研究方向：军事物流,军事供应链。