基于ADMM的车辆路径问题与时间窗口(VRPTW)的问题分解方案（Matlab代码实现）

💥💥💞💞欢迎来到本博客❤️❤️💥💥

🏆博主优势：🌞🌞🌞博客内容尽量做到思维缜密，逻辑清晰，为了方便读者。

⛳️座右铭：行百里者，半于九十。

⛳️赠与读者

👨‍💻做科研，涉及到一个深在的思想系统，需要科研者逻辑缜密，踏实认真，但是不能只是努力，很多时候借力比努力更重要，然后还要有仰望星空的创新点和启发点。当哲学课上老师问你什么是科学，什么是电的时候，不要觉得这些问题搞笑。哲学是科学之母，哲学就是追究终极问题，寻找那些不言自明只有小孩子会问的但是你却回答不出来的问题。建议读者按目录次序逐一浏览，免得骤然跌入幽暗的迷宫找不到来时的路，它不足为你揭示全部问题的答案，但若能让人胸中升起一朵朵疑云，也未尝不会酿成晚霞斑斓的别一番景致，万一它居然给你带来了一场精神世界的苦雨，那就借机洗刷一下原来存放在那儿的“躺平”上的尘埃吧。

或许，雨过云收，神驰的天地更清朗.......🔎🔎🔎

💥1 概述

参考文献：

摘要：新兴的城市物流应用需要解决诸多挑战，包括复杂的交通状况和对时间敏感的需求。本研究在城市物流背景下考虑了一个具有时间依赖行驶时间和时间窗口的车辆路径问题（VRPTW），旨在最小化总广义成本，包括与每辆车相关的运输、等待时间和固定成本。我们采用高维时空网络流模型来构建一个具有丰富准则和约束条件的基础车辆路径问题（VRP）。在解决VRP时，一个困难问题是如何通常迭代地提高原始和对偶解的质量，以及如何打破由许多相同解引起的对称性，特别是对于同质车辆。沿着这条线，许多耦合约束，如跨不同代理人或决策者的共识约束，需要仔细处理，以在中等或大规模实例下找到高质量的最优或接近最优解。目前，交替方向乘子法（ADMM）被广泛应用于凸优化领域，作为增广拉格朗日松弛和块坐标下降方法的整合，用于机器学习和大规模连续系统优化和控制。在这项工作中，我们介绍了使用ADMM解决多车辆路径问题，这是整数线性规划的特殊情况，并展示了一种将ADMM中使用的二次惩罚项简化为简单线性函数的方法。在更广泛的背景下，开发了一个计算可靠的分解框架，以迭代地提高原始和对偶解的质量。基本上，最小成本路径子问题或其他涉及二进制决策的类似子问题可以嵌入到一个顺序解决方案方案中，输出下界估计和上界可行解。我们使用经典的Solomon VRP基准实例来检验所提出方法的性能。还基于一家主要电子商务公司的一个问题解决比赛的真实实例对我们的方法进行评估。

关键词：城市物流、带时间窗口的车辆路径问题、交替方向乘子法、问题分解

1.1介绍

• Augmented Lagrangian relaxation(ALR)：增广拉格朗日松弛，在拉格朗日松弛的基础上加上一个二次惩罚项，增加了解法的鲁棒性，使得转换后的问题更容易求解。
• Block coordinate descent method：块坐标下降法，算法在迭代的过程中，沿着某一个坐标的方向进行一维搜索，寻找函数的一个局部极小值， 整个过程中循环搜索不同的坐标方向。
• Alternating Direction Method of Multiplier(ADMM)：ADMM可用于迭代优化K辆车的VRPTW问题，使得从不可行解收敛到可行，它把原问题分解成关于 每辆车的子问题，使得子问题可以调用向前动态规划算法求解。

1.2 技术用途

• 可应用于VRPTW(Vehicle Routing Problem with Time Window)问题。

1.3方法实现

• FDP：维护一个(K, S, T)的矩阵，K为参与考虑的方案数，S为需求点的个数，T为时间。状态为当前时刻t，前K个最优的配送方案，状态转移为当前时刻t，考虑前 K个最优配送方案，对于每一方案都可以选择任意未服务过的客户，到达t+t(i)时刻，t(i)表示从当前服务点出发，到达选择的新客户i服务点的时间花费，然后跳到t+1 时刻，每个时刻t只考虑前K个最优配送方案。定义初始状态，所有车辆都从同一个起始点出发，从时刻0开始出发。
• ADMM：首先初始化原问题的上界和下界、拉格朗日乘子、二次项参数和每辆车对应的配送方案等变量，开始循环，固定其他车辆的配送路径，对K辆车先后调用FDP 求出其最小成本的配送路径，更新乘子和惩罚项参数，然后生成上下界并更新。
• CalculateCostForVehicle：在某一个迭代轮次，根据当前车队的配送方案，计算出每一辆车的原始成本。
• FeasibleSolution:解的可行化。主要用于迭代轮次结束以后解还未收敛至可行解，则可行化该不可行解。若有某服务点被两辆车服务了两次，则保留第二辆车的服务， 修改第一辆车的配送，若有客户未被服务，则指派一辆备用的车辆为该客户服务。
• GeneralizedCostMatrix:生成广义成本矩阵，把迟到产生的费用加入到原成本矩阵，即允许迟到，但是会产生惩罚费用。
• GenerateFreshness：为每辆车选择最优的水果新鲜度，使得水果在配送至客户处时最接近客户要求的品质。已知每辆车配送方案的前提下，循环尝试每种新鲜度 可以使得每辆车对其服务客户的新鲜度偏差最小，选择对应新鲜度。

