【TWVRP】基于matlab蚁群算法求解带时间窗的多中心车辆路径规划问题【含Matlab源码 113期】
【摘要】
一、VRP简介
1 VRP基本原理 车辆路径规划问题(Vehicle Routing Problem，VRP)是运筹学里重要的研究问题之一。VRP关注有一个供货商与K个销售点的路径规划的情况，可以简述为...
一、VRP简介
1 VRP基本原理
车辆路径规划问题(Vehicle Routing Problem，VRP)是运筹学里重要的研究问题之一。VRP关注有一个供货商与K个销售点的路径规划的情况，可以简述为：对一系列发货点和收货点，组织调用一定的车辆，安排适当的行车路线，使车辆有序地通过它们，在满足指定的约束条件下（例如：货物的需求量与发货量，交发货时间，车辆容量限制，行驶里程限制，行驶时间限制等），力争实现一定的目标（如车辆空驶总里程最短，运输总费用最低，车辆按一定时间到达，使用的车辆数最小等）。
VRP的图例如下所示：
2 问题属性与常见问题
车辆路径问题的特性比较复杂，总的来说包含四个方面的属性：
（1）地址特性包括：车场数目、需求类型、作业要求。
（2）车辆特性包括：车辆数量、载重量约束、可运载品种约束、运行路线约束、工作时间约束。
（3）问题的其他特性。
（4）目标函数可能是总成本极小化，或者极小化最大作业成本，或者最大化准时作业。
3 常见问题有以下几类：
（1）旅行商问题
（2）带容量约束的车辆路线问题(CVRP)
该模型很难拓展到VRP的其他场景,并且不知道具体车辆的执行路径，因此对其模型继续改进。
（3）带时间窗的车辆路线问题
由于VRP问题的持续发展，考虑需求点对于车辆到达的时间有所要求之下，在车辆途程问题之中加入时窗的限制，便成为带时间窗车辆路径问题（VRP with Time Windows, VRPTW）。带时间窗车辆路径问题（VRPTW）是在VRP上加上了客户的被访问的时间窗约束。在VRPTW问题中，除了行驶成本之外, 成本函数还要包括由于早到某个客户而引起的等待时间和客户需要的服务时间。在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同。
模型2(参考2017 A generalized formulation for vehicle routing problems)：
该模型为2维决策变量
（4）收集和分发问题
（5）多车场车辆路线问题
参考(2005 lim，多车场车辆路径问题的遗传算法_邹彤, 1996 renaud)
由于车辆是同质的，这里的建模在变量中没有加入车辆的维度。
（6）优先约束车辆路线问题
（7）相容性约束车辆路线问题
（8）随机需求车辆路线问题
4 解决方案
（1）数学解析法
（2）人机交互法
（3）先分组再排路线法
（4）先排路线再分组法
（5）节省或插入法
（6）改善或交换法
（7）数学规划近似法
（8）启发式算法
5 VRP与VRPTW对比
二、蚁群算法简介
1 蚁群算法(ant colony algorithm,ACA)起源和发展历程
Marco Dorigo等人在研究新型算法的过程中，发现蚁群在寻找食物时，通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标，于是在1991年在其博士论文中首次系统地提出一种基于蚂蚁种群的新型智能优化算法“蚂蚁系统（Ant system,简称AS）”，后来，提出者及许多研究者对该算法作了各种改进，将其应用于更为广泛的领域，如图着色问题、二次分配问题、工件排序问题、车辆路径问题、车间作业调度问题、网络路由问题、大规模集成电路设计等。近些年来，M.Dorigo等人把蚂蚁算法进一步发展成一种通用的优化技术“蚁群优化（Ant Colony Optimization,简称ACO）”，并将所有符合ACO框架的算法称为“蚁群优化算法（ACO algorithm）”。
具体来说，各个蚂蚁在没有事先告知食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)信息素能够让其他蚂蚁感知从而起到一个引导的作用。通常多个路径上均有信息素时，蚂蚁会优先选择信息素浓度高的路径，从而使浓度高的路径信息素浓度更高，形成一个正反馈。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。最终，信息素浓度最高的路径即是最终被蚂蚁选中的最优路径。
与其他算法相比，蚁群算法是一种比较年轻的算法，具有分布式计算、无中心控制、个体之间异步间接通信等特点，并且易于与其他优化算法相结合，经过不少仁人志士的不断探索，到今天已经发展出了各式各样的改进蚁群算法，不过蚁群算法的原理仍是主干。
2 蚁群算法的求解原理
基于上述对蚁群觅食行为的描述，该算法主要对觅食行为进行以下几个方面模拟：
（1）模拟的图场景中包含了两种信息素，一种表示家，一种表示食物的地点，并且这两种信息素都在以一定的速率进行挥发。
（2）每个蚂蚁只能感知它周围的小部分地方的信息。蚂蚁在寻找食物的时候，如果在感知范围内，就可以直接过去，如果不在感知范围内，就要朝着信息素多的地方走，蚂蚁可以有一个小概率不往信息素多的地方走，而另辟蹊径，这个小概率事件很重要，代表了一种找路的创新，对于找到更优的解很重要。
（3）蚂蚁回窝的规则与找食物的规则相同。
（4）蚂蚁在移动时候首先会根据信息素的指引，如果没有信息素的指引，会按照自己的移动方向惯性走下去，但也有一定的机率改变方向，蚂蚁还可以记住已经走过的路，避免重复走一个地方。
（5）蚂蚁在找到食物时留下的信息素最多，然后距离食物越远的地方留下的信息素越少。找到窝的信息素留下的量的规则跟食物相同。蚁群算法有以下几个特点:正反馈算法、并发性算法、较强的鲁棒性、概率型全局搜索、不依赖严格的数学性质、搜索时间长，易出现停止现象。
蚂蚁转移概率公式：
公式中：是蚂蚁k从城市i转移到j的概率；α，β分别为信息素和启发式因子的相对重要程度；为边（i，j）上的信息素量；为启发式因子；为蚂蚁k下步允许选择的城市。上述公式即为蚂蚁系统中的信息素更新公式，是边（i,j)上的信息素量；ρ是信息素蒸发系数，0<ρ<1;为第k只蚂蚁在本次迭代中留在边（i,j）上的信息素量；Q为一正常系数；为第k只蚂蚁在本次周游中的路径长度。
在蚂蚁系统中，信息素更新公式为：
3 蚁群算法的求解步骤：
（1）初始化参数在计算之初，需要对相关参数进行初始化，如蚁群规模（蚂蚁数量）m、信息素重要程度因子α、启发函数重要程度因子β、信息素会发银子ρ、信息素释放总量Q、最大迭代次数iter_max、迭代次数初值iter=1。
（2）构建解空间将各个蚂蚁随机地置于不同的出发点，对每个蚂蚁k（k=1,2,3…m），按照（2-1）计算其下一个待访问城市，直到所有蚂蚁访问完所有城市。
（3）更新信息苏计算每个蚂蚁经过路径长度Lk(k=1,2,…，m），记录当前迭代次数中的最优解（最短路径）。同时，根据式（2-2）和（2-3）对各个城市连接路径上信息素浓度进行更新。
（4） 判断是否终止若iter<iter_max，则令iter=iter+1,清空蚂蚁经过路径的记录表，并返回步骤2；否则，终止计算，输出最优解。
（5）判断是否终止若iter<iter_max，则令iter=iter+1,清空蚂蚁经过路径的记录表，并返回步骤2；否则，终止计算，输出最优解。3. 判断是否终止若iter<iter_max，则令iter=iter+1,清空蚂蚁经过路径的记录表，并返回步骤2；否则，终止计算，输出最优解。
三、部分源代码
function varargout = AntColonyVRPGUI(varargin)
% ANTCOLONYVRPGUI M-file for AntColonyVRPGUI.fig
% ANTCOLONYVRPGUI, by itself, creates a new ANTCOLONYVRPGUI or raises the existing
% singleton*.
%
% H = ANTCOLONYVRPGUI returns the handle to a new ANTCOLONYVRPGUI or the handle to
% the existing singleton*.
%
% ANTCOLONYVRPGUI('CALLBACK',hObject,eventData,handles,...) calls the local
% function named CALLBACK in ANTCOLONYVRPGUI.M with the given input arguments.
%
% ANTCOLONYVRPGUI('Property','Value',...) creates a new ANTCOLONYVRPGUI or raises the
% existing singleton*. Starting from the left, property value pairs are
% applied to the GUI before AntColonyVRPGUI_OpeningFcn gets called. An
% unrecognized property name or invalid value makes property application
% stop. All inputs are passed to AntColonyVRPGUI_OpeningFcn via varargin.
%
% *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one
% instance to run (singleton)".
%
% See also: GUIDE, GUIDATA, GUIHANDLES
% Edit the above text to modify the response to help AntColonyVRPGUI
% Last Modified by GUIDE v2.5 11-Jun-2015 00:13:48
% Begin initialization code - DO NOT EDIT
gui_Singleton = 1;
gui_State = struct('gui_Name', mfilename, ...
'gui_Singleton', gui_Singleton, ...
'gui_OpeningFcn', @AntColonyVRPGUI_OpeningFcn, ...
'gui_OutputFcn', @AntColonyVRPGUI_OutputFcn, ...
'gui_LayoutFcn', [] , ...
'gui_Callback', []);
if nargin && ischar(varargin{1})
gui_State.gui_Callback = str2func(varargin{1});
end
if nargout
[varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
else
gui_mainfcn(gui_State, varargin{:});
end
% End initialization code - DO NOT EDIT
% --- Executes just before AntColonyVRPGUI is made visible.
function AntColonyVRPGUI_OpeningFcn(hObject, eventdata, handles, varargin)
% This function has no output args, see OutputFcn.
% hObject handle to figure
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% varargin command line arguments to AntColonyVRPGUI (see VARARGIN)
% Choose default command line output for AntColonyVRPGUI
handles.output = hObject;
%% change !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
handles.ismdvrp = true; %!!!
%%
if handles.ismdvrp == true
[handles.initClusters, handles.coordinates] = INIT;
handles.clusters = handles.initClusters;
set(handles.uipanelBases,'Visible','on');
create_init_plot_MDVRP(handles.coordinates, handles.clusters);
else
%initialization
[vehicles,demands,dist_stations,dist_bases] = INIT_VRP;
handles.vehicles = vehicles;
handles.demands = demands;
handles.distances_stations = dist_stations;
handles.distances_bases = dist_bases;
set(handles.uipanelBases,'Visible','off');
end
% Update handles structure
guidata(hObject, handles);
% UIWAIT makes AntColonyVRPGUI wait for user response (see UIRESUME)
% uiwait(handles.figure1);
% --- Outputs from this function are returned to the command line.
function varargout = AntColonyVRPGUI_OutputFcn(hObject, eventdata, handles)
% varargout cell array for returning output args (see VARARGOUT);
% hObject handle to figure
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Get default command line output from handles structure
varargout{1} = handles.output;
% --- Executes on selection change in algorithmPopupmenu.
function algorithmPopupmenu_Callback(hObject, eventdata, handles)
% hObject handle to algorithmPopupmenu (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: contents = cellstr(get(hObject,'String')) returns algorithmPopupmenu contents as cell array
% contents{get(hObject,'Value')} returns selected item from algorithmPopupmenu
%set invisible error messages
set(handles.errorMandatoryEditFields,'Visible','off');
%erase text in edit fields
set(handles.evaporationPheromoneEdit,'String','');
set(handles.attractStationEdit,'String','');
set(handles.increasePheromoneEdit,'String','');
set(handles.amountPheromoneEdit,'String','');
set(handles.eliteAntsEdit,'String','');
%set disabled all edit fields
set(handles.evaporationPheromoneEdit,'Enable','off');
set(handles.attractStationEdit,'Enable','off');
set(handles.increasePheromoneEdit,'Enable','off');
set(handles.amountPheromoneEdit,'Enable','off');
set(handles.eliteAntsEdit,'Enable','off');
%set disabled run button
set(handles.runButton,'Enable','off');
%set to 0 all results
set(handles.lengthWayText,'String','-');
set(handles.subroutesNText,'String','-');
set(handles.timeSpentText,'String','-');
if handles.ismdvrp == true
%set invisible bases' listbox
set(handles.listboxBases,'Visible','off');
set(handles.totalLengthText,'Visible','off');
set(handles.totalLengthText,'String','-');
set(handles.totalLengthLabel,'Visible','off');
%clear plot
cla;
create_init_plot_MDVRP(handles.coordinates, handles.clusters);
end
%clear plot
%cla;
%clear legend
legend('off');
val = get(hObject,'Value');
if val ~= 1 %not placeholder's text (not be executed)
if val ~= 2 %not Clark-Wright algorithm
%enable edit fields
if val == 5 %AntAlg with elite ants
set(handles.eliteAntsEdit,'Enable','on');
end
set(handles.evaporationPheromoneEdit,'Enable','on');
set(handles.attractStationEdit,'Enable','on');
set(handles.increasePheromoneEdit,'Enable','on');
set(handles.amountPheromoneEdit,'Enable','on');
end
%enable run button
set(handles.runButton,'Enable','on');
end
% --- Executes during object creation, after setting all properties.
function algorithmPopupmenu_CreateFcn(hObject, eventdata, handles)
% hObject handle to algorithmPopupmenu (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: popupmenu controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function evaporationPheromoneEdit_Callback(hObject, eventdata, handles)
% hObject handle to evaporationPheromoneEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of evaporationPheromoneEdit as text
% str2double(get(hObject,'String')) returns contents of evaporationPheromoneEdit as a double
% --- Executes during object creation, after setting all properties.
function evaporationPheromoneEdit_CreateFcn(hObject, eventdata, handles)
% hObject handle to evaporationPheromoneEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function attractStationEdit_Callback(hObject, eventdata, handles)
% hObject handle to attractStationEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of attractStationEdit as text
% str2double(get(hObject,'String')) returns contents of attractStationEdit as a double
% --- Executes during object creation, after setting all properties.
function attractStationEdit_CreateFcn(hObject, eventdata, handles)
% hObject handle to attractStationEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function increasePheromoneEdit_Callback(hObject, eventdata, handles)
% hObject handle to increasePheromoneEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of increasePheromoneEdit as text
% str2double(get(hObject,'String')) returns contents of increasePheromoneEdit as a double
% --- Executes during object creation, after setting all properties.
function increasePheromoneEdit_CreateFcn(hObject, eventdata, handles)
% hObject handle to increasePheromoneEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function amountPheromoneEdit_Callback(hObject, eventdata, handles)
% hObject handle to amountPheromoneEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of amountPheromoneEdit as text
% str2double(get(hObject,'String')) returns contents of amountPheromoneEdit as a double
% --- Executes during object creation, after setting all properties.
function amountPheromoneEdit_CreateFcn(hObject, eventdata, handles)
% hObject handle to amountPheromoneEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function eliteAntsEdit_Callback(hObject, eventdata, handles)
% hObject handle to eliteAntsEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of eliteAntsEdit as text
% str2double(get(hObject,'String')) returns contents of eliteAntsEdit as a double
% --- Executes during object creation, after setting all properties.
function eliteAntsEdit_CreateFcn(hObject, eventdata, handles)
% hObject handle to eliteAntsEdit (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
% --- Executes on button press in runButton.
function runButton_Callback(hObject, eventdata, handles)
% hObject handle to runButton (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
%clear legend
legend('off');
%clear plot
%cla;
%set invisible error messages
set(handles.errorMandatoryEditFields,'Visible','off');
indexAlg = get(handles.algorithmPopupmenu,'Value');
if indexAlg ~= 1 %not placeholder's text (not be executed)
if indexAlg ~= 2 %not Clark-Wright algorithm
if indexAlg == 5 %AntAlg with elite ants
if isempty(get(handles.eliteAntsEdit,'String'))
set(handles.errorMandatoryEditFields,'Visible','on');
return;
end
end
if ( isempty(get(handles.evaporationPheromoneEdit,'String')) || ...
isempty(get(handles.attractStationEdit,'String')) || ...
isempty(get(handles.increasePheromoneEdit,'String')) || ...
isempty(get(handles.amountPheromoneEdit,'String')) )
set(handles.errorMandatoryEditFields,'Visible','on');
return;
end
end
%set disabled run button
set(handles.runButton,'Enable','off');
if handles.ismdvrp == true
clusters = runAlgorithmMDVRP(indexAlg, handles);
handles.clusters = clusters;
listbox=findall(gcf,'tag','listboxBases');
guidata(listbox,handles);
%select first value in bases' listbox
set(handles.listboxBases,'Value',1);
listboxBases_Callback(listbox, eventdata, handles);
else
runAlgorithmVRP(indexAlg, handles);
end
%set enabled run button
set(handles.runButton,'Enable','on');
%set enabled zoom tools
set(handles.toolZoomIn,'Enable','on');
set(handles.toolZoomOut,'Enable','on');
%set enabled pan tool
set(handles.toolPan,'Enable','on');
zoom reset;
end
function [clusters] = runAlgorithmMDVRP(index, handles)
if index ~= 1
if index ~= 2
e = str2double(get(handles.evaporationPheromoneEdit,'String'));
alpha = str2double(get(handles.attractStationEdit,'String'));
beta = str2double(get(handles.increasePheromoneEdit,'String'));
tau0 = str2double(get(handles.amountPheromoneEdit,'String'));
E = str2double(get(handles.eliteAntsEdit,'String'));
end
try
tStart = tic; %start spent time
clusters = handles.initClusters;
handles.clusters = clusters;
basesName = cell(1,length(clusters)+1);
basesName{1} = 'Full view';
for c = 1:length(clusters)
switch index
case 2 %Clark-Wright
[ Route, RouteLength, vehicles ] = Clark_Wright_VRP( ...
clusters(c).demands, clusters(c).diststations, ...
clusters(c).distbases, clusters(c).vehicles_capacity );
case 3 %Ant-minpath
[Route, RouteLength, vehicles] = ANT_colony_algorithm_VRP_minpath( ...
clusters(c).diststations, clusters(c).distbases, ...
clusters(c).demands, [e alpha beta tau0], clusters(c).vehicles_capacity );
case 4 %Ant-partition
[Route, RouteLength, vehicles] = ANT_colony_algorithm_VRP( ...
clusters(c).diststations, clusters(c).distbases, ...
clusters(c).demands, [e alpha beta tau0], clusters(c).vehicles_capacity );
case 5 %Ant-elite ants
[Route, RouteLength, vehicles] = ANT_colony_algorithm_VRP_with_elite_ants( ...
clusters(c).diststations, clusters(c).distbases, ...
clusters(c).demands, [e alpha beta tau0 E], clusters(c).vehicles_capacity );
end
handles.clusters(c).mdvrp = changeStations(clusters, vehicles, RouteLength, Route, c);
basesName{c + 1} = sprintf('Base #%d',c); %saving bases that need to be added to listbox
end
tElapsed = toc(tStart); %end spent time
catch ME
msgbox(strcat('Error occured: ',ME.message),'Error','error');
end
clusters = handles.clusters;
%clear plot
cla;
create_plot_route_with_vehicles_MDVRP(handles.coordinates, handles.clusters);
set(handles.timeSpentText,'String',sprintf('%fs',tElapsed));
set(handles.listboxBases, 'String', basesName);
set(handles.listboxBases, 'Visible','on');
set(handles.totalLengthText,'String',num2str(getTotalLength(handles.clusters)));
set(handles.totalLengthText,'Visible','on');
set(handles.totalLengthLabel,'Visible','on');
end
function [mdvrp] = changeStations(clusters, vehicles, LR, R, clusterN)
mdvrp = struct('length_route',[],'vehicles',[],'simpleVehicles',[],'num_of_subroutes',[]);
len = length(vehicles);
mdvrp.simpleVehicles = vehicles;
for v = 1:len
vehicles(v).route(vehicles(v).route == 1) = 0;
len_route = length(vehicles(v).route);
for vr = 1:len_route
if vehicles(v).route(vr) ~= 0 %羼腓 礤 徉玎
vehicles(v).route(vr) = clusters(clusterN).stations(vehicles(v).route(vr)-1);
end
end
end
mdvrp.num_of_subroutes = number_of_subroutes(R);
mdvrp.length_route = LR;
mdvrp.vehicles = vehicles;
function [tlength] = getTotalLength(clusters)
tlength = 0;
clen = length(clusters);
for c = 1:clen
tlength = tlength + clusters(c).mdvrp.length_route;
end
function runAlgorithmVRP(index, handles)
if index ~= 1
if index ~= 2
e = str2double(get(handles.evaporationPheromoneEdit,'String'));
alpha = str2double(get(handles.attractStationEdit,'String'));
beta = str2double(get(handles.increasePheromoneEdit,'String'));
tau0 = str2double(get(handles.amountPheromoneEdit,'String'));
E = str2double(get(handles.eliteAntsEdit,'String'));
end
try
tStart = tic; %start spent time
switch index
case 2 %Clark-Wright
[Route,RouteLength,vehicles] = Clark_Wright_VRP( handles.demands, ...
handles.distances_stations, handles.distances_bases, handles.vehicles );
case 3 %Ant-minpath
[Route,RouteLength,vehicles] = ANT_colony_algorithm_VRP_minpath( handles.distances_stations,...
handles.distances_bases, handles.demands, [e alpha beta tau0], handles.vehicles);
case 4 %Ant-partition
[Route,RouteLength,vehicles] = ANT_colony_algorithm_VRP( handles.distances_stations, ...
handles.distances_bases, handles.demands, [e alpha beta tau0], handles.vehicles);
case 5 %Ant-elite ants
[Route,RouteLength,vehicles] = ANT_colony_algorithm_VRP_with_elite_ants( ...
handles.distances_stations, handles.distances_bases, handles.demands, ...
[e alpha beta tau0 E], handles.vehicles);
end
tElapsed = toc(tStart); %end spent time
create_plot_route_with_vehicles( add_bases_to_distances(handles.distances_stations, ...
handles.distances_bases), vehicles, [0 handles.demands] );
catch ME
msgbox(strcat('Error occured: ',ME.message),'Error','error');
end
set(handles.lengthWayText,'String',num2str(RouteLength));
set(handles.subroutesNText,'String',num2str(number_of_subroutes(Route)));
set(handles.timeSpentText,'String',sprintf('%fs',tElapsed));
end
% --------------------------------------------------------------------
function dataTooltip_ClickedCallback(hObject, eventdata, handles)
% hObject handle to dataTooltip (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% --------------------------------------------------------------------
function algorithmTooltip_ClickedCallback(hObject, eventdata, handles)
% hObject handle to algorithmTooltip (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% --- Executes on selection change in listboxBases.
function listboxBases_Callback(hObject, eventdata, handles)
% hObject handle to listboxBases (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: contents = cellstr(get(hObject,'String')) returns listboxBases contents as cell array
% contents{get(hObject,'Value')} returns selected item from listboxBases
%clear legend
legend('off');
%clear plot
cla;
index = get(handles.listboxBases,'value') - 1;
if index == 0 %if user want to see the full graph of routes
create_plot_route_with_vehicles_MDVRP(handles.coordinates, handles.clusters);
set(handles.lengthWayText,'String','-');
set(handles.subroutesNText,'String','-');
else
create_plot_of_base_MDVRP(handles.coordinates, handles.clusters, index);
set(handles.lengthWayText,'String',num2str(handles.clusters(index).mdvrp.length_route));
set(handles.subroutesNText,'String',num2str(handles.clusters(index).mdvrp.num_of_subroutes));
end
% --- Executes during object creation, after setting all properties.
function listboxBases_CreateFcn(hObject, eventdata, handles)
% hObject handle to listboxBases (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: listbox controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
% --------------------------------------------------------------------
function aboutMenu_Callback(hObject, eventdata, handles)
% hObject handle to aboutMenu (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
About %call gui About.m
% --------------------------------------------------------------------
function fileMenu_Callback(hObject, eventdata, handles)
% hObject handle to fileMenu (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% --------------------------------------------------------------------
function anotherVRPSubmenu_Callback(hObject, eventdata, handles)
% hObject handle to anotherVRPSubmenu (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% --------------------------------------------------------------------
function newDataSubmenu_Callback(hObject, eventdata, handles)
% hObject handle to newDataSubmenu (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
- 413
- 414
- 415
- 416
- 417
- 418
- 419
- 420
- 421
- 422
- 423
- 424
- 425
- 426
- 427
- 428
- 429
- 430
- 431
- 432
- 433
- 434
- 435
- 436
- 437
- 438
- 439
- 440
- 441
- 442
- 443
- 444
- 445
- 446
- 447
- 448
- 449
- 450
- 451
- 452
- 453
- 454
- 455
- 456
- 457
- 458
- 459
- 460
- 461
- 462
- 463
- 464
- 465
- 466
- 467
- 468
- 469
- 470
- 471
- 472
- 473
- 474
- 475
- 476
- 477
- 478
- 479
- 480
- 481
- 482
- 483
- 484
- 485
- 486
- 487
- 488
- 489
- 490
- 491
- 492
- 493
- 494
- 495
- 496
- 497
- 498
- 499
- 500
- 501
- 502
- 503
- 504
- 505
- 506
- 507
- 508
- 509
- 510
- 511
- 512
- 513
- 514
- 515
- 516
- 517
- 518
- 519
- 520
- 521
- 522
- 523
- 524
- 525
- 526
- 527
- 528
- 529
- 530
- 531
- 532
- 533
- 534
- 535
- 536
- 537
- 538
四、运行结果
五、matlab版本及参考文献
1 matlab版本
2014a
2 参考文献
[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例（第2版）[M].电子工业出版社，2016.
[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社，2017.
文章来源: qq912100926.blog.csdn.net，作者：海神之光，版权归原作者所有，如需转载，请联系作者。
原文链接：qq912100926.blog.csdn.net/article/details/112553769
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）