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

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;Δτk ij(t)表示第k只蚂蚁在周游过程中释放在路径上的信息素,其值视蚂蚁表现的优劣程度而定。路径越短释放的信息素就越多。

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

其中,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]免疫算法和蚁群算法相结合的免疫蚁群算法不仅体现了免疫算法的自适应性、多样性、全局寻优能力强等优点,而且有效克服了蚁群算法搜索时间长、易陷入停滞等缺点。免疫蚁群算法首先利用免疫算法寻找可行的较优解,利用寻找出的较优解产生信息素的初始值,然后再利用蚁群算法求解,从而缩短了搜索时间。

文章来源：《中国医疗器械信息》 网址: http://www.zgylqxxx.cn/qikandaodu/2021/0120/504.html