科技和产业

算法:机场终端VRPTW的多目标混合优化算法框架
1.初始化:
1.1初始化车辆初始状态和货运点节点状态,所有货运点节点未被服务
1.2设定到达时间函数t_i为无穷大,并初始化每辆车的载货量为0
2.应用Dijkstra算法计算最短路径
2.1使用Dijkstra算法计算机场货运站到每个货运点的最短路径
2.2根据路径更新到达时间函数t_i和载货量
3.遗传算法优化初始解
3.1基于Dijkstra生成的初始解,应用遗传算法(GA)交叉和变异操作,产生新的路径解
3.2评估新解的成本,并更新最优解
4.模拟退火算法(SA)局部搜索
4.1在遗传算法生成的解上执行模拟退火算法,进一步优化路径成本,降低时间窗惩罚
4.2根据温度衰减策略接受或拒绝新的解
5.自适应大邻域搜索(ALNS)优化
5.1应用ALNS动态调整解空间,对车辆路径进行大范围扰动搜索
5.2重新评估扰动后的解,若成本更低,则接受新解
6.综合多目标优化
6.1结合遗传算法、模拟退火和ALNS的结果,优化运输成本和时间窗惩罚的加权目标函数
7.输出最优解
7.1输出最小总成本的车辆路径集合R,包含每辆车的路径和到达时间

算法:机场终端VRPTW的多目标混合优化算法框架
1.初始化:
1.1初始化车辆初始状态和货运点节点状态,所有货运点节点未被服务
1.2设定到达时间函数t_i为无穷大,并初始化每辆车的载货量为0
2.应用Dijkstra算法计算最短路径
2.1使用Dijkstra算法计算机场货运站到每个货运点的最短路径
2.2根据路径更新到达时间函数t_i和载货量
3.遗传算法优化初始解
3.1基于Dijkstra生成的初始解,应用遗传算法(GA)交叉和变异操作,产生新的路径解
3.2评估新解的成本,并更新最优解
4.模拟退火算法(SA)局部搜索
4.1在遗传算法生成的解上执行模拟退火算法,进一步优化路径成本,降低时间窗惩罚
4.2根据温度衰减策略接受或拒绝新的解
5.自适应大邻域搜索(ALNS)优化
5.1应用ALNS动态调整解空间,对车辆路径进行大范围扰动搜索
5.2重新评估扰动后的解,若成本更低,则接受新解
6.综合多目标优化
6.1结合遗传算法、模拟退火和ALNS的结果,优化运输成本和时间窗惩罚的加权目标函数
7.输出最优解
7.1输出最小总成本的车辆路径集合R,包含每辆车的路径和到达时间

编号	经度	纬度	名称	收货量/t	最早可接受送达时间	最晚可接受送达时间
0	104.695 300	31.483 218	机场货运站	0.00	9:30	13:40
1	104.653 549	31.449 708	凝晖物流园	0.86	9:30	12:20
2	104.658 334	31.450 201	富发物流园	1.04	9:30	12:20
3	104.711 329	31.507 312	龙溪物流园	1.08	9:20	12:40
4	104.655 736	31.465 609	力展物流(绵阳二配送中心)	1.20	9:00	12:40
5	104.700 480	31.528 545	力展物流(绵阳高水配送中心)	0.89	9:10	12:20
6	104.661 501	31.450 344	绵阳市美福地物流有限公司	0.94	9:00	11:30
7	104.624 927	31.462 037	远成集团(辽宁大道)	1.07	9:10	11:20
8	104.660 218	31.447 921	联合运通物流	1.04	9:10	12:50
9	104.658 753	31.432 362	绵阳传化智慧物流枢纽	1.08	9:20	11:30
10	104.594 035	31.438 162	川江货运物流园	1.11	9:20	11:20
11	104.731 633	31.434 890	宇鑫物流	1.20	9:00	11:30
12	104.642 069	31.474 815	绵阳市三里包装有限公司物流分公司	0.81	9:30	11:30
13	104.729 122	31.485 245	京东物流(绵阳涪城快运集配站)	0.98	9:20	11:30
14	104.733 889	31.470 016	四川兄弟联物流有限公司(先锋路店)	0.80	9:10	11:30
15	104.729 924	31.435 614	双九快运有限公司	1.14	9:20	12:20
16	104.725 646	31.492 773	绵阳华青物流有限公司	0.94	9:30	11:40
17	104.638 159	31.449 705	乾坤物流(兴业南路)	1.09	9:20	12:40
18	104.685 952	31.532 575	韵达快递	1.04	9:20	11:40
19	104.767 688	31.432 500	中国邮政速递物流(经开区营业部)	0.87	9:00	12:40
20	104.644 156	31.473 176	绵阳安运物流有限公司	0.96	9:20	11:40
21	104.729 567	31.507 167	八维物流	0.92	9:20	11:30
22	104.726 400	31.448 914	良伟快运货运	0.81	9:30	12:40
23	104.731 741	31.434 452	力展物流(绵阳毅德店)	0.99	9:00	11:40
24	104.730 540	31.435 464	云聚物流	0.96	9:20	12:10
25	104.723 855	31.441 490	德邦快递(绵阳涪城区分部)	0.94	9:00	11:30
26	104.679 433	31.547 743	余氏东风物流(高水龙门石马点)	1.18	9:20	11:40
27	104.681 532	31.418 067	顺丰速运有限公司绵阳快运营业点	1.18	9:20	12:40
28	104.731 628	31.434 778	恒兴物流	1.19	9:10	11:40
29	104.790 848	31.391 235	力展物流(绵阳经开区配送中心)	0.82	9:00	11:20
30	104.701 845	31.523 540	绵阳鑫秀云物流	1.15	9:10	12:30
31	104.665 494	31.449 687	起航物流	0.99	9:30	11:10
32	104.654 419	31.486 598	四川虎威物流有限公司	0.93	9:30	11:20
33	104.659 648	31.449 723	四川三志物流供应链管理有限公司	1.00	9:00	12:10
34	104.767 257	31.417 928	四川省烟草公司绵阳市公司物流中心	0.94	9:00	11:30
35	104.669 388	31.493 075	中国邮政速递物流(九盛路店)	1.10	9:00	11:20

