免疫蚁群算法在常规医疗器械配送路径优化中的应用

费 腾,张立毅,韩应征,张 锦

(1.太原理工大学信息工程学院,太原 030024;2.天津商业大学信息工程学院,天津 300134)

0 引 言

近年来,随着医疗事业的蓬勃发展,医疗器械的需求也随之增加,使得医疗器械物流成为物流产业的重要组成部分。但由于我国医疗器械物流相对于西方发达国家起步较晚,尤其是医疗器械作为一种特殊物品,目前既缺乏专业性的物流队伍,也缺乏科学规范的物流管理。如何快速有效、安全经济地配送医疗器械是目前医疗器械物流的研究重点和热点。

本文将免疫蚁群算法(Immune Ant Colony Optimization,IACO)应用于常规医疗器械物流配送的路径优化中,以合理调度车辆,获得最短路径,减少配送成本,降低患者负担。

1 医疗器械物流配送路径优化模型

为了方便模型建立,对常规医疗器械物流配送的路径优化问题作如下假设:

(1)仅考虑位置已知的单一医疗器械配送中心,所有配送车辆起点和终点均是医疗器械配送中心。

(2)车辆运输的医疗器械可以混装,且每个医疗器械需求点所需要的医疗器械不超过车辆的最大载重量。

(3)每个医疗器械需求点的位置和需求量都已知,其需求由且仅由一辆车一次送货满足。

(4)车辆的载重量已知。

(5)车辆对每个医疗器械需求点服务,途中只有卸货而无装货的情况。

在上述基本假设的前提下,以配送成本为最小,构造配送路径的目标函数为[1]

式中,L为医疗器械需求点的个数;c0为出车的单位成本;m′为车辆数;c为车辆行驶距离的单位成本;dij(i,j=0,1,2,…,L)为医疗器械需求点 i与医疗器械需求点 j点之间的距离;c1为超载惩罚系数;g1为第 i个医疗器械需求点的需求量;q为车辆的最大载重量;k(k=1,2,…,m′)为车辆的编号。

将医疗器械配送中心编号为 0,医疗器械需求点编号为 1、2、3、…、L,定义变量 xijk、yki为

式(1)包括3部分,第一项为车辆的固定成本,第二项是车辆的运输成本,第三项是超载惩罚成本。式(2)与式(8)为约束条件;式(2)表示车辆在运输过程中,对任何一辆车而言,所装医疗器械的总重量不会超过其车辆本身的最大载重量;式(3)、式(4)和式(5)保证每个医疗器械需求点有且仅有一辆车通过;式(6)表示第 j需求点的任务由第 k辆车完成时,车辆 k从需求点 j行驶到需求点j;式(7)表示第 i需求点的任务由第k辆车完成时,车辆 k从需求点 j行驶到需求点 i;式(8)保证了所有车辆从医疗器械配送中心出发,最后回到医疗器械配送中心。

2 蚁群算法

蚁群算法是一种仿生学算法,由意大利学者M.Dorigo[2]等人提出。设有 n座城市,任意两座城市 i、j之间的距离为 dij(i,j=1,2,…,n),bi(t)表示t时刻位于城市 t的蚂蚁个数,蚁的总数,τij(t)表示 t时刻支路 ij上的信息素量,在 t=0时刻,各条路径上的信息量强度相等。Δτij(t)=C(C为常数)。

随着时间的推移,新的信息素加进来,旧的信息素要挥发,设 ρ为信息素的挥发因子,一般取值为[0,1][3],表征信息素的挥发快慢。当所有蚂蚁完成一次周游后,各条路径上的信息素为

Δτij(t)表示本次周游中路径 ij上的信息素增量 ,初始时刻,Δτij(0)=0;Δτkij(t)表示第k只蚂蚁在周游过程中释放在路径上的信息素,其值视蚂蚁表现的优劣程度而定。路径越短释放的信息素就越多。

式中,Q为常数,Lk表示本次周游第k只蚂蚁所形成的回路长度。蚂蚁k在周游时由城市 i向城市 j的转移概率 pkij为

其中,allowedk=(1,2,…,n)-tabuk表示蚂蚁 k当前能选择的城市集合;tabuk(k=1,2,…,m)表示第 k只蚂蚁的禁忌表,记录蚂蚁 k已经经过的城市,用来说明蚂蚁的记忆性。ηij(t)为启发函数,表示由城市 i转移到城市 j的期望程度,一般取ηij(t)=1/dij。α为路径 ij上残留信息的重要程度,β为启发信息的重要程度。

蚁群算法基本运行过程:m只蚂蚁同时从某个城市出发,根据式(12)选择下一个要访问的城市,蚂蚁趋向于访问具有较高信息素强度量的路径。已经去过的城市放入 tabuk中,当所有的蚂蚁完成了一次巡回后,由式(9)到式(11)更新每条路径的信息素,反复上述过程,直到终止条件成立。

3 免疫蚁群算法求解模型

免疫算法具有快速随机的全局搜索能力,但对于系统中的反馈信息利用不足,当求解到一定范围时往往做大量无为的冗余迭代,求解效率低;而蚁群算法具有分布式并行搜索能力,通过信息量的积累和更新收敛于最优路径上,但其初期信息素匮乏,求解速度较慢。[4]免疫算法和蚁群算法相结合的免疫蚁群算法不仅体现了免疫算法的自适应性、多样性、全局寻优能力强等优点,而且有效克服了蚁群算法搜索时间长、易陷入停滞等缺点。免疫蚁群算法首先利用免疫算法寻找可行的较优解,利用寻找出的较优解产生信息素的初始值,然后再利用蚁群算法求解,从而缩短了搜索时间。