📚2 运行结果

期望送达最早时间窗：0（默认全部车辆从时间0从共同出发点出发）

期望送达最晚时间窗：在时间集合中随机生成

两点间配送时长：随机设置任意两点间时长为1,2,或者3

配送成本比时长：1：1

消费者订单需求量：随机设置集合[25,40]内的正整数

图1左图为UB和LB随着迭代次数的变化，右图为未服务的顾客数随着迭代次数的变化。从右图可以看出随着迭代轮次的增加，未服务的顾客数从最大值逐渐下降，到约第32轮次时收敛至0，说明程序逐渐从刚迭代时得到的全部顾客都未服务的不可行解，随着迭代轮次的增加，到收敛时可以得到一个全部顾客都满足需求的可行解。由左图可以看出随着迭代轮次的增加，上界逐渐下降，下界逐渐上升，解的质量随着迭代轮次的增加而增加。结合上述结论，随着迭代轮次的增加至程序收敛时，可以得到一个较好的可行解（或未收敛时得到一个近似较优解）。下面通过比较其中两个迭代轮次的解（一个是收敛后，另一个是未收敛时），证明收敛后的解较优，即程序可以通过迭代使得解逐渐变优，直到收敛。

未收敛轮次选取：

选取相对较好计算的第14次迭代结果进行分析，第14次迭代车-路径结果及成本如下表所示（0为共同起点，26为共同终点）：

表1：第14次迭代车路径结果及成本

使用车次：9

其中重复服务的顾客：20.25

未服务的顾客：13.14.22

详细讲解见第4部分。

部分代码：

%parameters
lambda1 = 1;
lambda2 = 1;
T = 10; % Time.
R = 4; % Freshness.
W = 100; % Car capacity.
c = 100; % Customers.
s = c+2; % Space node.
alpha2 = 2; % Time window penalty for delivery late.
rho = 0.1;
bestK = 100;
iteration = 100; % ADMM iterations.

% The next 3 lines of code is used to generate random time intervals
% between random 2 nodes. Writes it in an excel file and then copy it
% to 'inputFor100.xlsx' file.
%timeRange = [1, 3];
%[ B ] = GenerateRandomTime( c, timeRange );
%xlswrite('randomTimeFor100', B);

node = xlsread('inputFor100.xlsx', 1, 'B2:E101', 'basic');
demand = node(:, 1);
%et = node(:, 2);
lt = node(:, 3);
freshness = node(:, 4);
K = ceil(sum(demand)/W)+2; % Set vehicle number.
clear node;
link = xlsread('inputFor100.xlsx', 2, 'D2:D10405', 'basic');

link = reshape(link, [s, s]);
[ UB1 ] = CalculateObject1UB( link );
link = reshape(link, [s, s, 1, 1]);
C = zeros(s, s, T+1, T+1); % Arc cost matrix. Vehicles start from t=0.

.....

subplot(1, 2, 1)
plot(x, y1, x, y2);
xlabel('Iteration')
ylabel('UB & LB')
legend('UB','LB')

subplot(1, 2, 2)
plot(x, unServedNode);
xlabel('Iteration')
ylabel('The number of unserved Node')

% Suggest to use this function after program has been converged.
[ finalSeq, timeSeq ] = FeasibleSolution( visitedSeq, finalRout, serviceTimes, C );

% Generate freshness deviation and freshness choice for each vehicle.
[ proposalR_K, freshnessDeviation ] = ...
GenerateFreshness( finalSeq, timeSeq, freshness, R );

🎉3参考文献

文章中一些内容引自网络，会注明出处或引用为参考文献，难免有未尽之处，如有不妥，请随时联系删除。

[1] Y.Yao, X.Zhu, H.Dong, S.Wu, H.Wu, L.C.Tong and X.Zhou, "ADMM-based Problem Decomposition Scheme for Vehicle Routing Problem with Time Windows," Transportation Research Part B:Methodological, vol. 129, no. 19, pp. 156-174, 2019.

🌈4 Matlab代码、数据、文档