编号	经度	纬度	名称	收货量/t	最早可接受送达时间	最晚可接受送达时间
0	104.695 300	31.483 218	机场货运站	0.00	9:30	13:40
1	104.653 549	31.449 708	凝晖物流园	0.86	9:30	12:20
2	104.658 334	31.450 201	富发物流园	1.04	9:30	12:20
3	104.711 329	31.507 312	龙溪物流园	1.08	9:20	12:40
4	104.655 736	31.465 609	力展物流(绵阳二配送中心)	1.20	9:00	12:40
5	104.700 480	31.528 545	力展物流(绵阳高水配送中心)	0.89	9:10	12:20
6	104.661 501	31.450 344	绵阳市美福地物流有限公司	0.94	9:00	11:30
7	104.624 927	31.462 037	远成集团(辽宁大道)	1.07	9:10	11:20
8	104.660 218	31.447 921	联合运通物流	1.04	9:10	12:50
9	104.658 753	31.432 362	绵阳传化智慧物流枢纽	1.08	9:20	11:30
10	104.594 035	31.438 162	川江货运物流园	1.11	9:20	11:20
11	104.731 633	31.434 890	宇鑫物流	1.20	9:00	11:30
12	104.642 069	31.474 815	绵阳市三里包装有限公司物流分公司	0.81	9:30	11:30
13	104.729 122	31.485 245	京东物流(绵阳涪城快运集配站)	0.98	9:20	11:30
14	104.733 889	31.470 016	四川兄弟联物流有限公司(先锋路店)	0.80	9:10	11:30
15	104.729 924	31.435 614	双九快运有限公司	1.14	9:20	12:20
16	104.725 646	31.492 773	绵阳华青物流有限公司	0.94	9:30	11:40
17	104.638 159	31.449 705	乾坤物流(兴业南路)	1.09	9:20	12:40
18	104.685 952	31.532 575	韵达快递	1.04	9:20	11:40
19	104.767 688	31.432 500	中国邮政速递物流(经开区营业部)	0.87	9:00	12:40
20	104.644 156	31.473 176	绵阳安运物流有限公司	0.96	9:20	11:40
21	104.729 567	31.507 167	八维物流	0.92	9:20	11:30
22	104.726 400	31.448 914	良伟快运货运	0.81	9:30	12:40
23	104.731 741	31.434 452	力展物流(绵阳毅德店)	0.99	9:00	11:40
24	104.730 540	31.435 464	云聚物流	0.96	9:20	12:10
25	104.723 855	31.441 490	德邦快递(绵阳涪城区分部)	0.94	9:00	11:30
26	104.679 433	31.547 743	余氏东风物流(高水龙门石马点)	1.18	9:20	11:40
27	104.681 532	31.418 067	顺丰速运有限公司绵阳快运营业点	1.18	9:20	12:40
28	104.731 628	31.434 778	恒兴物流	1.19	9:10	11:40
29	104.790 848	31.391 235	力展物流(绵阳经开区配送中心)	0.82	9:00	11:20
30	104.701 845	31.523 540	绵阳鑫秀云物流	1.15	9:10	12:30
31	104.665 494	31.449 687	起航物流	0.99	9:30	11:10
32	104.654 419	31.486 598	四川虎威物流有限公司	0.93	9:30	11:20
33	104.659 648	31.449 723	四川三志物流供应链管理有限公司	1.00	9:00	12:10
34	104.767 257	31.417 928	四川省烟草公司绵阳市公司物流中心	0.94	9:00	11:30
35	104.669 388	31.493 075	中国邮政速递物流(九盛路店)	1.10	9:00	11:20

路线编号	路线	收货成本/元	惩罚成本/元	车辆到达各节点的时长/min
路线1	0→27→8→32→16→2→12→20→21→5→0	1 054.31	13.42	0.00→11.05 →16.89 →35.20 →55.80 →77.03 →91.15 →101.95 →123.47 →138.54 →155.34
路线2	0→15→11→10→30→18→26→17→7→0	1 181.04	15.97	0.00→9.35 →9.63 →40.64 →73.59 →87.41 →101.60 →129.40 →143.99 →165.52
路线3	0→1→19→29→9→24→4→6→3→35→0	1 358.39	32.75	0.00→8.17 →24.68 →40.92 →69.66 →88.10 →110.68 →122.96 →146.83 →162.65 →177.49
路线4	0→31→14→33→23→34→25→28→22→13→0	916.76	34.46	0.00→7.03 →17.34 →38.35 →56.93 →72.69 →89.92 →100.90 →112.77 →130.75 →143.68

路线编号	路线	收货成本/元	惩罚成本/元	车辆到达各节点的时长/min
路线1	0→27→8→32→16→2→12→20→21→5→0	1 054.31	13.42	0.00→11.05 →16.89 →35.20 →55.80 →77.03 →91.15 →101.95 →123.47 →138.54 →155.34
路线2	0→15→11→10→30→18→26→17→7→0	1 181.04	15.97	0.00→9.35 →9.63 →40.64 →73.59 →87.41 →101.60 →129.40 →143.99 →165.52
路线3	0→1→19→29→9→24→4→6→3→35→0	1 358.39	32.75	0.00→8.17 →24.68 →40.92 →69.66 →88.10 →110.68 →122.96 →146.83 →162.65 →177.49
路线4	0→31→14→33→23→34→25→28→22→13→0	916.76	34.46	0.00→7.03 →17.34 →38.35 →56.93 →72.69 →89.92 →100.90 →112.77 →130.75 →143.68

