基于蚁群算法求解VRPTW路径规划问题研究

魏子秋 孙明哲

摘  要：目前我国物流业迅速发展，但是同时伴有某些方面的不足，比如：成本控制不足。文章将联系实际情况，同时以配送车辆的运输总成本、总行驶距离和碳排放量为目标函数，并充分考虑实际出现的约束条件，再利用MATLAB软件运行带有时间窗的蚁群算法，对车辆配送路径进行仿真实验，最后寻找到最优配送路径以满足目标函数。通过实验表明，该数学模型和算法可以更好地解决物流配送路径选择的问题，以达到降低物流成本、提高物流效率等目的。

关键词：物流配送;蚁群算法;路径优化

中图分类号：U116.2    文献标识码：A

Abstract： At present， China's logistics industry is developing rapidly， but it is accompanied by some shortcomings， such as insufficient cost control. In this paper， according to the actual situation， taking the total transportation cost， total driving distance and carbon emissions of distribution vehicles as objective functions， and taking full account of the actual constraints， the MATLAB software is used to run ant colony algorithm with time window to simulate the vehicle distribution path， and finally find the optimal distribution path to meet the objective function. Experiments show that the mathematical model and algorithm can better solve the problem of logistics distribution route selection， so as to reduce logistics costs and improve logistics efficiency.

Key words： logistics distribution; ant colony algorithm; path optimization

0  引  言

在1959年，Dantzing和Ramser 在經过实验和思考后，首次提出配送车辆路径优化问题[1]。在物流运输中配送是重要的环节，准确选择配送车辆路径能有效缩短运输时间、降低运输成本、满足顾客需求等目的。

关于寻找最优配送线路问题已经成为研究的热点之一[2]。最初蚁群算法是研究旅行商的问题[3]，现在已经广泛应用到许多寻找最优解的问题中。例如：郑娟毅等利用蚁群算法寻找配送车辆路径最优的问题[4]，张银玲等利用蚁群算法寻找移动机器人的最优路径[5-6]，鲁丰玲、白俊强等通过蚁群算法寻找无人机最优路径[7-8]，蚁群算法被应用到解决旅游最优路线的问题中[9-10]，Wang Yong等[11]利用蚁群算法解决VNF布局网络问题，张肖琳等[12]在绿色环保角度，对油耗、污染物排放等因素进行约束构建路径优化模型，利用蚁群算法找出最优路径。可以看出蚁群算法虽然可以解决许多实际问题，但还存在不足，于是提出最大最小蚂蚁系统[13]以及混合蚂蚁系统[14]等方法，都在一定程度上提高了运算效率。虽然大多数文献已经对路径优化进行了充分研究，但本文结合时间窗约束建立总成本最小、总行驶距离最短、碳排放量最低的多目标优化模型，通过蚁群算法对设置的参数和约束条件进行求解，得出最优的配送路线。

1  物流配送路径模型

该问题的一般提法是[15]：已知配送中心的横、纵坐标，所有客户的横、纵坐标和需求量，车辆必须从配送中心开始出发对每个客户进行配送，对每个客户进行配送完毕之后再回到配送中心，在车辆额定容量和行驶距离等约束条件下，使得目标（如成本最少、路程最短等）达到最优。在实际情况中，除了成本外还要考虑其他许多因素，车辆路径优化问题大多数都是多目标优化，求解难度更大，所以研究带有时间窗的路径优化问题意义重大。

1.1  问题的描述

已知某物流公司的配送中心及客户的横、纵坐标，同时由相同属性（油耗、载重、速度）的车辆从配送中心出发向各自回路中的客户进行货物配送，配送完毕之后再回到配送中心，每个客户所需的货物量不超过车辆运载能力，并且每个需求点只能在配送时间窗内由一辆车配送，每辆车所服务的客户需求之和不超过车辆的载重量。

在实际情况下，为达到配送中的总运输成本最低、总行驶距离最短、碳排放量最低等目的而提出的问题。

1.2  建立多目标数学模型

1.2.1  参数和变量

由此建立数学模型，用O表示配送中心仓库;有n辆相同的车辆，给每条回路上的I个客户提供货物;用a表示车辆的固定成本;用N表示确定所需的车辆数目，每辆车的编号为i，并且只在一条回路上行驶;用a表示车辆在客户j和k的配送过程中所产生的运输成本;用b表示客户点j和配送中心O之间的产品总量;每辆车i的路径为c;车辆i服务于客户j为c;用I=0表示车辆i没有可服务的客户;用d表示在车辆i的配送回路中，两个相邻客户所配送需要的路程;用d表示车辆i从第I个客户行驶到配送中心O的距离;用d表示客户j和k之间的距离;用e表示车辆i配送结束之后回到配送中心所剩下的货物总量;用L表示车辆i行驶的最远路程;用p表示车的碳排放量;用Q表示在车辆i的回路中，客户j所需要的货物量;用w表示车辆i的额定载重;用ET表示车辆i分别给客户j最早的配送时间;用LT表示车辆i分别给客户j最晚的配送时间;用WT表示车辆i从客户j出发的时间;用RT表示车辆i到达客户j的时间;用α和β分别表示硬、软时间窗惩罚成本系数;用UT表示车辆i对客户j所服务的时间;用T表示车辆i从客户j配送完毕后，再出发到客户k所耗费的时间;用v表示车辆在配送过程中的速度;用S表示所有车辆进行配送的总路程;用Z表示所有车辆在配送过程中的运输总成本;用F表示所有车辆总的碳排放量水平。

为了满足客户点j设置的配送时间窗，在对客户点j进行配送时，配送车辆到达时间RT必须满足下式：ET≤RT≤LT;

配送车辆i在客户j到k间行驶的时间：T=d/v;

配送车辆i从客户j出发抵达下一个客户点k的时间：RT=WT+UT+T;

时间窗惩罚函数系数用集合H表示：H=α， β。

1.2.2  目标函数

由描述的问题和分析可知，在进行物流配送时应首先考虑总成本最小，其中包括运输成本、车辆固定成本、违时惩罚成本;同时又要考虑最优路径的选择和碳排放量最低，从而得到多目标函数：

minZ=a×sign

I+a×N+max

ET

-RT， 0+max

RT

-LT， 0       （1）

minS=

d+d×sign

I                                   （2）

minF=p×d×sign

I                                    （3）

目標函数（1）表示使车辆在最佳运输路径上的运输总成本最小（前两项为运输成本，后两项为惩罚成本）;目标函数（2）表示使车辆对所有客户完成配送并返回配送中心后，进行配送的总路程最短;目标函数（3）表示使车辆的排放量降到最低，以降低环境污染。

1.2.3  约束条件

对上述目标函数进行约束：

Q≤w                                                （4）

d+d×sign

I≤L                                       （5）

0≤I≤m                                                （6）

I=m                                                 （7）

C=

C

|C∈V

，V

，…，

V， j=1，2，…，

I                                  （8）

C∩C=φ， ?≠j                                            （9）

e=0， ?∈m                                             （10）

sign

I=

（11）

N≤n                                                （12）

RT∈

ET，

LT    i∈N， j∈m                                    （13）

约束条件（4）表示为车辆的容量条件，每辆车所装载的货物在小于等于额定载重量的情况下，满足相应回路中客户的总需求;约束条件（5）表示每个子回路中的车辆配送路程不超过所有车辆总配送路程;约束条件（6）表示配送车辆在各自的回路中所服务的客户不超过客户总量;约束条件（7）表示所有需求车辆所服务的客户总数等于实际的客户总数，保证所有客户都能得到服务;约束条件（8）表示每辆车所服务客户的集合;约束条件（9）表示每个客户被有且仅有一辆车所服务;约束条件（10）确保所有运行车辆空车返回配送中心;约束条件（11）表示第i辆车是否参与服务;约束条件（12）表示有进行配送任务的车辆数要小于等于总的车辆数;约束条件（13）表示车辆在符合相应客户的时间窗内进行配送。

2  蚁群算法

Marco Dorigo通过对蚂蚁群体觅食的研究，随后在1992年提出蚁群算法[16]（Ant Colony Optimization， ACO），它是一种模拟仿真寻找最优路径的算法，该算法具体是模仿蚂蚁在寻找食物过程中分泌一种特殊的可随着时间的推移而挥发的信息素来引导其他蚂蚁选择此路径的行为，经过一段时间后寻找到最优路径的目的。

2.1  参数设置

蚁群算法中有最基本的6个参数：用m表示蚂蚁的总数;用Q表示蚂蚁一次循环释放信息素的总量;用t表示在运算过程中最大的迭代次数;用α表示信息素因子;用β表示启发函数因子;用ρ表示信息素挥发因子。

2.2  构建行动路径

在构建路径的过程中，用轮盘赌法选择蚂蚁要到达的下一座城市。计算公式如下：

p=

式中：用i表示起点，j表示终点;ηt=1/d表示i和j之间距离的倒数，ηt是启发函数;用τt表示在时间t时刻，起点i到终点j之间所包含的信息素浓度大小;用allowed表示蚂蚁k还没有到达过剩下城市的集合;此路径上的信息素浓度大小由两地距离长短控制，两地距离越短，信息素浓度越大，选择此路径的几率就会越大，反之，距离越远浓度越小;从公式可以看出信息素因子α决定信息素浓度，启发函数因子β决定转移期望对蚂蚁k从i到j可能性的贡献程度。

2.3  更新信息素

蚂蚁释放的信息素具有随着时间挥发的特性。因此，在每一次迭代完成后，都要将蚂蚁所带来的相关信息和信息素浓度进行更新，规则为：

τt+1=τt×1-ρ+Δτ， 0<ρ<1

Δτ=Δτ

式中：1-ρ表示信息素残留系数;Δτ表示迭代过程中，路径ij上信息素增量;Δτ表示第k只蚂蚁在本次迭代中留在ij上的信息素量，如下式：

Δτ=

式中：L表示螞蚁k所经过的所有路径之和。

2.4  判断迭代是否终止

是否达到迭代次数可以判断仿真实验是否终止。一次迭代就是指m只蚂蚁都走完所有的路径，即存在m个搜索路径。在所有的路径中选择最短的路径，做出这一次迭代的可视化结果，更新信息素;然后将新的最短路径与上一次的最短路径进行对比，同时增加1次迭代次数;最后计算当前迭代次数与最开始设置的迭代次数相差多少次，若正好相等则停止迭代，否则进行下一次迭代。

3  仿真实验

某配送中心（编号0）有额定载重为1 000kg的配送车辆6辆，需在42天内（1 008h）将货物派送至19个客户点，从0

～19依次对配送中心仓库和19个客户点进行编号，其中配送中心以及各个客户点之间的横、纵坐标，客户的需求量、左时间窗、右时间窗和所对应的服务时间如表1所示。

将表1中的数据换成矩阵形式后，导入到MATLAB中，并且对算法中的参数进行多轮假设，得出最优的参数数值为：蚂蚁总数量m=35，释放信息素常量Q=100，运算最大迭代次数t=100，信息素因子α=1，启发函数因子β=3，信息素挥发因子ρ

=0.4，等待时间重要程度因子γ=2，时间窗跨度重要程度因子δ=3。

对参数设置完毕后，将表1中数据与参数值同时输入到程序中，经过100次仿真实验，得到6种结果，其中798.4072km为最优路径，计算过程如表2所示。

得出4条车辆最优配送回路路线：

配送路线1：0→5→13→19→10→14→12→2→0，运输量为835kg;

配送路线2：0→17→18→3→11→9→6→1→0，运输量为1 000kg;

配送路线3：0→7→4→0，运输量为293kg;

配送路线4：0→8→15→16→0，运输量为455kg。

4条配送回路路线如图1所示：

图1为MATLAB运行出的相对最优配送路径，蓝点为车辆配送中心，蓝色线为配送路线1，红色线为配送路线2，绿色线为配送路线3，橙色线为配送路线4。

在原始的算法中没有对顾客服务时间的约束，会增加惩罚成本并且大幅降低顾客满意度，此方法将配送车辆在时间约束下计算出相对最优的路径，更好地降低物流成本，提高客户满意度等优势。可见，带有时间窗的蚁群算法更加符合企业的成本控制和顾客的需求，使该模型的配送效益最高，适用性更强。

4  结  论

如今我国的物流产业正在进行迅速的发展，但不可避免会出现成本控制等问题，所以合理规划最优路径以降低成本显得尤为重要。此方法在车辆的行驶距离、物流成本、碳排放量等目标基础上，做了数学优化模型，并利用MATLAB运行带有时间窗的蚁群算法寻找车辆的最优路径，达到车辆行驶距离、运输成本、碳排放量最低的目标，此计算结果在一定程度上对实际情况有参考价值。

参考文献：

[1] Dantzig G B， Ramser J H. The truck dispatching problem[J]. Management Science， 1959，6（1）：80-91.

[2] 罗梓瑄，刘学文. 基于蚁群算法的物流配送路径优化研究[J]. 重庆工商大学学报（自然科学版），2020，37（4）：89-94.

[3] 李炳宇，萧蕴诗. 基于模式求解旅行商问题的蚁群算法[J]. 同济大学学报（自然科学版），2003（11）：1348-1352.

[4] 郑娟毅，付姣姣，程秀琦. 面向物流车辆路径规划的自适应蚁群算法[J]. 计算机仿真，2021，38（4）：477-482.

[5] 张银玲，牛小梅. 蚁群算法在移动机器人路径规划中的仿真研究[J]. 计算机仿真，2011，28（6）：231-234.

[6] 张晓玲，罗印升，张宝峰，等. 基于蚁群算法的移动机器人路径规划[J]. 激光杂志，2016，37（11）：80-83.

[7] 魯丰玲. 基于蚁群算法的无人机舰机协同任务规划[J]. 舰船科学技术，2019，41（18）：67-69.

[8] 白俊强，柳长安. 基于蚁群算法的无人机航路规划[J]. 飞行力学，2005（2）：35-38.

[9] 万慧云，蒋艳. 基于蚁群算法的5A景点旅游路线规划问题研究[J]. 软件导刊，2019，18（4）：141-144.

[10] 李梦丹. 基于蚁群算法西安旅游路线的优化研究[J]. 价值工程，2020，39（20）：136-137.

[11]  Wang Yong， Han Zunpu. Ant colony optimization for traveling salesman problem based on parameters optimization[J]. Applied Soft Computing， 2021，107（2）：107439.

[12] 张肖琳，梁力军，张梦婉. 绿色物流配送路径优化研究——以京东配送为例[J]. 价格月刊，2020（8）：64-69.

[13]  Stutzle T. MAX-MIN ant system[J]. Future Generation Computer Systems， 2000，16（8）：899-914.

[14]  Gambardella L M， Dorigo M. An ant colony system hybridized with a new local search for the ordering problem[J]. Informs Journal of Computing， 2000，12（3）：237-255.

[15]  Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research， 1987，35（2）：254-265.

[16]  Marco Dorigo. Using transputers to increase speed and flexibility of genetics-based machine learning systems[J]. Microprocessing and Microprogramming， 1992，34（1-5）：147-152.