基于蚁群算法求解VRPTW路径规划问题研究
- 格式：docx
- 大小：1.39 MB
- 文档页数：13
基于蚁群算法求解VRPTW路径规划问题研究
作者：魏子秋 孙明哲
来源：《物流科技》2022年第03期
摘 要：目前我国物流业迅速发展，但是同时伴有某些方面的不足，比如：成本控制不足。文章将联系实际情况，同时以配送车辆的运输总成本、总行驶距离和碳排放量为目标函数，并充分考虑实际出现的约束条件，再利用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∈
為了满足客户点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）