路线编号	路线	收货成本/元	惩罚成本/元	车辆到达各节点的时长/min
路线1	0→27→9→17→12→26→18→5→30→0	893.68	0	0.00→11.05 →15.08 →31.01 →46.04 →70.22 →81.02 →95.00 →106.25 →121.95
路线2	0→11→28→24→22→14→13→16→21→3→0	1 002.80	0.59	0.00→11.05 →15.08 →31.01 →46.04 →70.22 →81.02 →95.00 →106.25 →121.95
路线3	0→35→32→6→31→8→1→10→7→20→0	1 117.30	0	0.00→4.04 →6.43 →23.57 →33.45 →43.65 →54.55 →73.64 →88.18 →102.59 →120.77
路线4	0→19→29→34→23→15→25→33→2→4→0	815.70	0	0.00→13.34 →20.98 →35.27 →49.23 →58.95 →70.16 →90.81 →100.41 →113.01 →129.77

路线编号	路线	收货成本/元	惩罚成本/元	车辆到达各节点的时长/min
路线1	0→27→9→17→12→26→18→5→30→0	893.68	0	0.00→11.05 →15.08 →31.01 →46.04 →70.22 →81.02 →95.00 →106.25 →121.95
路线2	0→11→28→24→22→14→13→16→21→3→0	1 002.80	0.59	0.00→11.05 →15.08 →31.01 →46.04 →70.22 →81.02 →95.00 →106.25 →121.95
路线3	0→35→32→6→31→8→1→10→7→20→0	1 117.30	0	0.00→4.04 →6.43 →23.57 →33.45 →43.65 →54.55 →73.64 →88.18 →102.59 →120.77
路线4	0→19→29→34→23→15→25→33→2→4→0	815.70	0	0.00→13.34 →20.98 →35.27 →49.23 →58.95 →70.16 →90.81 →100.41 →113.01 →129.77

基于多目标优化算法的机场终端VRPTW研究

PDF下载

黄春丽 , 吴永强

科技和产业 | 科技创新 2025,25(4): 58-63

收起

科技和产业 | 科技创新 2025, 25(4): 58-63

基于多目标优化算法的机场终端VRPTW研究

全屏

黄春丽, 吴永强

作者信息

中国民用航空飞行学院机场学院, 四川广汉 618307

黄春丽(2000—),女,山东临沂人,硕士研究生,研究方向为路径规划;

吴永强(1969-),男,四川峨眉人,博士,副教授,研究方向为物流规划。

Research on Airport Terminal VRPTW Based on Multi-objective Optimization Algorithm

Chunli HUANG, Yongqiang WU

Affiliations

Air Traffic Management College, Civil Aviation Flight University of China, Guanghan 618307, Sichuan, China

出版时间: 2025-02-25

文章导航

摘要

收起

针对机场终端带有时间窗的车辆路径问题(VRPTW),提出一种基于遗传算法(GA)、模拟退火(SA)和自适应大邻域搜索(ALNS)的多目标混合优化算法框架。该模型综合车辆派遣成本和时间窗惩罚成本的最小化,并考虑揽货中心资源共享的影响。通过K-Means聚类、模拟退火优化站点遍历次序以及遗传算法优化货运点货物量级分类,实现算法的高效求解。结果表明,该算法降低了揽货中心16.88%总成本,验证了模型的有效性和实用性。

关键词

VRPTW / 路径规划 / 时间窗 / 混合算法 / 机场终端

Abstract

收起

A multi-objective hybrid optimization algorithm framework was proposed for the vehicle routing problem with time windows (VRPTW) at airport terminals, based on genetic algorithm (GA), simulated annealing (SA) and adaptive large neighborhood search (ALNS). Aiming to minimize both vehicle dispatch costs and time window penalty costs, the impact of resource sharing at cargo centers was considered. Through the use of K-means clustering, simulated annealing for optimizing the order of site visits, and genetic algorithm for classifying freight point cargo levels, the algorithm efficiently solving the problem was achieved. Experimental results show that the algorithm reduces the total cost of the cargo center by 12.46%, demonstrating the effectiveness and practicality of the model.

Key words

VRPTW / route planning / time window / Dijkstra algorithm / airport terminal

引用本文

黄春丽, 吴永强. 基于多目标优化算法的机场终端VRPTW研究. 科技和产业, 2025 , 25 (4) : 58 -63 .

Chunli HUANG, Yongqiang WU. Research on Airport Terminal VRPTW Based on Multi-objective Optimization Algorithm[J]. Science Technology and Industry, 2025 , 25 (4) : 58 -63 .

正文

收起

在现代物流与运输领域,车辆路径优化问题(vehicle routing problem, VRP)一直是研究的核心课题,尤其是带有时间窗约束的车辆路径问题(vehicle routing problem with time windows, VRPTW),其核心目标是在满足车辆容量和时间窗约束的前提下,优化车辆路线以最小化总运输成本^[1]。近年来,元启发式算法在解决VRPTW问题中表现出显著的效果。这些算法通过引入多样化的启发式策略,增强了全局搜索能力,缓解了局部最优问题^[2]。禁忌搜索算法(tabu search, TS)是较早应用于VRPTW问题的元启发式算法之一。通过引入禁忌表来记录已经访问的解,TS避免了循环搜索和陷入局部最优,显著提高了局部搜索的效率^[3]。模拟退火算法(simulated annealing, SA)模仿物理退火过程,非线性问题中表现尤为突出^[4]。遗传算法(genetic algorithm, GA)基于自然选择和遗传机制,通过种群初始化、选择、交叉和变异操作,能够有效提高解的质量^[5]。例如,Azi等^[6]提出的单车路径问题精确算法为解决时间窗约束下的多路径规划提供新的方法。此外,蚁群算法(ant colony optimization, ACO)通过模拟蚂蚁觅食的行为,利用信息素的浓度来引导路径选择,已被成功应用于复杂的路径优化问题^[7]。粒子群优化算法(particle swarm optimization, PSO)模拟了群体智能,通过个体最优与群体最优的协同作用来寻找最优解^[8],在车辆路径问题的求解中展现出强大的竞争力。

