基于蚁群算法的图书物流中心配送路径规划

计三有,王 星

(武汉理工大学物流工程学院,湖北 武汉 430063)

车辆路径问题(Vehicle Routing Problem,VRP)最早由G.Dantzig和 J.Ramser于1959年提出[1].VRP问题已经被证明是NP-Hard问题,针对它的求解算法主要有精确算法和智能算法两类.由于精确算法在有限的时间内并不是总能得到合适的解,因此,在实际应用中,智能算法要更有效.本文采用一种新型的智能算法——蚁群算法(Ant Colony Optimization,ACO)进行求解.

1 图书物流车辆路径规划模型

图书因其商品的特殊性质,客户的需求一般体现为高频率、小批量的特点.在这种情况下,单个客户的需求量通常较小,多个客户需求量之和才能达到一部车辆的有效装载容量.若仍采用不同客户需求分车配送的方式,则大大降低了资源利用率.[2-3]

1.1 模型描述及优化

为简化建模过程,优化模型结构,特对物流车辆路径规划模型做如下设定:1)配送中心的图书储备量能满足所有需求点的需求,不存在缺货情况;2)车辆顺序地为需求点提供配送服务,只有卸货不带取货;3)每个客户需求点只被一辆车服务一次;4)配送车辆由配送中心出发,服务结束后返回配送中心;

1.2 车辆路径规划模型

根据模型描述及相关假设,基于零担运输策略的图书物流车辆规划模型建立如下:

其中:N为客户需求点总数;k代表车辆编号,且k∈{1,2,…,K};dij为需求点i与j之间的距离,其中,i≠j且i,j∈{1,2,…,N};qi为客户点i的需求量;Ck为车辆k的最大装载量;xijk为判断系数,且

式(1)为优化目标表达式,使配送路径的总里程数尽可能小;式(2)、(3)表示每一辆参与配送的车辆都从配送中心出发,并最终回到配送中心;式(4)、(5)表示每个需求点被且仅被一辆车服务一次;式(6)表示容量约束,保证每辆车的实际装载量都不超过其容量.

2 最短距离的改进

目前在VRP问题的研究中,任意两个客户点间的最短距离,通常采用两点间的直线距离.这样的简化与实际路程并不吻合[5].

城市交通路况比较复杂,两点之间的距离并非是直线距离,而是行车路线中各段路程的代数和,有的时候实际距离与直线距离相差非常大.

针对该问题,本文结合实例在计算任意两个客户点之间的最短距离时采取通过GPS导航系统取得的路程数据为基础,进行优化计算.

3 蚁群算法

蚁群算法最早是由Marco Dorigo于1992年在他的博士论文中提出,是一种模仿蚂蚁觅食过程的模拟进化算法[6].

为模拟蚂蚁选择路径及路径上信息素的更新过程,定义如下符号:m为蚂蚁数量;dij为城市i,j之间的距离;ηij是路段(i,j)的能见度,反映由城市i转移到城市j的启发程度,ηij=1/dij;τij为t时刻在ij路径上信息素的残留量.则蚂蚁从城市i转移到城市j的概率

式中:α和β为两个参数,分别表示已积累的信息和启发信息在蚂蚁选择路径时的相对重要性.tempk(k=1,2,…,m)是为满足容量约束的配送点的集合,表示在t时刻蚂蚁k可选的待访问点.

信息素更新规则如下式所示:

其中,ρ是为了避免累积的信息素淹没启发信息引入的挥发系数,0<ρ<1;Δ τij(t)表示本次循环中(i,j)路段的信息素增量.[7～8]

4 配送实例分析

本配送实例中,相关配送点数据存入matlab工作空间,在算法优化过程中调用.

根据模型建立蚁群算法程序,参数设置为:蚂蚁数m=15,信息素比重α=1,启发信息比重β=4,挥发系数ρ=0.1,进化次数n gen=100.用matlab7.0编程求解,程序运行结果如图1所示.

最终线路:线路一,1→22→16→13→17→19→14→1;线路二,1→8→2→3→18→4→9→1;线路三,1→10→5→6→12→7→1;线路四,1※21→20→15→11→1.运输总距离为178.9 km.

经统计计算,该次配送的实际运输距离为207.0 km.与之相比,经过优化的配送路径能减少13%的配送里程.

图1 程序运行结果

5 结论

结合图书配送的特点,在配送车辆装载容量有限情况下,建立以配送总里程最短为目标的图书物流配送路径规划模型,开发了符合模型描述的蚁群算法程序.针对实例的仿真研究表明,优化结果能降低配送里程,提高配送效率,减少配送决策时间.

[1]Dantzig G,Ramser J,The trunk dispatching problem[J],Management Science,1959(6):80-91.

[2]张美娟.图书物流新发展:图书物流配送[J].出版发行研究,2000(6):43-44.

[3]胡 勇,郁阳刚.关于图书物流配送的研究[J].商场现代化,2007(35):108.

[4]龚延成,郭晓汾,尤晓铃,等.基于遗传算法的物流配送车辆调度间题研究[J].数学的实践与认识,2004,34(6):93-97.

[5]陈 昊,宁红云.基于集合运算的最短路径搜索算法[J].计算机工程,2007,33(20):199-203.

[6]Colorni A,Dorigo M,M aniezzo V,et al.Distributed optimization by ant colonies[C]//Proceedings of the 1st European Conference on Artificial Life,1991:134-142

[7]王 颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报,2002,14(1):31-33.

[8]Bell E,MeMullen R.Ant colony optimization techniques for the vehicle routing problem[J].Advanced Engincedng Informaties,2004,18:41-44: