文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 蚁群优化算法在物流配送车辆路径问题中的应用研究
侵权投诉

蚁群优化算法在物流配送车辆路径问题中的应用研究

tsp 蚁群算法 数学建模

第11卷#第6期席先杰:蚁群优化算法在物流配送车辆路径问题中的应用研究2011年12月

B

示)有n(1,2,,,n)个客户需要配送货物,每个客户需要配送的货物量是Xi(i=1,2,3,,,n),客户点i到j的距离为dij(i,j=1,2,,,n),设实际所需要的车辆数为S,每辆配送车的配送货物容量是Q,nk为第k辆车所经过的客户点总数,用集合Rk=rki0[i[nk来表示第k辆车所经过的客户点,其中,rki表示第k辆车经过的第i个客户点,如果经过则rki为1,否则为0,rk0表示配货中心,得到的数学模型如下:

minz1=m

i=0j=0s=1

p=

kij

uIJ

k

Sij(t)Siu(t)

A

Gij(t)Giu(t)

,jIJk

(7)

0,otherwise

其中,Jk为蚂蚁k当前状态下尚未访问过的客户位点的集合,该集合在系统进行过程中会不断地动态调整;参数A,B分别用来控制信息素轨迹强度和配送货物所用时间的相对比重。随着时间的推移,信息素量将逐渐挥发。用参数1-Q表示信息素浓度强度的降低程度,经过h个时刻后,蚁群会完成一次配送移动过程,此时客户点i,j线路上的信息素浓度强度根据下式进行调整:

Sij(t+h)=Q#Sij(t)+

k

k=1

(1)

m

minz2= s.t.

ijs

EEE

kk

dijrijs(2)(3)(4)(5)(6)

E

m

$Sij

k

(8)

k=1

Er

i=0K

EXr

iik

k

is

[Q,s=1,2,,,m

式(8)中,$Sij表示第k只蚂蚁在本次配送过程中对客户点i,j之间线路上信息素浓度强度的增量,其定义如下:

QPLk,如果蚂蚁在本次配送中经过了k$Sij= 路径i,j(9)

0,否则

式(9)中,Q表示信息素浓度强度是一定常数;Lk=

=1,i=1,2,,,n

k=0K

ExEx

K

=rjs,j=1,2,,,k;s=1,2,,,m=ris,i=1,2,,,k;s=1,2,,,m

ijs

k=0

其中,式(1)目标函数z1最小化车辆数,式(2)z2是求得最短的总路径长度,式(3)为车辆容量限制,保证每条路径上各客户点的货物需求总量和必须小于车辆容载能力,式(4)为每个客户的运输任务仅由一辆车完成;式(5)和式(6)限制了每个客户点必须有一辆车完成且只能由一辆车来完成,且只能被访问一次。

2.3 配送车辆路径规划问题

配送车辆路径规划就是对含有n个配送目的地的货单,寻找一条最佳的货物配送路径,通过合理调度配送车辆和货物单,使完成一次配所送花费的成本最小。本文利用基本蚁群算法并对其进行改进,以求解货物配送过程中的最短路径。求解过程如下,设定蚁群中的蚂蚁数量为m,Sij(t)表示t时刻在i,j线路上残留的信息素量,所表示的实际意义为完成客户点i的货物配送后,选择客户点j配送货物的信息素的强度。系统初始状态时,各个客户点上的信息素量相等,Sij(0)=S0,Gij(t)是能见度因数,在本文中定义为(1PTij),Tij表示从客户点i到客户点j送货用时。蚂蚁k(k=1,2,,,m)在运动过程中,根据送货线路上信息素的强度来决定转移方向,t时刻蚂蚁k从客户点i到客户点j的转移概率p定义为

k

ij

E

tij表示蚂蚁k在本次配送中完成送货单中

k

所有货物的客户位点花费的时间。本文对信息素浓度强度进行调整时利用整体信息而不是局部信息,因此,求解车辆路径规化问题时具有较好性能。2.4 算法描述

基本蚁群算法在每次进化时,只能固定地选择其中一条路径,若在每一个点上都放置一只蚂蚁,必然使算法复杂度增加,搜索时间变长。对于车辆路径规化问题,针对问题本身的特点,由于每次配送操作时车辆都是从物流中心点开始配送,且完成配送任务后又回到配送中心点,因此,本文对基本蚁群算法进行改进。每次配送进行开始时,在起始节点即配送客户点上放置m只蚂蚁。作业开始后,m只蚂蚁随机地选择下一个配送客户点。此方法有效减小了算法复杂度,缩短了搜索时间。

算法具体步骤如下:

(1)系统初始化,t=0,配送次数nc=0,每条边即客户点i到客户点j线路上的Sij(0)=S0,且$Sij=0,Jk=(0,1,,,n),tabuk=ª(禁忌表为空)。(2)将m只蚂蚁放置在物流中心初始位置处,将第k只蚂蚁所在的客户点号从Jk中删除,并加入到

k

tabuk中,开始循环搜索路径,根据式(7)中概率pij选择下一个要送货的客户点j并记录该客户点编号,将刚选择的客户点编号j从Jk中删除,并加入到tabuk中。

(下转35页)

上一页第2页

你可能喜欢

  • 车辆路径优化问题
  • 蚁群算法 matlab
  • 物流配送优化问题
  • 汽车零部件
  • 算法matlab代码
  • 配送中心选址模型
  • 算法代码

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email