然而,尽管这些元启发式算法在解决VRPTW问题中表现出不同的优势,但仍然存在一定的局限性。例如,GA^[9]、SA^[10]和K-means^[11]等算法在求解大规模问题时,可能会面临计算时间长、解的质量不稳定等问题。因此,近年来,混合元启发式算法成为研究的重点。通过结合多种算法的优势,混合算法旨在提高求解的效率和解的质量。例如,Jabir^[12]设计了一种混合蚁群算法和变邻域搜索算法,用于解决绿色车辆路径问题,显著提升了解的质量和效率。类似地,Kallehauge^[13]等提出的AGVNS算法在解决多机场货运站车辆路径问题(multi-depot vehicle routing problem, MDVRP)中展现了较高的灵活性和效率。

尽管上述元启发式算法在解决VRPTW问题中取得一定的成果^[14],但它们在处理更大规模、更复杂的实际问题时,仍面临计算效率低下和解的质量不稳定等挑战。因此,近年来,多种元启发式算法的混合方法得到了广泛关注。这些方法通过结合不同算法的优势,旨在提升求解效率和解的质量。

为了解决这些问题,本文提出以下内容:提出一种基于遗传算法、模拟退火算法与自适应大邻域搜索算法的多目标混合优化框架,通过构建多目标优化模型,在求解过程中同步考虑运输成本和时间窗惩罚,保证解决方案的经济性与实用性;通过共享种群与自适应策略,确保GA、SA和ALNS算法的高效协同工作,从而显著提升了求解速度和解的质量;以绵阳南郊机场为具体实例,以混合算法为框架,结合具体实例数据进行数据分析和优化。

1 机场终端VRPTW优化模型

收起

1.1 问题描述

VRPTW包括设计一组路线,以最小化车队的总行驶距离。车辆的载货量一定且车辆数量有限^[15],路线输送的总负载不能超过车辆的容量。每个货运点必须在其时间范围内只接受一次服务,然而像任何其他路口一样,货运点可以在没有服务的情况下被多次遍历。

1.2 模型假设

(1)每个货运点的货物量已知且确定。

(2)揽收车车型一致,且载重量已知。

(3)在时间窗和载重量允许的情况下,揽收车可以前往多个收集点。

(4)当车辆满载时回到机场货运站清空,并前往其他货运点收集,直到所有节点被服务。

(5)任意2个货运点之间的距离已知,车辆的速度固定。

(6)揽收车的固定成本已知,并且单位距离的行驶成本已知。

(7)交通状况良好,没有转向限制,不考虑单行道。

1.3 目标函数及约束条件:最小化揽收成本

1.3.1 目标函数

待揽收货运点有n个

$(\mathit{i},\mathit{j}=\mathrm{1,2},\dots,\mathit{n})$

;i或j=0表示机场货运站;货运点i的需求为q_i;货运点i 期望的最早揽收时间和最晚揽收时间分别为e_i、l_i;由货运点i到货运点j的运输时间、运输距离分别为t_i、c_i;到达货运点之后的停留时间(作业时间)为f_i;可供使用的车辆共m辆(k=1,2,…,m),每辆车的最大载重量为Q;第k辆车到达货运点i的时间为s_jk,其中s_0k为车辆k从机场货运站驶出;车辆运输的可变成本为α,元/tkm,固定成本为β,元/次;提前或延后到达将产生相应的单位惩罚成本,分别为λ、μ;x_ijk车辆k由货运站i到货运站j(x_ijk=0,1,其中

$\mathit{i},\mathit{j}=\mathrm{0,1},2,\dots,\mathit{n};\mathit{k}=\mathrm{1,2},\dots,\mathit{m})$

。任一货运站

$\mathit{j}(\mathit{j}\ne 0)$

存在m个“到达时间”,其中只有一个大于0,其余m-1个全部等于0,揽收车辆到达货运点j 提供服务的时间为z_j。并引入非负辅助变量Δ_i和

${\mathit{\theta }}_{\mathit{i}},\mathit{i}=1,\dots,\mathit{n},$

且

${\mathit{\Delta }}_{\mathit{i}}\ge 0$

${\mathit{\theta }}_{\mathit{i}}\ge 0$

。Δ_i表明车辆k在提前到达i的非负差值,同理θ_i 表明车辆k在延后到达i的非负差值。车辆揽收完毕后回到货运站的时间为r_k。普货收运的总成本U为

(1)

$\mathit{m}\mathit{i}\mathit{n}\mathit{U}=\mathit{\alpha }\sum _{\mathit{k}=1}^{\mathit{m}}\sum _{\mathit{i}=0}^{\mathit{n}}\sum _{\mathit{j}=0}^{\mathit{n}}{\mathit{c}}_{\mathit{i}\mathit{j}}{\mathit{x}}_{\mathit{i}\mathit{j}\mathit{k}}+\mathit{\beta }\sum _{\mathit{k}=1}^{\mathit{m}}\sum _{\mathit{j}=1}^{\mathit{n}}{\mathit{x}}_{0\mathit{j}\mathit{k}}+$

$\sum _{\mathit{i}=1}^{\mathit{n}}(\mathit{\lambda }{\mathit{\Delta }}_{\mathit{i}}+\mathit{\mu }{\mathit{\theta }}_{\mathit{i}})$

1.3.2 约束条件

(1)车辆容量约束:

(2)

$\sum _{\mathit{i}=1}^{\mathit{n}}({\mathit{q}}_{\mathit{i}}\sum _{\mathit{j}=1}^{\mathit{n}}{\mathit{x}}_{\mathit{i}\mathit{j}\mathit{k}})\le \mathit{Q},\mathit{ }\mathit{k}=\mathrm{1,2},\dots,\mathit{m}$

