Click the blue text above to follow us
📋📋📋 The table of contents is as follows: 🎁🎁🎁
Contents
⛳️ Gift for Readers
💥1 Overview
1.1 Introduction
1.2 Application Scenarios
1.3 Method Implementation
📚2 Results
🎉3 References
🌈4 MATLAB Code, Data, Documentation
Gift for Readers
👨💻 Conducting research involves a profound system of thought, requiring researchers to be logical, meticulous, and serious. However, effort alone is not enough; often leveraging resources is more important than sheer hard work. Additionally, one must have innovative and inspirational points of view. When a philosophy teacher asks you what science is or what electricity is, do not dismiss these questions as trivial. Philosophy is the mother of science; it seeks to explore ultimate questions and find those self-evident questions that only children would ask but you cannot answer. It is recommended that readers browse through the contents in order to avoid suddenly falling into a dark maze without finding their way back. This may not reveal all the answers to your questions, but if it can evoke clouds of doubt in your mind, it may create a beautiful sunset of thoughts. If it brings you a spiritual downpour, then take the opportunity to brush off the dust that has settled on your “lying flat” mindset. Perhaps, after the rain, the world will be clearer…🔎🔎🔎
1 Overview
Abstract: Emerging urban logistics applications face numerous challenges, including complex traffic conditions and time-sensitive demands. This study considers a Vehicle Routing Problem with Time Windows (VRPTW) in the context of urban logistics, aiming to minimize total generalized costs, including transportation, waiting time, and fixed costs associated with each vehicle. We employ a high-dimensional spatiotemporal network flow model to construct a foundational vehicle routing problem (VRP) with rich criteria and constraints. A significant challenge in solving the VRP is how to iteratively improve the quality of primal and dual solutions and how to break the symmetry caused by many identical solutions, especially for homogeneous vehicles. Along this line, many coupling constraints, such as consensus constraints across different agents or decision-makers, need to be carefully handled to find high-quality optimal or near-optimal solutions for medium or large-scale instances. Currently, the Alternating Direction Method of Multipliers (ADMM) is widely used in the field of convex optimization as an integration of augmented Lagrangian relaxation and block coordinate descent methods for machine learning and large-scale continuous system optimization and control. In this work, we introduce the use of ADMM to solve the multi-vehicle routing problem, a special case of integer linear programming, and demonstrate a method to simplify the quadratic penalty term used in ADMM to a simple linear function. In a broader context, we develop a computationally reliable decomposition framework to iteratively improve the quality of primal and dual solutions. Essentially, the minimum cost path subproblem or other similar subproblems involving binary decisions can be embedded into a sequential solution scheme, outputting lower bound estimates and upper bound feasible solutions. We use classic Solomon VRP benchmark instances to test the performance of the proposed method. Our approach is also evaluated based on a real instance from a problem-solving competition of a major e-commerce company.
Keywords:Urban Logistics, Vehicle Routing Problem with Time Windows, Alternating Direction Method of Multipliers, Problem Decomposition
1.1 Introduction
-
Augmented Lagrangian Relaxation (ALR): An extension of Lagrangian relaxation that adds a quadratic penalty term, enhancing the robustness of the solution method and making the transformed problem easier to solve. Block Coordinate Descent Method: An algorithm that iteratively searches along one coordinate direction to find a local minimum of the function, cycling through different coordinate directions. Alternating Direction Method of Multipliers (ADMM): ADMM can be used to iteratively optimize the VRPTW problem for K vehicles, allowing convergence from infeasible solutions to feasible ones. It decomposes the original problem into subproblems for each vehicle, enabling the use of forward dynamic programming algorithms to solve them.
1.2 Application Scenarios
-
Applicable to the Vehicle Routing Problem with Time Windows (VRPTW).
1.3 Method Implementation
FDP: Maintain a matrix (K, S, T), where K is the number of schemes considered, S is the number of demand points, and T is time. The state is the current time t, and the top K optimal delivery schemes. The state transition considers the top K optimal delivery schemes, where for each scheme, any unserved customer can be selected. At time t+t(i), t(i) represents the time taken to reach the new customer i from the current service point, then jump to time t+1. At each time t, only the top K optimal delivery schemes are considered. Define the initial state where all vehicles start from the same starting point at time 0. ADMM: First, initialize the upper and lower bounds of the original problem, Lagrange multipliers, quadratic term parameters, and delivery schemes for each vehicle, then start the loop, fixing the delivery paths of other vehicles. For K vehicles, call FDP in turn to find the minimum cost delivery path, update multipliers and penalty parameters, and then generate and update the bounds. CalculateCostForVehicle: In a certain iteration, calculate the original cost for each vehicle based on the current fleet’s delivery scheme. FeasibleSolution: Feasibility of the solution. Mainly used when the solution has not yet converged to a feasible solution after the iteration ends. If a service point is served twice by two vehicles, retain the service of the second vehicle and modify the delivery of the first vehicle. If there are customers not served, assign a spare vehicle to serve that customer. GeneralizedCostMatrix: Generate a generalized cost matrix, adding penalties for lateness to the original cost matrix, allowing for lateness but incurring penalty costs. GenerateFreshness: Select the optimal fruit freshness for each vehicle, ensuring that the fruit is as close to the customer’s required quality upon delivery. Given the delivery scheme for each vehicle, loop through each freshness option to minimize the freshness deviation for each vehicle’s service to its customers.
📚2 Results Expected earliest delivery time window: 0 (default all vehicles start from time 0 from a common starting point) Expected latest delivery time window: Randomly generate two points in the time set for delivery duration: Randomly set the duration between any two points to 1, 2, or 3 Delivery cost ratio to duration: 1:1 Consumer order demand: Randomly set positive integers within the set [25,40]
2 Results
Figure 1: The left graph shows the changes in UB and LB with the number of iterations, while the right graph shows the number of unserved customers with the number of iterations. From the right graph, it can be seen that as the number of iterations increases, the number of unserved customers gradually decreases from the maximum value, converging to 0 around the 32nd iteration, indicating that the program gradually transitions from an infeasible solution where all customers are unserved to a feasible solution that meets the demands of all customers as the number of iterations increases. The left graph shows that as the number of iterations increases, the upper bound gradually decreases while the lower bound gradually increases, indicating that the quality of the solution improves with the number of iterations. Based on the above conclusions, as the number of iterations increases until the program converges, a good feasible solution can be obtained (or an approximate optimal solution can be obtained if not converged). Below, we compare the solutions from two iterations (one after convergence and one before convergence) to demonstrate that the solution after convergence is superior, indicating that the program can iteratively improve the solution until convergence.
Selecting the relatively well-calculated result from the 14th iteration, the vehicle-path results and costs are shown in the table below (0 is the common starting point, 26 is the common endpoint):
|
Vehicle id |
Vehicle routing solution |
Cost |
|
1 |
0-26 |
0 |
|
2 |
0-26 |
0 |
|
3 |
0-23-18-26 |
5.0000 |
|
4 |
0-20-19-25-26 |
7.0000 |
|
5 |
0-5-2-12-26 |
5.0000 |
|
6 |
0-6-15-4-26 |
5.0000 |
|
7 |
0-20-8-25-26 |
6.0000 |
|
8 |
0-1-17-26 |
4.0000 |
|
9 |
0-11-16-7-26 |
5.0000 |
|
10 |
0-21-3-26 |
4.0000 |
|
11 |
0-24-9-10-26 |
6.0000 |
|
Total |
47.0000 |
Table 1: Vehicle path results and costs from the 14th iteration
Number of vehicles used: 9
Customers served multiple times: 20.25
Unserved customers: 13.14.22
Detailed explanation can be found in section 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 );
3References
Some content in this article is sourced from the internet, and references will be noted. If there are any inaccuracies, please feel free to contact us for removal.
[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 Code, Data, Documentation
Public Account
Lychee Research Society