I. Introduction to VRP
1 Basic principles of VRPVehicle Routing Problem (VRP) is one of the most important research problems in operations research. VRP is concerned with the path planning of a supplier and K points of sale, which can be summarized as: for a series of delivery points and receiving points, the organization calls certain vehicles, arranges appropriate driving routes, and makes the vehicles pass through them in an orderly manner, under specified constraints (e.g. The demand and quantity of goods, delivery and delivery time, vehicle capacity limit, mileage limit, driving time limit, etc.), and strive to achieve certain goals (such as the shortest total mileage of empty vehicles, the lowest total transportation cost, vehicles arrive at a certain time, the use of the smallest number of vehicles, etc.). The legend of VRP is as follows:
3 Common problems are as follows:(1) Traveling salesman Problem (2) Vehicle Routing problem with Capacity Constraint (CVRP)
4 solutions (1) mathematical analysis method (2) human-computer interaction method (3) group and then arrange route method (4) group and then arrange route method (5) save or insert method (6) improve or exchange method (7) mathematical programming approximation method (8) heuristic algorithm
5 Comparison between VRP and VRPTW
IWD (Intelligent Water Drop) algorithm introduction
1 overview In nature, the channel is composed of flowing water droplets move to create huge group, compared with the water droplets group itself, which flows through the channel is what they are in the surroundings, and the environment are the drastic change of flow direction of the water droplets groups, at the same time, the surrounding environment also influence the flow of water droplets group. For example, in the environment, solid boulders and soil hinder the flow of water droplets, while soft and loose soil has much less resistance to the flow of river water. In fact, the appearance of rivers in nature is the result of the long-term interaction between droplet groups and the surrounding environment. According to people’s common sense, most of the rivers and waterways in nature are zigzagging, but the water in the river is not like the human vision to the lake or the sea, but, the water droplets under the action of the earth’s gravity constantly forward flow. As we all know, the earth’s gravity direction pointing to the center of the earth, so if the surrounding environment without obstacles, water should be along the direction of gravity to the center of the earth movement: due to the gravity of the earth, the water droplets in the process of flow will get some acceleration, therefore with its movement speed will slowly rising. However, in reality, there is no such ideal state and no ideal straight path from the source of water to the center of the earth, and even the actual path of water dissipation is far different from the ideal path due to the influence of brick barriers, hence the appearance of the river we see today. It is found that it is optimal for water droplets to establish a channel of meters under the condition of movement. Water droplets in a river have two properties: they have a certain speed and they carry a certain amount of soil. In this case, the water droplets move the mud from one place to another as they move. As far as we know, the earth will be carried in water from high speed to the flow rate is low, the reason is that when the water droplets at high speeds of its kinetic energy is larger, can overcome the earth’s gravity to take the role of the soil, when the water flow with low speed, water droplets will carry soil in earth’s gravity deposited in the droplets travel path. For this reason, the earth will be in the region of the flow rate is higher allochthonous more and more, corresponding channel is becoming more and more deep, has attracted more and more flow here, which can hold more water, the soil and water droplets carried in flow speed is slow because of the earth’s gravity Unloaded and deposition in the riverbed. When a water droplet flows from one place to another in a river, the velocity of the droplet, the amount of soil carried by the droplet, and the amount of soil between the two places all change significantly: 1) the velocity of the droplet will increase as it flows; 2) The water droplets will carry more and more soil, and 3) the river bed between these two points will carry less and less soil.
In fact, as described above, water clearings carry a certain amount of soil from the riverbed as they move from one place to another, and the amount of soil in the river channel decreases and the amount of soil carried by the dropper body increases. In the process of this movement, the velocity at which the water droplets flow will also change. Speed larger droplets when flow carries on more mud from the river, in addition, due to the water flow speed with speed and it week associated with environment, the environment for the movement of the water droplets to play the role of a block, so when large amounts of surrounding soil, clear water flow rate in the period of path of growth will be slower, When the surrounding soil is small, the speed of water droplets in the period of path gain corresponding will be more and more quickly, will be easier to forward flow: within this we get move when the water droplets in the nature has the following properties: 1) high flow rate of water droplets than low flow rate of water droplets in the path moves can carries more of the earth: 2) The velocity increment obtained by water droplets in the path with less soil is greater than that obtained in the path with the most soil: 3) when water flow in choosing a path to the possibility of a larger move toward the path of the soil is less. 3 intelligent water basic principle of the algorithm Above has introduced the water droplets in nature has the characteristics of some typical, according to the above description of these features, according to the imagination of people, can the virtual human model is set up, known as intelligent water droplets (IWD), It has two important properties: Soil (IWD) is generally used to represent the amount of soil carried by water droplets, and Veloci TV (/WD) is used to represent the velocity of water flowing forward. In engineering problem solving, the surrounding environment of intelligent water droplets flowing represents the engineering problems we need to solve. Since the shortest path sought by intelligent water droplets in interaction is the optimal path found by us in solving engineering problems, soil(JWD) and Velocity (IWD), two important properties of intelligent water droplets, are constantly changing in the process of sub-path finding. We assume that some intelligent water droplets flow from a starting point to an end point in an environment where there may be more than one path from the beginning point to the end point. The environment referred to here is the engineering problem we need to solve in practice, which can be divided into two kinds of problems: first, in the case of the end point is known, to solve this kind of problem needs to find the best path from the beginning point to the end point according to a certain standard (usually distance). Second: in the case that the position of the end point is not known in advance, to solve this kind of problem, it is necessary to find the optimal position of the end point according to the cost or other standards.
Three, some source code
clc; close all; clear all;
%% Variable initialization
iterations = 60;
pIter = 3; % # of parallel sol'ns calculated to find totalbest stats = zeros(iterations, 2); % rows are iteration number, columns are best/worst % Initial variables tempInit = 150; % initial temperature for SA temp = tempInit; TempDec = 0.95; % temperature decrease rate tempIter = 1; % number of iterations at each step soilInit = 1000; velocityInit = 100; a_v = 1000; a_s = 1000; B_v = 0.01; B_s = 0.01; c_v = 1; c_s = 1; vel_params = [a_v b_v c_v]; soil_params = [a_s b_s c_s]; % Soil updating params rho_O = 0.9; rho_n = 1 - rho_o; % Global soil updating params rho_s = 0.8; Rho_iwd = 1.5; % Data sets pind = 1; % problem index problempath = '. /.. /data/problems/';
problemfiles = { 'p01', 'p02', 'p03', 'p04', 'p05'}; solutionpath = '. /.. /data/solutions/';
solutionfiles = { 'p01.res', 'p02.res', 'p03.res', 'p04.res', 'p05.res'}; %% Load and format data % Grab the first fileset [desc, depot_desc, cust, depot] = parseProblemSet(strcat(problempath, problemfiles{pind})); num_customers = desc(3); num_depots = desc(4); num_vehicles = desc(2); all_coords = [cust(:,2:3); depot(:,2:3)]; % Build adjacency matrix row is source, col is dest [ distMat globalSoilMat ] = prepareBoard(desc, depot_desc, cust, depot, soilInit); soilMat = globalSoilMat; % Soil weightings based on edge length soilMat = log(distMat+1).*globalSoilMat; %logarithmic %soilMat = distMat.*globalSoilMat; %linear %soilMat = exp(distMat).*globalSoilMat; %exponential soilMat = normalizeSoilMat(soilMat, soilInit); globalSoilMat = soilMat; % globalSoilMat contains the soil going forward %% Initialize agents for i = 1:pIter dropstemp = []; for d = 1:num_depots % for each depot for v = 1:num_vehicles % populate vehicles dep = depot(d,1); capacity = depot_desc(d,2); dropstemp = [ dropstemp; WaterDrop(dep,capacity,velocityInit, ... vel_params, soil_params) ]; end end drops(:, 1, i) = dropstemp; end clear dropstemp; % Best solution best_sol = 0; best_cost = 0; temp_counter = 0; %% Simulate water drops for it = 1:iterations % reset calcualtion variables soilMat = globalSoilMat; for i = 1:pIter % reset droplets for dr = 1:length(drops) drops(dr, 1, i) = drops(dr, 1, i).reset(velocityInit); end end for s = 1:pIter % iterate to get parallel solutions and then will compare % Build a full route set with multiple agents % Reset the parameters of each water drop on init customers = cust(:,1); demand = [cust(:,1) cust(:, 5)]; while ~isempty(customers) for i = 1:length(drops) if isempty(customers) break; % stop processing this loop since allocation complete end % Simulate water drop flow for one agent iwd = drops(i, 1, s); iwd = iwd.flow(soilMat,customers, demand); customers(customers == iwd.route(end)) = []; % Update water drop iwd = iwd.updateVelocity(soilMat); iwd = iwd.updateSoil(distMat); drops(i, 1, s) = iwd; % Update soil on edges dsoil = iwd.deltaSoil(distMat); n = length(iwd.route); soilMat(iwd.route(n - 1), iwd.route(n)) = ... rho_o * soilMat(iwd.route(n - 1), iwd.route(n)) ... - rho_n * dsoil; soilMat(iwd.route(n), iwd.route(n - 1)) = ... rho_o * soilMat(iwd.route(n), iwd.route(n - 1)) ... - rho_n * dsoil; end% end of looping over agents for allocation end % end of customer allocation % send agents home for i = 1:length(drops) drops(i, 1, s) = drops(i, 1, s).returnHome(); end end % parallel solution construction parallelCost = zeros(pIter, 1); parallelBestCost = 0; % Calculate total solution cost (Euclidean distance; sum of routes) for s = 1:pIter dropcost = 0; for i = 1:length(drops) dropcost = drops(i, 1, s).calcRouteCost(distMat); parallelCost(s) = parallelCost(s) + dropcost; end end % Get index of the best solution bestIndex = 0; for s = 1:pIter if parallelCost(s) == min(parallelCost) bestIndex = s; parallelBestCost = parallelCost(s); break; end end % Stat updating stats(it, :) = [min(parallelCost) max(parallelCost)]; % Update the best solution if (parallelBestCost < best_cost) || (best_cost == 0) best_cost = parallelBestCost best_sol = drops(:, :, bestIndex); end % Update the global soil probability = exp(-(parallelBestCost - best_cost)/temp); temp_counter = temp_counter + 1; if (temp_counter > tempIter) temp_counter = 0; temp = temp*tempDec; %reduce it end function [desc, depot_desc, cust, depot] = parseProblemSet(filename) % Summary: Function for parsing Cordeau problem sets and returning % arrays containing the data. % % desc: Prob descr (type, # vehicles, # cust, # dep) % depot_desc: Descr of depots (max dur of route, max vehicle load) % cust: Customers (id, x,y, serv dur, demand, visit freq, % # visit combs, list visit combs) % depot: Depots (same as customers, but list is not present) f = fopen(filename); % Open for read % Description of problem set desc = str2double(strsplit(strtrim(fgets(f)), ' ')); if length(desc) ~= 4 error('File not correct format') end % Pull out variables desc_cell = num2cell(desc); [ptype m n t] = desc_cell{:}; % Depot descriptions depot_desc = zeros(t,2); for i = 1:t depot_desc(i,:) = str2double(strsplit(strtrim(fgets(f)), ' ')); end % Customers first_cust = str2double(strsplit(strtrim(fgets(f)), ' ')); cust = zeros(n,length(first_cust)); cust(1,:) = first_cust; for i = 2:n cust(i,:) = str2double(strsplit(strtrim(fgets(f)), ' ')); end % Depots first_depot = str2double(strsplit(strtrim(fgets(f)), ' ')); depot = zeros(t,length(first_depot)); depot(1,:) = first_depot; for i = 2:t depot(i,:) = str2double(strsplit(strtrim(fgets(f)), ' ')); end fclose(f); % Close it up return endCopy the code4. Operation results
Matlab version and references
1 matlab version 2014A
[1] Yang Baoyang, YU Jizhou, Yang Shan. Intelligent Optimization Algorithm and Its MATLAB Example (2nd Edition) [M]. Publishing House of Electronics Industry, 2016. [2] ZHANG Yan, WU Shuigen. MATLAB Optimization Algorithm source code [M]. Tsinghua University Press, 2017.