(2)每个货运点都有且仅有一辆车为其服务一次:

(3)

$\sum _{\mathit{i}=0}^{\mathit{n}}\sum _{\mathit{k}=1}^{\mathit{m}}{\mathit{x}}_{\mathit{i}\mathit{j}\mathit{k}}=1,\mathit{ }\mathit{j}=\mathrm{1,2},\dots,\mathit{n}$

(3)到达及离开每个货运点的车辆应为同一辆:

(4)

$\sum _{\mathit{i}=0}^{\mathit{n}}{\mathit{x}}_{\mathit{i}\mathit{j}\mathit{k}}=\sum _{\mathit{i}=0}^{\mathit{n}}{\mathit{x}}_{\mathit{j}\mathit{i}\mathit{k}}$

$\mathit{j}=\mathrm{0,1},\dots,\mathit{n};\mathit{k}=\mathrm{1,2},\dots,\mathit{n}$

(4)时间窗约束:

(5)

${\mathit{z}}_{\mathit{i}}+{\mathit{\Delta }}_{\mathit{i}}\ge {\mathit{e}}_{\mathit{i}},\mathit{ }\mathit{i}=\mathrm{1,2},\dots,\mathit{n}$

(6)

${\mathit{z}}_{\mathit{j}}-{\mathit{\theta }}_{\mathit{i}}\le {\mathit{l}}_{\mathit{i}},\mathit{ }\mathit{i}=\mathrm{1,2},\dots,\mathit{n}$

(5)时间节点约束:

(7)

$\sum _{\mathit{i}=0}^{\mathit{n}}{\mathit{x}}_{\mathit{i}\mathit{j}\mathit{k}}({\mathit{s}}_{\mathit{i}\mathit{k}}+{\mathit{f}}_{\mathit{i}}+{\mathit{t}}_{\mathit{i}\mathit{j}})={\mathit{s}}_{\mathit{j}\mathit{k}},\mathit{ }\mathit{k}=\mathrm{1,2},\dots,\mathit{m};\mathit{j}=\mathrm{1,2},\dots,\mathit{n}$

(8)

${\mathit{z}}_{\mathit{j}}=\sum _{\mathit{k}=1}^{\mathit{m}}{\mathit{s}}_{\mathit{j}\mathit{k}},\mathit{ }\mathit{j}=\mathrm{1,2},\dots,\mathit{n}$

2 目标混合算法框架

收起

为了优化机场终端VRPTW问题中的车辆路径规划,采用基于Dijkstra算法的多目标混合算法框架。该框架结合了遗传算法(GA)、模拟退火(SA)以及自适应大邻域搜索(ALNS)等元启发式算法的优点,机场终端VRPTW的多目标混合优化算法框架如表1所示。

算法步骤说明如下。

初始化:首先初始化所有车辆和货运点节点的状态。所有车辆的初始位置设定为机场货运站,货运点节点的状态设定为未服务。初始化到达时间函数t_i为无穷大,表示尚未计算任何到达时间,同时将所有车辆的载货量初始化为0,确保在路径规划中考虑车辆的容量约束。

应用Dijkstra算法计算最短路径:使用Dijkstra算法,从机场货运站开始计算所有货运点节点的最短路径。该步骤不仅提供了路径长度,还通过评估路径中的每个弧,更新节点的到达时间函数t_i。这为后续的时间窗优化提供基础。

遗传算法优化初始解:在生成初始路径解后,遗传算法通过交叉和变异操作产生新的解。新解被用于改进车辆的路径规划,使其在更大范围内探索可能的解空间。遗传算法确保解的多样性,进而找到较优的解。

模拟退火算法(SA)局部搜索:模拟退火算法通过接受一定概率的劣解,防止陷入局部最优。该算法对遗传算法生成的解进行局部搜索优化,以进一步减少运输成本和时间窗惩罚。在温度逐渐降低的过程中,系统逐步收敛到全局最优解。

自适应大邻域搜索(ALNS)优化:ALNS通过动态调整解空间中的邻域大小,对车辆路径进行大范围扰动。该步骤有助于解决复杂VRPTW问题中的大规模调整需求,允许算法跳出局部最优,寻找更具潜力的解。

综合多目标优化:结合遗传算法、模拟退火和ALNS的结果,针对多目标条件进行综合优化。特别是针对运输成本和时间窗惩罚的加权目标函数,最终选择最低成本且满足所有约束的最优解。

输出最优解:在算法完成后,输出最优解,包括所有车辆的路径及其到达时间。该解将同时最小化运输成本和时间窗惩罚,并满足所有货运点节点的需求和时间窗约束。

此多目标混合算法框架有效整合了Dijkstra算法与元启发式算法的优势,适用于处理复杂的VRPTW问题,尤其是在处理具有硬时间窗和软时间窗约束的情况下,其性能和有效性得到显著提升。

3 算例分析

收起

本文以绵阳南郊机场货运站揽收系统为例,一个机场货运站的货运点坐标及收货量如表2所示。

3.1 绵阳机场揽收中心优化前的车辆规划

机场货运站原始路线信息如表3所示,路线分布不合理导致车队收货,成本高,进而揽收中的惩罚成本直线上升。

3.2 绵阳机场揽收中心优化后的车辆规划

软件平台为MATLAB2023,迭代次数为1 000,种群大小100。车辆载重均为3 t;收运车固定成本分别为500元/d;单位距离收运成本分别为2.5元/km;超时惩罚成本为1.5元/min;所有车辆从货运站出发,完成揽收后回到货运站。

图1表示的混合算法在算例中的迭代进化过程。对比不同算法代表的收敛曲线,可以看出在迭代初期,混合算法展现出了更快的收敛速度,能够迅速逼近最优解,并且能跳出局部最优解,输出的最优路径如表4所示。路线优化前后对比分布图如图2中所示,原始路线同一货运点车队反复经过,且相邻货运点的连贯性有待提高,优化后路线重复和交叉迂回明显减少。