(1)抗体的编码

把目标函数和约束条件作为抗原,抗体采用自然编码方式,利用需求点直接排列方法。[5]

随机产生 L个需求点的全排列(i=1,2,…,m1-1,m1,…,n1-1,n1,…,L)若q,则将 m1至 L逐个后移一位,将 0插入第 m1位。若q,则将 n1至L逐个后移一位。将0插入第 n1位。按照这样的方法继续,直至将 m′(m′为车辆数)个 0全部插入到相应位置。这样就形成了一条长度为 L+m′+1的初始抗体

车辆 1从配送中心 0出发,服务需求点 1到需求点m1-1,然后返回配送中心0,形成子路线1;车辆 2从配送中心0出发,服务需求点m1到需求点n1-1,然后返回配送中心 0,形成子路线 2。以此类推,形成子路线。

(2)亲和力函数

1)抗体和抗原之间的亲和力

抗体和抗原之间的亲和力表示抗体与抗原之间的匹配程度。抗体 s和抗原之间的亲和力由配送路径的目标函数 Z(s)变换而成,即

2)抗体和抗体之间的亲和力 Bs,t

抗体和抗体之间的亲和力表示抗体与抗体之间的匹配程度和抗体与抗体之间的相似程度,采用基于配送路径的目标函数差的方法将抗体 s与抗体 t之间的亲和力定义为

(3)产生新的抗体

采用选择、交叉、变异三个操作用以产生新的抗体。

1)选择操作

选择操作的目的是为了把优质的个体直接传到下一代或通过交叉配对产生新的个体再传到下一代。选择操作选用轮盘赌选择[5]的方法,按照一定的淘汰概率淘汰一部分劣质的个体。

2)交叉操作

交叉操作的作用是从当前种群中选出优良个体作为父代以繁殖下一代。交叉操作可分为两个步骤:第一步是将新复制产生的匹配的抗体随机两两匹配,第二步进行交叉繁殖。

3)变异操作

变异操作采用反转变异,即在个体编码中,随机选择两点(两点之间称为反转区域),再将反转区域按反序插入到原来位置中即完成反转变异操作。[5]

(4)免疫蚁群算法求解模型步骤

Step 1输入代价函数和约束条件确定抗原。

Step 2对抗体进行编码,产生初始抗体。

Step 3计算抗体和抗原之间的亲和力以及抗体和抗体之间的亲和力。

Step 4进行选择、交叉、变异产生新的抗体,从而产生可行的较优解,产生信息素的初始值 。

Step 5令NC=0(NC为迭代次数),load bus=0(load bus为车辆的负载),初始化参数。

Step 6将 m只蚂蚁都放在医疗器械配送中心。

Step 7根据式(12)计算蚂蚁 k的转移概率,选择并移动到下一个城市 j,同时将 j加入到 tabuk。检查车辆的负载是否达到最大载重。若达到,返回医疗器械配送中心。

Step8 tabuk是否满。若为否,回到 step 7,否则 ,继续 step 9。

step 9计算目标函数,记录当前的最好解,进行信息素更新。初始时刻的信息素由式(15)决定。

step 10若 NC

4 实验仿真

假定医疗器械配送中心的坐标是(14.5,13.0),医疗器械配送中心需要向 20个医疗器械需求点运送医疗器械。表 1所示为各个医疗器械需求点的坐标及需求量。每辆车的最大装载量为 8吨。仿真时,令 c0=0,则费用只与车辆运行路程有关。令单位路程的代价 c=1,则费用与运行长度相等,即车辆运行 1个单位距离,费用就增加一元。超载惩罚系数 c1=1。文献[6]中给出了对 α、β、ρ设置的研究结果,经过多次试验,当 α=1、β=5、ρ=0.6时,运算结果最好。各医疗器械需求点之间以及各医疗器械需求点与医疗器械配送中心的距离,利用距离公式计算,即

运输车辆数为

式中[·]表示取整,λ∈ (0,1),可根据装车的复杂性及约束多少调整,一般装车越复杂,λ越小,反之则越大。[7]

由于各个医疗器械需求点的总需求量为 23.7吨,根据式(17),取 λ=0.98,故需车辆数为

表1 实验数据 吨

图 1所示为基本蚁群算法的一次最优解的运行路线。图 2所示为免疫蚁群算法的一次最优解的运行路线。图 3所示为免疫蚁群算法与基本蚁群算法在相同运行环境下的一次最优解寻优曲线。

图1 基本蚁群算法一次最优解路线图

实验仿真表明,免疫蚁群算法的收敛速度高于基本蚁群算法,因而免疫蚁群算法有效地缩短了搜索时间。

5 结束语

本文将免疫蚁群算法用于常规医疗器械配送路径优化中。实验仿真表明,该算法在一般医疗器械配送的路径优化问题中,具有全局寻优能力,收敛速度快等优点,为解决常规医疗器械配送路径的优化提出了一条新的思路。

[1] 朱树人,李文彬,匡芳君.一种带软时间窗的物流配送路径优化遗传算法[J].计算机工程与科学,2005,27(12):108-110.

[2] Dorigo M.Ant Colony System:A Cooperative Learning approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[3] 刘立东.改进蚁群优化算法的研究[D].成都:西南交通大学,2005.

[4] 梁啸.基于蚁群和免疫组合算法的物流配送路径优化问题的研究[D].吉林:吉林大学,2007.

[5] 闫旺.基于免疫算法的物流配送车辆优化调度研究[D].西安:长安大学,2005.