3.3 绵阳机场揽收中心优化前后的成本综合对比

如图3所示,应用混合算法对揽收模型进行优化后,结果表明原始路线数据的揽收总成本为4 607.1元,总时间花费为160.51 min;而经过混合算法优化后的揽收总成本降至3 829.48元,总时间花费减少至123.61 min。相较于原始数据,优化后的总成本降低了16.88%,总时间减少了22.99%。这一结果表明,混合算法在优化揽收模型的过程中显著降低了揽收成本,并提高了揽收效率。

4 结论

收起

本文针对绵阳南郊机场货运站的揽收系统,通过引入带有时间窗的车辆路径问题(VRPTW)模型,并结合最短路径算法和时间窗惩罚函数,对揽收路径进行优化。通过算例分析,优化后的揽收系统显著减少了车队的总行驶距离,降低了时间窗惩罚成本,同时提高了车队的利用效率和经济效益。优化结果表明,本文所提出的多目标混合算法框架在实际场景中具有较强的应用价值,降低了16.88%的总成本。能够有效解决机场终端复杂的车辆调度问题,为机场货运揽收系统的优化提供新的思路和技术支持。

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

DESROCHERS

, LENSTRA

J K

, SAVELSBERGH

M W P

, et al. Vehicle routing with time windows: optimization and approximation[M]. Amsterdam: North-Holland, 1988.

[2]

BEZERRA

S N

, SOUZA

S R

, FREITAS

M J

. AGVNS algorithm for solving the multi-depot vehicle routing problem[J]. Electronic Notes in Discrete Mathematics, 2018, 66: 167-174.

[3]

SOEANU

, RAY

, BERGER

, et al. Multi-depot vehicle routing problem with risk mitigation: model and solution algorithm[J]. Expert Systems with Applications, 2019, 145: 113099.

[4]

, WANG

, LI

, et al. Benefit analysis of shared depot resources for multi-depot vehicle routing problem with fuel consumption[J]. Transportation Research Part D Transport and Environment, 2018, 59: 417-432.

[5]

YÜCENUR

, DEMIREL

N Ç

. A new geometric shape-based genetic clustering algorithm for the multi-depot vehicle routing problem[J]. Expert Systems with Applications, 2011, 38(9): 11859-11865.

[6]

AZI

, GENDREAU

, POTVIN

. An exact algorithm for a single-vehicle routing problem with time windows and multiple routes[J]. European Journal of Operational Research, 2007, 178(3): 755-766.

[7]

REPOUSSIS

P P

, TARANTILIS

C D

, IOANNOU

. The open vehicle routing problem with time windows[J]. Journal of the Operational Research Society, 2007, 58(3): 355-367.

[8]

SUZUKI

. A new truck-routing approach for reducing fuel consumption and pollutants emission[J]. Transportation Research Part D: Transport and Environment, 2011, 16(1): 73-77.

[9]

王新华. 带时间窗的车辆路线问题研究[D]. 上海: 同济大学, 2006.

[10]

马华伟. 带时间窗车辆路径问题及其启发式算法研究[D]. 合肥: 合肥工业大学, 2008.

[11]

许美贤, 郑琰. 城市故障共享单车回收路径优化——以摩拜单车为例[J]. 科学技术与工程, 2021, 21(13): 5546-5555.

[12]

KALLEHAUGE

. Formulations and exact algorithms for the vehicle routing problem with time windows[J]. Computers & Operations Research, 2008, 35(7): 2307-2330.

[13]

GARCIA

N A

, BULLINARIa

J A

. An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows[J]. Computers & Operations Research, 2011, 38(1): 287-300.

[14]

段凤华. 带软时间窗约束的开放式车辆路径问题及其应用[D]. 长沙: 中南大学, 2009.

2025年第25卷第4期

PDF下载

303

144

引用本文

BibTeX

文章信息

接收时间：2024-08-21
首发时间：2025-08-17
出版时间：2025-02-25

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-08-21

基金

作者信息

中国民用航空飞行学院机场学院, 四川广汉 618307

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/kjhcy/CN/1163867268908794823

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

算法:机场终端VRPTW的多目标混合优化算法框架
1.初始化:
1.1初始化车辆初始状态和货运点节点状态,所有货运点节点未被服务
1.2设定到达时间函数t_i为无穷大,并初始化每辆车的载货量为0
2.应用Dijkstra算法计算最短路径
2.1使用Dijkstra算法计算机场货运站到每个货运点的最短路径
2.2根据路径更新到达时间函数t_i和载货量
3.遗传算法优化初始解
3.1基于Dijkstra生成的初始解,应用遗传算法(GA)交叉和变异操作,产生新的路径解
3.2评估新解的成本,并更新最优解
4.模拟退火算法(SA)局部搜索
4.1在遗传算法生成的解上执行模拟退火算法,进一步优化路径成本,降低时间窗惩罚
4.2根据温度衰减策略接受或拒绝新的解
5.自适应大邻域搜索(ALNS)优化
5.1应用ALNS动态调整解空间,对车辆路径进行大范围扰动搜索
5.2重新评估扰动后的解,若成本更低,则接受新解
6.综合多目标优化
6.1结合遗传算法、模拟退火和ALNS的结果,优化运输成本和时间窗惩罚的加权目标函数
7.输出最优解
7.1输出最小总成本的车辆路径集合R,包含每辆车的路径和到达时间

算法:机场终端VRPTW的多目标混合优化算法框架

1.初始化:

1.1初始化车辆初始状态和货运点节点状态,所有货运点节点未被服务

1.2设定到达时间函数t_i为无穷大,并初始化每辆车的载货量为0

2.应用Dijkstra算法计算最短路径

2.1使用Dijkstra算法计算机场货运站到每个货运点的最短路径

2.2根据路径更新到达时间函数t_i和载货量

3.遗传算法优化初始解

3.1基于Dijkstra生成的初始解,应用遗传算法(GA)交叉和变异操作,产生新的路径解

3.2评估新解的成本,并更新最优解

4.模拟退火算法(SA)局部搜索

4.1在遗传算法生成的解上执行模拟退火算法,进一步优化路径成本,降低时间窗惩罚

4.2根据温度衰减策略接受或拒绝新的解

5.自适应大邻域搜索(ALNS)优化

5.1应用ALNS动态调整解空间,对车辆路径进行大范围扰动搜索

5.2重新评估扰动后的解,若成本更低,则接受新解

6.综合多目标优化

6.1结合遗传算法、模拟退火和ALNS的结果,优化运输成本和时间窗惩罚的加权目标函数

7.输出最优解

7.1输出最小总成本的车辆路径集合R,包含每辆车的路径和到达时间

编号	经度	纬度	名称	收货量/t	最早可接受送达时间	最晚可接受送达时间
0	104.695 300	31.483 218	机场货运站	0.00	9:30	13:40
1	104.653 549	31.449 708	凝晖物流园	0.86	9:30	12:20
2	104.658 334	31.450 201	富发物流园	1.04	9:30	12:20
3	104.711 329	31.507 312	龙溪物流园	1.08	9:20	12:40
4	104.655 736	31.465 609	力展物流(绵阳二配送中心)	1.20	9:00	12:40
5	104.700 480	31.528 545	力展物流(绵阳高水配送中心)	0.89	9:10	12:20
6	104.661 501	31.450 344	绵阳市美福地物流有限公司	0.94	9:00	11:30
7	104.624 927	31.462 037	远成集团(辽宁大道)	1.07	9:10	11:20
8	104.660 218	31.447 921	联合运通物流	1.04	9:10	12:50
9	104.658 753	31.432 362	绵阳传化智慧物流枢纽	1.08	9:20	11:30
10	104.594 035	31.438 162	川江货运物流园	1.11	9:20	11:20
11	104.731 633	31.434 890	宇鑫物流	1.20	9:00	11:30
12	104.642 069	31.474 815	绵阳市三里包装有限公司物流分公司	0.81	9:30	11:30
13	104.729 122	31.485 245	京东物流(绵阳涪城快运集配站)	0.98	9:20	11:30
14	104.733 889	31.470 016	四川兄弟联物流有限公司(先锋路店)	0.80	9:10	11:30
15	104.729 924	31.435 614	双九快运有限公司	1.14	9:20	12:20
16	104.725 646	31.492 773	绵阳华青物流有限公司	0.94	9:30	11:40
17	104.638 159	31.449 705	乾坤物流(兴业南路)	1.09	9:20	12:40
18	104.685 952	31.532 575	韵达快递	1.04	9:20	11:40
19	104.767 688	31.432 500	中国邮政速递物流(经开区营业部)	0.87	9:00	12:40
20	104.644 156	31.473 176	绵阳安运物流有限公司	0.96	9:20	11:40
21	104.729 567	31.507 167	八维物流	0.92	9:20	11:30
22	104.726 400	31.448 914	良伟快运货运	0.81	9:30	12:40
23	104.731 741	31.434 452	力展物流(绵阳毅德店)	0.99	9:00	11:40
24	104.730 540	31.435 464	云聚物流	0.96	9:20	12:10
25	104.723 855	31.441 490	德邦快递(绵阳涪城区分部)	0.94	9:00	11:30
26	104.679 433	31.547 743	余氏东风物流(高水龙门石马点)	1.18	9:20	11:40
27	104.681 532	31.418 067	顺丰速运有限公司绵阳快运营业点	1.18	9:20	12:40
28	104.731 628	31.434 778	恒兴物流	1.19	9:10	11:40
29	104.790 848	31.391 235	力展物流(绵阳经开区配送中心)	0.82	9:00	11:20
30	104.701 845	31.523 540	绵阳鑫秀云物流	1.15	9:10	12:30
31	104.665 494	31.449 687	起航物流	0.99	9:30	11:10
32	104.654 419	31.486 598	四川虎威物流有限公司	0.93	9:30	11:20
33	104.659 648	31.449 723	四川三志物流供应链管理有限公司	1.00	9:00	12:10
34	104.767 257	31.417 928	四川省烟草公司绵阳市公司物流中心	0.94	9:00	11:30
35	104.669 388	31.493 075	中国邮政速递物流(九盛路店)	1.10	9:00	11:20

编号

经度

纬度

名称

收货量/t

最早可接受
送达时间

最晚可接受
送达时间

104.695 300

31.483 218

机场货运站

0.00

9:30

13:40

104.653 549

31.449 708

凝晖物流园

0.86

9:30

12:20

104.658 334

31.450 201

富发物流园

1.04

9:30

12:20

104.711 329

31.507 312

龙溪物流园

1.08

9:20

12:40

104.655 736

31.465 609

力展物流(绵阳二配送中心)

1.20

9:00

12:40

104.700 480

31.528 545

力展物流(绵阳高水配送中心)

0.89

9:10

12:20

104.661 501

31.450 344

绵阳市美福地物流有限公司

0.94

9:00

11:30

104.624 927

31.462 037

远成集团(辽宁大道)

1.07

9:10

11:20

104.660 218

31.447 921

联合运通物流

1.04

9:10

12:50

104.658 753

31.432 362

绵阳传化智慧物流枢纽

1.08

9:20

11:30

104.594 035

31.438 162

川江货运物流园

1.11

9:20

11:20

104.731 633

31.434 890

宇鑫物流

1.20

9:00

11:30

104.642 069

31.474 815

绵阳市三里包装有限公司物流分公司

0.81

9:30

11:30

104.729 122

31.485 245

京东物流(绵阳涪城快运集配站)

0.98

9:20

11:30

104.733 889

31.470 016

四川兄弟联物流有限公司(先锋路店)

0.80

9:10

11:30

104.729 924

31.435 614

双九快运有限公司

1.14

9:20

12:20

104.725 646

31.492 773

绵阳华青物流有限公司

0.94

9:30

11:40

104.638 159

31.449 705

乾坤物流(兴业南路)

1.09

9:20

12:40

104.685 952

31.532 575

韵达快递

1.04

9:20

11:40

104.767 688

31.432 500

中国邮政速递物流(经开区营业部)

0.87

9:00

12:40

104.644 156

31.473 176

绵阳安运物流有限公司

0.96

9:20

11:40

104.729 567

31.507 167

八维物流

0.92

9:20

11:30

104.726 400

31.448 914

良伟快运货运

0.81

9:30

12:40

104.731 741

31.434 452

力展物流(绵阳毅德店)

0.99

9:00

11:40

104.730 540

31.435 464

云聚物流

0.96

9:20

12:10

104.723 855

31.441 490

德邦快递(绵阳涪城区分部)

0.94

9:00

11:30

104.679 433

31.547 743

余氏东风物流(高水龙门石马点)

1.18

9:20

11:40

104.681 532

31.418 067

顺丰速运有限公司绵阳快运营业点

1.18

9:20

12:40

104.731 628

31.434 778

恒兴物流

1.19

9:10

11:40

104.790 848

31.391 235

力展物流(绵阳经开区配送中心)

0.82

9:00

11:20

104.701 845

31.523 540

绵阳鑫秀云物流

1.15

9:10

12:30

104.665 494

31.449 687

起航物流

0.99

9:30

11:10

104.654 419

31.486 598

四川虎威物流有限公司

0.93

9:30

11:20

104.659 648

31.449 723

四川三志物流供应链管理有限公司

1.00

9:00

12:10

104.767 257

31.417 928

四川省烟草公司绵阳市公司物流中心

0.94

9:00

11:30

104.669 388

31.493 075

中国邮政速递物流(九盛路店)

1.10

9:00

11:20

路线编号	路线	收货成本/元	惩罚成本/元	车辆到达各节点的时长/min
路线1	0→27→8→32→16→2→12→20→21→5→0	1 054.31	13.42	0.00→11.05 →16.89 →35.20 →55.80 →77.03 →91.15 →101.95 →123.47 →138.54 →155.34
路线2	0→15→11→10→30→18→26→17→7→0	1 181.04	15.97	0.00→9.35 →9.63 →40.64 →73.59 →87.41 →101.60 →129.40 →143.99 →165.52
路线3	0→1→19→29→9→24→4→6→3→35→0	1 358.39	32.75	0.00→8.17 →24.68 →40.92 →69.66 →88.10 →110.68 →122.96 →146.83 →162.65 →177.49
路线4	0→31→14→33→23→34→25→28→22→13→0	916.76	34.46	0.00→7.03 →17.34 →38.35 →56.93 →72.69 →89.92 →100.90 →112.77 →130.75 →143.68

路线编号

路线

收货成本/元

惩罚成本/元

车辆到达各节点的时长/min

路线1

0→27→8→32→16→2→12→20→21→5→0

1 054.31

13.42

0.00→11.05 →16.89 →35.20 →55.80 →77.03 →91.15 →101.95 →123.47 →138.54 →155.34

路线2

0→15→11→10→30→18→26→17→7→0

1 181.04

15.97

0.00→9.35 →9.63 →40.64 →73.59 →87.41 →101.60 →129.40 →143.99 →165.52

路线3

0→1→19→29→9→24→4→6→3→35→0

1 358.39

32.75

0.00→8.17 →24.68 →40.92 →69.66 →88.10 →110.68 →122.96 →146.83 →162.65 →177.49

路线4

0→31→14→33→23→34→25→28→22→13→0

916.76

34.46

0.00→7.03 →17.34 →38.35 →56.93 →72.69 →89.92 →100.90 →112.77 →130.75 →143.68

路线编号	路线	收货成本/元	惩罚成本/元	车辆到达各节点的时长/min
路线1	0→27→9→17→12→26→18→5→30→0	893.68	0	0.00→11.05 →15.08 →31.01 →46.04 →70.22 →81.02 →95.00 →106.25 →121.95
路线2	0→11→28→24→22→14→13→16→21→3→0	1 002.80	0.59	0.00→11.05 →15.08 →31.01 →46.04 →70.22 →81.02 →95.00 →106.25 →121.95
路线3	0→35→32→6→31→8→1→10→7→20→0	1 117.30	0	0.00→4.04 →6.43 →23.57 →33.45 →43.65 →54.55 →73.64 →88.18 →102.59 →120.77
路线4	0→19→29→34→23→15→25→33→2→4→0	815.70	0	0.00→13.34 →20.98 →35.27 →49.23 →58.95 →70.16 →90.81 →100.41 →113.01 →129.77

路线编号

路线

收货成本/元

惩罚成本/元

车辆到达各节点的时长/min

路线1

0→27→9→17→12→26→18→5→30→0

893.68

0.00→11.05 →15.08 →31.01 →46.04 →70.22 →81.02 →95.00 →106.25 →121.95

路线2

0→11→28→24→22→14→13→16→21→3→0

1 002.80

0.59

0.00→11.05 →15.08 →31.01 →46.04 →70.22 →81.02 →95.00 →106.25 →121.95

路线3

0→35→32→6→31→8→1→10→7→20→0

1 117.30

0.00→4.04 →6.43 →23.57 →33.45 →43.65 →54.55 →73.64 →88.18 →102.59 →120.77

路线4

0→19→29→34→23→15→25→33→2→4→0

815.70

0.00→13.34 →20.98 →35.27 →49.23 →58.95 →70.16 →90.81 →100.41 →113.01 →129.77