一问题重述
现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。
现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见附表表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见附表表1，50个位置点的坐标见附表表2。
假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。
现在送货员要将100件货物送到50个地点。请完成以下问题。
1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。
2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。
3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。
图1 快递公司送货地点示意图
O点为快递公司地点，O点坐标(11000,8250),单位：米
（各货物号及信息见附表一；五十个为位置点的坐标见附表二；各连通位置点之间的相互到达信息见附表三）
二模型假设
一：假定送货员在送货期间不需要休息，且速度保持以二十四公里每小时不变。二：假定送货员只能沿这些连通线路行走，而不能走其它任何路线。
三：假定任一送货员的最大载重为五十公斤，所带货物最大体积为一立方米。四：假定送货员按时上班并且不考虑中午休息时间。
五：假定送货员在送货途时能顺利到达下一个目的地，途中无意外事件的发生。六：假定不存在交接货物延时情况且单件或多件货物交接时交接时间均能按每
件三分钟计算。
三 符号说明
m
为蚁群中蚂蚁数量；
()i b t 为t 时刻位于点i 的蚂蚁个数，且m ＝1
()n
i i b t =∑；
ij d 为城市i 和j 之间的距离；
ij n
为边（i ，j ）的能见度，反映由点i 转移到点j 的启发程度； ij τ
为边（i ，j ）上的信息素轨迹强度；
ij τ
为蚂蚁k 在边（i ，j ）上留下的单位长度轨迹信息素量； k ij p 为蚂蚁k 的转移概率； J 是尚未访问的城市。 n 为城市个数
C
为n 个城市的坐标，n ×2的矩阵
NC_max 最大迭代次数 M
为蚂蚁个数
Alpha 表征信息素重要程度的参数 Beta 表征启发式因子重要程度的参数 Rho 信息素蒸发系数 Q
信息素增加强度系数 R_best 各代最佳路线 L_best
各代最佳路线的长度
四 问题分析
问题一：
此问题研究如何最快地将货物送到指定地点并返回。问题中不考虑时间限制，由于送货时涉及到最大载重量和最大体积，所以此处我们先考虑前30件货物的总重量 m 和总体积 v ，经过计算得：m =48.5公斤， 1V =0.88立方米。
所有需运送的货物重量及体积均未达最大承受值。即送货员可往复一次将所要求货物送完。因此该问题是经典的最佳旅行售货员回路的求解问题。 问题二：
由简单计算可得30件货物的质量和体积均在送货员一次送货运载能力范围内，此时问题等价于在第一问中添加了时间限制因素。在这种条件下，一种极端的情况送货员沿任意一条路径送递完全部货物,都能满足所有货物的时限要求,这时问题已变成了第一问中一般的TSP 问题;在另一种极端情况下,一个送货员不可能在规定的时限内将全部货物送达,即问题无解。经过计算，可知第二问中的描述属于中间情况，故可将其进行组合优化得到最优解。
五 模型的建立及求解
问题一：建立图论模型。在此采用蚁群算法进行求解。
第一步：初始化，将所有送货点坐标列出，并计算出关联两点之间的距离，对于不关联的两点距离赋给一个很大的值，以便于求解。在利用蚁群算法求解赋权图(,)G V E =的最佳旅行售货员回路中，需先求出G 中任意两个顶点之间的最短路径，然后构造一个完全赋权图'G '(,)V E =,'(,),(,)min (,)G i j E i j d i j ω?∈=。求解任意两顶点的最短路采用Floyd 算法。为得到最短路径，设路径矩阵R ，i 到j 之间经过的点()k ij r ，()()2525()k k ij R r ?=。
利用Floyd 算法求解完全赋权图：输入带权邻接矩阵2525((,))W i j ω?= （1） 赋初值：对所有,i j ，(,)(,),(,), 1.d i j i j r i j j k ω←←← （2） 更新：对所有i,j,若(,)(,)(,)d i k d k j d i j +<，则
(,)(,)(,),(,).d i j d i k d k j r i j k ←+←
（3） 若25,k =停止运算；否则1,k k ←+重复（2）（3）.
（4） 若()1,k ij r a =则点1a 是i 到j 的最短路的中间点。然后用同样方法查找。
第二步：用蚁群算法迭代一次，得出一个最优解，由此来计算出max τ和min τ的大小。由max τ得到信息素的初值，然后进行信息素更新，判断是否超出（max τ，min τ）范围，如果超出，则限制大小。
第三步：继续迭代，直到第三次，得到min τ。判断信息素是否超出（max τ，min τ），如果超出，则限制大小。
第四步：往复迭代计算，直到达到最大迭代次数。每一次计算都得出新的最优解，所以每一次计算中，max τ和min τ都会重新被更新，是一个动态变化范围。
第五步：输出最后结果。
利用Matlab 程序进行计算 （为便于计算，现将货物送达地点重新进行编号，其对应关系及位置点坐标见附表）得出结果：
路线：0—18—13—19—24—31—27—39—27—31—34—40—45—42—49—42—43—38—36—38—35—32—23—16—14—17—21—26—0
路程：54668m 路线图
问题二：
该问题是在第一个问题的前提下加入了时间的限制，要求在指定时间内将货物送到指定地点，并且仍然保持运货距离最短。在这种条件下，一种极端的情况送货员沿任意一条路径送递完全部货物,都能满足所有货物的时限要求,这时问题已变成了第一问中一般的TSP问题;在另一种极端情况下,一个送货员不可能在规定的时限内将全部货物送达,即问题无解。经过计算，可知第二问中的描述属于中间情况，故可将其进行组合优化得到最优解。
所以我们在第一个问题最短距离的前提下对第二个问题进行优化，按照问题二给出的时间限制对送货点进行分组：
由于1—30号货物的总质量=48.5公斤，总体积=0.88立方米，所以可以不考虑质量和体积对送货的影响。
按照上表的分组，我们根据优先运送限制时间早的货物，在前一组货物不超过规定时间的前提下可运送后面的货物。根据约束时间、最短距离、节约矩阵的限制，再参照问题一的最优解：
0—18—13—19—24—31—27—39－27－31—34—40—45—49—42—43—38—35—32—23—16—14—17—21—26—0
若按照问题一的最优解路径运送，45号送货点不能按时到达，因此我们将第四组中的27、39号送货点暂不送货，得出前三组的送货路线：0－18－13－19－24－31－34－40－45－42－49－42－43－38
对于第四组的送货点，我们采取Dijkstra算法求出38号送货点到起始点的最短距离及最短路径：
38－35－32－23－16－14－17－21－36－27－39－27－31－26－0
于是我们得出一个近似最优解：
0－18－13－19－24－31－34－40－45－42－49－42－43－38－35－32－23－16－14－17－21－36－27－39－27－31－26－0
此路径距离为54952米，需要时间3.79h。
路线图：
六模型的优缺点
优点：
一：对于本案例建立的模型简单。能够将较复杂的问题在符合逻辑的前提下，将问题大大简化，忽略一些对结果影响较小的,偶然的或不合理的因素，使我们能够抓住主要矛盾，忽略次要矛盾，最终使我们能较快的在一定误差范围内得到一个更加合理的结果。
二：对于本案例所建立的模型有较强的适应性。我们所建立的模型也是一种优化模型，在解决许多问题时，如：线路部设问题，运输安排问题，厂区布局问题旅游最短线路问题及管道输水等优化问题时有很好的适应性，通用型，优越性。缺点：
一：本文中所建立的模型是在忽略了许多次要因素的前提下建立起来的，但在实际中这些因素是不能忽略的。因此，通过本文中所建立的模型得出的结果和实际有一定的偏差，而且偏差的大小是无法估算和预测的。
二：在本案例所建模型中运用到的蚁群算法无法得出最优结果，此算法只能得到
近似最优解，即在模型假设中所给的限定条件下，排除掉一些次要因素后通过本案例所建模型仍无法得到最优解。
七模型的推广
本案例建立了图论模型，可以将其扩展到很多生活中的实际问题中。对于生活中的很多复杂问题都有一定的帮助和指导作用。首先，在问题一中我们用到Floyd 算法求取从某指定点到其余个顶点的最短路，此算法在解决线路部设，运输安排，厂区布局等问题时有重要意义。其次，我们在问题一中用到了蚁群算法。这种算法有别于传统编程模式，其优势在于，避免了冗长的编程和筹划，程序本身是基于一定规则的随机运行来寻找最佳配置。此外，一群算法的思想不仅可以用在数学上，还可以用在其他学科上。本文中所建立的模型能解决许多生活中的实际问题，但由此模型所得出的结论是在一定条件限制下得出的，因此，它有一定的局限性。
八参考文献
[1]段海滨《蚁群算法原理及其应用》[M].北京：科学出版社.2005 .
[2]李明海邢桂华.《用MATLAB实现中国旅行商问题的求解》[J].《微计算机应用》，20047，第25卷第2期.218－222.
[3] 李士勇.《蚁群算法及其应用》[M].哈尔滨：哈尔滨工业大学出版社.2004.
[4] 肖华勇。《使用数学建模与软件应用》。西北工业大学出版社。
[5] 刘士新，刘玲，张涛《求解VRPBTW的变邻域搜索算法》.东北大学学报。
[6]张志涌，《Matlab教程》.北京航空航天大学出版社。
九附录
附录一
附表1 各货物号信息表
附表2 50个位置点的坐标
附表3 各连通点位置点之间相互到达信息
附表四
附录二
问题一的Matlab程序
第一步：变量初始化
n=size(C,1); %n表示问题的规模（点的个数）
D=zeros(n,n); %D表示完全图的赋权邻接矩阵
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps; %i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps （浮点相对精度）表示
end
D(j,i)=D(i,j); %对称矩阵
end
end
Eta=1./D; %Eta为启发因子，这里设为距离的倒数
Tau=ones(n,n); %Tau为信息素矩阵
Tabu=zeros(m,n); %存储并记录路径的生成
NC=1; %迭代计数器，记录迭代次数
R_best=zeros(NC_max,n); %各代最佳路线
L_best=inf.*ones(NC_max,1); %各代最佳路线的长度
L_ave=zeros(NC_max,1); %各代路线的平均长度
while NC<=NC_max %停止条件之一：达到最大迭代次数，停止
第二步：将m只蚂蚁放到n个点上
Randpos=[]; %随即存取
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';
第三步：m只蚂蚁按概率函数选择下一个点，完成各自的周游
for j=2:n %所在点不计算
for i=1:m
visited=Tabu(i,1:(j-1)); %记录已访问的点，避免重复访问
J=zeros(1,(n-j+1)); %待访问的点
P=J; %待访问点的选择概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0 %开始时置0
J(Jc)=k;
Jc=Jc+1; %访问的点个数自加1
end
end
%下面计算待选点的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原则选取下一个点
Pcum=cumsum(P); %cumsum，元素累加即求和
Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end
第四步：记录本次迭代最佳路线
L=zeros(m,1); %开始距离为0，m*1的列向量
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1)); %原距离加上第j个点到第j+1个点的距离end
L(i)=L(i)+D(R(1),R(n)); %一轮下来后走过的距离
end
L_best(NC)=min(L); %最佳距离取最小
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线
L_ave(NC)=mean(L); %此轮迭代后的平均距离
NC=NC+1 %迭代继续
第五步：更新信息素
Delta_Tau=zeros(n,n); %开始时信息素为n*n的0矩阵
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i); %此次循环在路径（i，j）上的信息素增量
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
%此次循环在整个路径上的信息素增量
end
Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发，更新后的信息素
第六步：禁忌表清零
Tabu=zeros(m,n); %%直到最大迭代次数
end
第七步：输出结果
Pos=find(L_best==min(L_best)); %找到最佳路径（非0为真）
Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径
Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离
end
注：问题中蚂蚁数量m＝200；信息素重要程度的参数Alpha=1;启发因子重要程度的参数Beta=5;信息素蒸发系数Rho=0.1;最大迭代次数NC_max=200;信息素增加强度系数Q=100。相关点的坐标见附表四。
送货路线设计问题 送货线路设计问题 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。 现在送货员要将100件货物送到50个地点。请完成以下问题。 1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。 2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。 3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。
以上各问尽可能给出模型与算法 送货路线设计模型 一.摘要 本文是关于快递公司送货路线设计问题，即在给定送货地点和给定设计规范的条件下，确定送货员的最短运行线路，即耗时最少的送货线路。本文为了能够全面的利用所有的数据，决定建立模型一：采用“D-J模型”。在此模型中，运用Dijkstra算法和Kruskal算法相结合求解,然后套用此模型可以得到最优的结果是：送货员所走过的总路程：56.27114573千米；送完全部货物所需时间：3.8446小时。 本文为了能够解决更通俗的套用模型，由此建立模型二：“分析&递推模型”。在此模型中利用分析法和递归的思路建立动态的方法求得最优化结果来相结合求解,然后套用此模型可以得到最优的结果是：送货员所走过的总路程：60.04552405千米送完全部货物所需时间：4.001896835小时。 在问题一的基础上，加多的时间的限制，利用模型二，求出送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间的最快完成的结果是：送货员所走过的总路程59.2435千米送完全部货物所需时间：3.96848小时。
实训0501：配送线路优化设计实训 实训目标： 1、能根据给出的配送中心与单个客户之间的路线图及图中各节点之间的综合成本数值， 找到配送中心与单个客户之间的成本最小路线并计算出此路线成本的数值。 2、能够在配送中心现有送货车辆能力及实际送货成本限定的前提下，规划出配送中心 往各个客户送货综合成本最低的送货网络路径图。 实训内容： 1、某配送中心与某单个客户之间成本最小路线规划及最小成本数值计算 2、在配送中心现有车辆送货能力及车辆单趟送货成本有限定的前提下，为配送中 心向多个客户送货规划若干条送货线路，并使各条线路的总成本数最小。 环境要求：普通多媒体机房教室 情境描述： 实训第1部分情境：某连锁超市的配送中心位于城市边缘的郊区，但超市的一家门店位于繁华的城市中心区，因此负责送货路线规划的计划调度员要规划出配送中心到这个门店的送货成本最低的路线。最初按交通图所示里程最短的线路进行送货，见下图： 图中O代表配送中心，A代表门店，V1—V4代表要经过的关键节点（如主要道路的交叉路口、立体交叉互通枢纽等），连线边上的数值代表每一路段的里程，图中绿线连接的O-V1-V4-A为里程最短线路。 但很快发现里程最短并不意味着成本最低，因为里程最短这条路有一条新建的大桥（图中V4点与A点之间黑色加粗部分）来回都要收取通行费，这条路是城区主干道且建成时间较长通行条件较差，越往城中心走道路拥堵越严重，每趟送货产生的油耗、车辆送货时间占用、送货人员工作时间等综合成本超出了正常水平，并且多次发生没按门店的要求时间送达的情况。因此计划调度员对每一条能从O到A的线路都进行了实地勘察记录，并综合考虑每条送货线路的里程、时间、车辆耗损，得出了每条线路每一个路段的送货运行成本，汇总出了一张从配送中心到此门店的送货路径数据图。现在计划调度员要依据此图，找出配送中心与该门店之间送货成本最低路径。 实训第2部分情境：该配送中心除为该门店送货外，还为其他地区的9个门店送货，按照实训第1部分的方法，计划调度员找到了配送中心到每个门店的成本最低线路，但配送中心的送货资源有限，不能为每个门店单独送货，只能一辆车一趟为几个门店循环送货。这样从一个门店到另一个门店之间也要找到成本最低的线路，因此同样采用实训第1部分的方法，找到了两两门店之间的成本最低线路并计算出了数值。现在，计划调度员要规划从配送中心出发为各个门店循环送货后最终回到配送中心的送货路线总规划图并且总送货成本要
山西工商学院 毕业设计 题目浅析物流配送路径优化问题 学生姓名杨美玲 学号200822054247 专业物流管理 班级08物流二班 指导教师李桂娥 二零一一年十月二十八日
目录 摘要 (ⅰ) 一、引言（问题的提出） (1) 二、物流配送路径优化问题的数学模型……………………………X 三、物流配送路径优化问题的遗传算法……………………………X （一）遗传算法的基本要素………………………………………X （二）物流配送路径优化问题的遗传算法的构造……………………X 四、实验计算与结果分析…………………………………………X 五、结论…………………………………………………………X 参考文献…………………………………………………………X 致谢………………………………………………………………X
中英文摘要 摘要：论文在建立物流配送路径优化问题的数学模型的基础上，构造了求解该问题的遗传算法，并进行了实验计算。计算结果表明，用遗传算法进行物流配送路径优化，可以方便有效地求得问题的最优解或近似最优解。 关键词：物流配送；遗传算法；优化 Study on the Optimizing of Physical Distribution Routing Problem Based on Genetic Algorithm Abstract：On the basis of establishing the optimizing model on physical distribution routing problem, this paper presents a genetic algorithm for solving this problem, and make some experimental calculations. The experimental calculation results demonstrates that the optimal or nearly optimal solutions to the physical distribution routing problem can be easily obtained by using genetic algorithm. Keywords：physical distributio n；genetic algorith m；optimizing
送货线路设计问题
目录 摘要 (5) 1问题重述 (5) 2模型的假设 (5) 3符号说明 (5) 4.问题分析 (6) 5．模型的建立与求解 (7) 5.1问题一 (7) 5.2问题二 (8) 5.2.1模型的建立 (8) 5.2.2模型的求解 (9) 5.3问题三 (9) 5.3.2模型的求解 (9) 6模型的检验 (9) 7模型的评价 (9) 7.1模型的优点 (9) 7.2模型的缺点 (9) 参考文献 (9) 附录 (10)
摘要 最短路径作为现代优化算法研究的一个经典问题一直在工程规划，网络系统，物流运输，通信和军事运筹学等领域有着十分广泛的应用，基于对成本，效率和限制条件的考虑，可以设计一可行性方案十七耗时最少，路径最短。 通过对本题要解决问题的分析，它既不是一个完全的TSP问题，也不是一个完全的欧拉回路问题，但它可转化为在遍历所有所有要送达货物接收点的前提下，是总路程最短，用遗传算法得出最短路径图，同时将所求问题转化为0-1整数规划，求出一个最优哈米尔顿回路 问题一：将1~30号货物送到指定地点并返回，构造最优哈米尔顿回路，将问题转化成遗传问题，设计出最快完成路线与方式，给出路程长度和所用时间，标出送货路线图。 问题二：在问题一的基础上，需要考虑时间的限制的情况下，即在满足时间条件约束的条件下求得最优解的问题，从而转化为多目标规划模型，设计最佳方案，标出最快完成路线。 问题三：送货员所能承载货物的最大质量和最大体积有限，既需要考虑送货员的承载能力的情况下，达到送货时间最短，通过一次送货的重量和体积的限制与尽量将最小生成树的枝节点靠近主干划分为三个区域，在每个区域中通过遗传算法求出最优的哈米尔顿回路，从而得到最短送完所有货物的最优方案，并标出送货线路。 关键词：遗传算法最优哈米尔顿回路最小生成树多目标优化 1问题重述 2模型的假设 对于上述实际问题，我们给了合理的假设： （1）假设送货员回到出发点O后取货时间不计，到达货物接收点的时间不包括此次在该点的交易时间； （2）假设送货车在路上不会出现故障或堵车，运送货物不会出现丢失或损坏；（3）对与某些至少要经过两次以上的货物接收点，认为第一次经过时就把所有货物一次送到。 3符号说明
快递员配送路线优化模型 摘要 如今，随着网上购物的流行，快递物流行业在面临机遇的同时也需要不断迎接新的挑战。如何能够提高物流公司的配送效率并降低配送过程中的成本，已成为急需我们解决的一个问题。下面，本文将针对某公司的一名配送员在配送货物过程中遇到的三个问题进行讨论及解答。 对于问题一，由于快递员的平均速度及在各配送点停留的时间已知，故可将最短时间转换为最短路程。在此首先通过Floyd求最短路的算法，利用Matlab 程序将仓库点和所有配送点间两两的最短距离求解出来，将出发点与配送点结合起来构造完备加权图，由完备加权图确定初始H圈，列出该初始H圈加点序的距离矩阵，然后使用二边逐次修正法对矩阵进行翻转，可以求得近似最优解的距离矩阵，从而确定近似的最佳哈密尔顿圈，即最佳配送方案。 对于问题二，依旧可以将时间问题转化为距离问题。利用问题一中所建立的模型，加入一个新的时间限制条件，即可求解出满足条件的最佳路线。 对于问题三，送货员因为快件载重和体积的限制，至少需要三次才能将快件送达。所以需要对100件快件分区，即将50个配送点分成三组。利用距离矩阵寻找两两之间的最短距离是50个配送点中最大的三组最短距离的三个点，以此三点为基点按照准则划分配送点。 关键字：Floyd算法距离矩阵哈密尔顿圈二边逐次修正法矩阵翻转
问题重述 某公司现有一配送员，，从配送仓库出发，要将100件快件送到其负责的50个配送点。现在各配送点及仓库坐标已知，货物信息、配送员所承载重物的最大体积和重量、配送员行驶的平均速度已知。 问题一：配送员将前30号快件送到并返回，设计最佳的配送方案，使得路程最短。 问题二：该派送员从上午8：00开始配送，要求前30号快件在指定时间前送到，设计最佳的配送方案。 问题三：不考虑所有快件送达的时间限制，现将100件快件全部送到并返回。设计最佳的配送方案。配送员受快件重量和体积的限制，需中途返回取快件，不考虑休息时间。 符号说明 D：n个矩阵 n V：各个顶点的集合 E：各边的集合 e：每一条边 ij w:边的权 ()e G：加权无向图 , v v：定点 i j C：哈密尔顿圈 () f V：最佳哈密尔顿圈 i
送货路线设计问题的答案 1、问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。 现在送货员要将100件货物送到50个地点。请完成以下问题。 1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。 2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。
要求标出送货线路。 3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。 2、问题分析 送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计。 图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。 对于问题二要考虑到所到的点的时间的要求是否满足题意即采用多次分区域的假设模型从而找出最优的解 对于问题三则要考虑到体积和质量的双重影响，每次到达后找到达到最大的体积和质量的点然后返回，再依次分析各个步骤中可能存在的不合理因素达到模型的进一步合理优化得到最合理的解。 3、模型假设与符号说明
【最新整理，下载后即可编辑】 快递员配送路线优化模型 摘要 如今，随着网上购物的流行，快递物流行业在面临机遇的同时也需要不断迎接新的挑战。如何能够提高物流公司的配送效率并降低配送过程中的成本，已成为急需我们解决的一个问题。下面，本文将针对某公司的一名配送员在配送货物过程中遇到的三个问题进行讨论及解答。 对于问题一，由于快递员的平均速度及在各配送点停留的时间已知，故可将最短时间转换为最短路程。在此首先通过Floyd 求最短路的算法，利用Matlab程序将仓库点和所有配送点间两两的最短距离求解出来，将出发点与配送点结合起来构造完备加权图，由完备加权图确定初始H圈，列出该初始H圈加点序的距离矩阵，然后使用二边逐次修正法对矩阵进行翻转，可以求得近似最优解的距离矩阵，从而确定近似的最佳哈密尔顿圈，即最佳配送方案。 对于问题二，依旧可以将时间问题转化为距离问题。利用问题一中所建立的模型，加入一个新的时间限制条件，即可求解出满足条件的最佳路线。 对于问题三，送货员因为快件载重和体积的限制，至少需要三次才能将快件送达。所以需要对100件快件分区，即将50个配送点分成三组。利用距离矩阵寻找两两之间的最短距离是50个配送点中最大的三组最短距离的三个点，以此三点为基点按照准则划分配送点。
关键字：Floyd算法距离矩阵哈密尔顿圈二边逐次修正法矩阵翻转 问题重述 某公司现有一配送员，，从配送仓库出发，要将100件快件送到其负责的50个配送点。现在各配送点及仓库坐标已知，货物信息、配送员所承载重物的最大体积和重量、配送员行驶的平均速度已知。 问题一：配送员将前30号快件送到并返回，设计最佳的配送方案，使得路程最短。 问题二：该派送员从上午8：00开始配送，要求前30号快件在指定时间前送到，设计最佳的配送方案。 问题三：不考虑所有快件送达的时间限制，现将100件快件全部送到并返回。设计最佳的配送方案。配送员受快件重量和体积的限制，需中途返回取快件，不考虑休息时间。 符号说明 D：n个矩阵 n V：各个顶点的集合 E：各边的集合 e：每一条边 ij w:边的权 ()e G：加权无向图 , v v：定点 i j
配送路线优化
————————————————————————————————作者: ————————————————————————————————日期： ?
石河子大学毕业论文 题目:节约里程法在新疆国美电器物流配 送路线优化中的应用研究 院（系)：商学院商务管理系 年级：2008级 专业:物流管理 班级：物流2０08(1）班 学号:２008175477 姓名：张露露 指导教师:李霞 完成日期: 2０12年０3月１0日
目录 引言?错误!未定义书签。 1.物流配送概述?错误!未定义书签。 1．１物流配送的概念 ..................................................................... 错误!未定义书签。 1.2物流配送的功能3? 1.3物流配送路线优化的意义 (3) ２.新疆国美电器物流配送中心基本概况3? 2.１新疆国美电器简介 ................................................................................................. ３ 2.2新疆国美电器配送中心运作现状及现有路线分析 (4) ２．2．1现有配送路线概况........................................................................................ ５２.2.２现有配送路线中存在的问题分析 .. (6) 3.节约里程法在新疆国美电器物流配送路线优化中的应用研究?７ 3.1建立ＶRP模型7? 3．1．1物流配送模型 (7) 3．1．2节约里程法的基本理论 (7) 3．１.3新疆国美电器物流配送中心VRP模型的建立 (9) 3.2模型求解9? 3.３配送路线优化1?０ 3.４配送路线优化前后比较分析及思考 ............................................................... １6 ３.4．1优化前后比较分析1?６ 3．4.２节约里程法的思考 (16) 4．新疆国美电器物流配送中心配送路线优化对策分析18? 4.1完善物流配送体系，加强物流运作标准化18? 4．2构建物流信息系统平台,降低配送成本?１８ 4.３合理安排配送排程,减少不必要的配送路线 (18) 4.４优化配送资源,提高物流配送效率 ............................................................... 1９ 结束语2?０ 致谢21? 参考文献 (22)
物流配送最优路径规划
关于交通运输企业物流配送最优路径规划的 研究现状、存在问题及前景展望 摘要：本文综述了在交通运输企业的物流配送领域最优路径规划的主要研究成果、研究存在问题及研究方向。主要研究成果包括运用各种数学模型和算法在运输网中选取最短或最优路径；从而达到路径、时间最优和费用最优；以及物流配送网络优化、车辆系统化统一调度的发展。今后研究的主要方向包括绿色物流，运输系统及时性和准确性研究等。 关键词：物流配送；最优路径；路径规划 Overview of scheme on Shortest Logistics Distribution Route in Transportation Industry Student: Wan Lu Tutor: Chen Qingchun Abstract: This paper reviewed of the optimal path planning about the main research results, problems and direction in the field of transportation enterprise logistics distribution. Main research results include using various mathematical model and algorithm selection or optimal shortest path in the network. So we can achieve the optimal path, the shortest time and minimum cost. At the same time, logistics distribution network optimization, the vehicle systematic development of unified scheduling are the research issues.The main direction of future research include green logistics, transportation system accurately and timely research and so on. Key words: Logics Distribution; Optimal Path; Path Planning 引言 物流业在我国的新兴经济产业中占据了重要了地位，称为促进经济快速增长的“加速器”。而物流配送作为物流系统的重要环节，影响着物流的整个运作过程以及运输企业的发展趋势和前景。采用科学、合理的方法来进行物流配送路径的优化，是物流配送领域的重要研究内容。近年，国内外均有大量的企业机构、学者对物流配送中最优路径选择的问题，进行了大量深入的研究，从早期车辆路径问题研究，到根据约束模型及条件不断变化的车辆最优路径研究，以及随着计算机学科的发展而推出的针对物流配送路径最优化的模型和算法等方面，都取得丰硕的学术成果。但是对于绿色物流配送的研究仍然不足。鉴于物流配送最优路径研究的重大理论意义和实践价值，为对我国物流配送的效率水平有一个系统的理解和把握，有必要对现有成果进行统计和归纳。本文尝试对我国运输企业物流配送最优路径规划进行探讨，以期为今后做更深人和全面的研究提供一定的线索和分析思路。 1 国内外研究现状 1.1 国内研究现状 1.1.1 主要研究的问题
送货路线设计问题 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。 现在送货员要将100件货物送到50个地点。请完成以下问题。 1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。 2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。 3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。 以上各问尽可能给出模型与算法
送货路线设计模型 一.摘要 本文是关于快递公司送货路线设计问题，即在给定送货地点和给定设计规范的条件下，确定送货员的最短运行线路，即耗时最少的送货线路。本文为了能够全面的利用所有的数据，决定建立模型一：采用“D-J模型”。在此模型中，运用Dijkstra算法和Kruskal算法相结合求解,然后套用此模型可以得到最优的结果是：送货员所走过的总路程：56.27114573千米；送完全部货物所需时间：3.8446小时。 本文为了能够解决更通俗的套用模型，由此建立模型二：“分析&递推模型”。在此模型中利用分析法和递归的思路建立动态的方法求得最优化结果来相结合求解, 然后套用此模型可以得到最优的结果是：送货员所走过的总路程：60.04552405千米送完全部货物所需时间：4.001896835小时。 在问题一的基础上，加多的时间的限制，利用模型二，求出送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间的最快完成的结果是：送货员所走过的总路程59.2435千米送完全部货物所需时间：3.96848小时。 由于受重量和体积限制，为了有规律的进行计算，建立模型三：“分区送货策略模型”。通过对送货点的分成不同的区域，在对其继续单独的利用模型二计算，得到最优的结果为：
石河子大学毕业论文 题目：节约里程法在新疆国美电器物流配 送路线优化中的应用研究 院（系）：商学院商务管理系 年级： 2008级 专业：物流管理 班级：物流2008（1）班 学号： 姓名：张露露 指导教师：李霞 完成日期： 2012年03月10日 目录 引言 ................................................................................................................................... 1.物流配送概述 ................................................................................................................. 1.1物流配送的概念 ....................................................................................... 1.2物流配送的功能 (3) 1.3物流配送路线优化的意义 (3) 2.新疆国美电器物流配送中心基本概况 (3) 2.1新疆国美电器简介 (3) 2.2新疆国美电器配送中心运作现状及现有路线分析 (4) 2.2.1现有配送路线概况 (5)
2.2.2现有配送路线中存在的问题分析 (6) 3.节约里程法在新疆国美电器物流配送路线优化中的应用研究 (7) 3.1建立VRP模型 (7) 3.1.1物流配送模型 (7) 3.1.2节约里程法的基本理论 (7) 3.1.3新疆国美电器物流配送中心VRP模型的建立 (9) 3.2模型求解 (9) 3.3配送路线优化 (10) 3.4配送路线优化前后比较分析及思考 (16) 3.4.1优化前后比较分析 (16) 3.4.2节约里程法的思考 (16) 4.新疆国美电器物流配送中心配送路线优化对策分析 (18) 4.1完善物流配送体系，加强物流运作标准化 (18) 4.2构建物流信息系统平台，降低配送成本 (18) 4.3合理安排配送排程，减少不必要的配送路线 (18) 4.4优化配送资源，提高物流配送效率 (19) 结束语 (20) 致谢 (21) 参考文献 (22) 摘要 配送作为物流活动中直接与消费者相连的环节，在企业的物流成本中，配送成本占了相当高的比例。配送线路安排的合理与否对配送速度、成本、效益影响很大，特别是多用户配送线路的确定更为复杂。 正确合理地安排车辆的配送线路，实现合理的线路运输，可以有效地节约运输时间，
如何结合实际优化配送线路 编者按配送是行业现代物流建设中的一个关键环节，配送线路的合理制定对于实现商流、物流、信息流、资金流的有机统一，打造优质、高效、低成本的现代物流体系具有十分重要的作用。本版特选取部分烟草商业企业报道他们在优化配送线路方面的有效做法，供大家借鉴。 优化送货线路提升物流配送水平 浙江省杭州市烟草专卖局（分公司）配送中心来燕妮 浙江省杭州市烟草专卖局（分公司）按照“合理规划、统一标准、经济实用、综合配套”和“优质、高效、低成本”的要求，以物流标准化管理为重点，以注重效率为导向，优化送货线路，提升物流配送水平。 一、制定线路优化标准 2006年11月，杭州烟草制定了《卷烟物流配送标准化管理手册》，其中对线路优化标准作了相关规定： 1.合理设置接货点。全市县（区）局（公司）设立送货部，参照送货半径30~50公里，结合道路状况、零售客户分布情况、配送卷烟数量、车型等指标合理设立接货点。 2.确定送货里程、户数、数量、承担量。规定送货员实行每周5天工作制。城区主要集镇每日送货户数基本核定为70~90户，送货量为3000~5000条左右；地处城郊、城乡结合部区域，每日送货户数基本核定为50~70户，送货量为2000~3500条左右；山区、偏远农村的零售客户送货户数基本核定为35户左右，送货量为1200条左右，送货里程200公里左右。 3.明确送货模式标准。卷烟全部由配送中心“按订单组织货源”，并直接配送到各单位送货部，各送货部负责将卷烟送货到户，实行二段式送货方式；城区、集镇、近郊客户实行直接配送和过车式跨区域配送方式；对边远山区、农村零售客户采取直接配送、过车式配送、外聘式配送相结合的方式。 二、利用现代信息技术，实现送货线路最优化 杭州市局（分公司）配送中心的线路优化工作紧紧围绕高效、低成本的目标，突出城乡、县市一体化运作，以现代化实现高效率，以规模化实现低成本。目前，全市卷烟配送架构已初具规模。配送中心通过智能化车辆调度系统，对杭州本级的配送线路进行了优化调整。 1.智能化车辆调度。建立了车辆调度管理系统，来自业务系统的订单信息经过送货线路优化模块自动排单系统处理，在地理信息系统（GIS）的支持下，每日生成动态的送货指导线路和分拣配货策略，分拣配货策略由计算机网络发送到配货流水线，送货计划则打印成送货清单交给送货员，以确保卷烟安全、及时送达。 2.车辆运行监控。采用GPS车辆定位系统，对送货车辆进行实时监控。在送货途中，送货员可以结合当日路况，修正GIS指导线路，GPS卫星定位系统则对送货车辆进行全程监控，加强送货管理，提高应对突发事件的能力。同时，在合理优化线路的基础上，对配送线路进行动态管理，保证了每条送货线路的合理性和科学性。 3.货站到货管理。在车辆对接进行卷烟过车时，通过全球眼系统对整个卷烟交接过程进行全程监控，从而使整个送货流程更加安全、透明。 三、打破区域界限，完善送货服务 杭州市局（分公司）配送中心积极探索跨区域配送模式，不断完善送货服务，降低配送成本，提高配送效率。 1.打破市场和行政区划界限。从2005年下半年开始，杭州市局（分公司）配送中心逐步对余杭、临安、富阳、萧山、建德、桐庐、淳安进行了跨区域配送线路整合，目前已实现了杭州与余杭、建德与桐庐、淳安与建德、淳安与桐庐、临安与富阳、滨江与萧山之间的跨区域配送。特别是将原属于淳安县局（公司）茶园支线的24户零售客户划入建德配送分中心，送货里程从原来的57公里缩短到现在的15公里。 2006年，配送中心在原有基础上进行了大量调研后，认为原来的访销及送货线路存在送货线路重复、送货成本偏高和送货量不均等问题。针对薄弱环节和问题，配送中心总结全市跨区域配送经验，解决了市场部客户经理访销与送货线路不一致、客户订货量与送货员当天送货工作量差距较大的问题，不断推进跨区域配送工作，进一步降低了配送成本，提高了整体运行效率。
期末数学建模 报告（A）题 姓名：李飞专业：功能材料学号：120540214 姓名：谭秀松专业：自动化学号：120610317 2014-6-7
送货路线设计问题 摘要 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，针对一个送货员要去城市多处送货并返回，该图为一个网络图，如何设计线路使送货员所用时间最少。因为速度是恒定的，并且货物交换时间也相同，所以把求时间最短问题转化为求路径最短的问题，采用Floyd算法思想、借助矩阵、MATLAB软件和编程，求出最短距离矩阵和最短路径矩阵。再通过数据的分析、筛选和计算，从而可在图上标出送货员到各个点的最短路径，得到最优解。 针对问题一：采用“D-J模型”。在此模型中，运用Floyd算法求解,然后套用此模型可以得到最优的结果是：送货员所走过的总路程：54707.5米。 针对问题二：采用“分析&递推模型”。在此模型中利用分析法和递归的思路建立动态的方法求得最优化结果来相结合求解,然后套用此模型可以得到最优的结果是：送货员所走过的总路程：52004.37米送完全部货物所需时间：3小时37分01秒。 针对问题三：分区送货策略模型”。通过对送货点的分成不同的区域，在对其继续单独的利用模型二计算，得到最优的结果为： 关键词：分析&递推模型Floyd算法 Kruskal算法最短路径最小生成树法 一、问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方。所以在快递公司送货策略中，确定合理的行走路线是关键的问题。 问题（1）在送货员送货路线设计问题中，送货员从图1中的起点O出发，将1~30件货物送到指定目的地并返回，要求所用时间最短。此时送货员可将
2010年宝鸡文理学院数学建模竞赛 编号专用页 评阅编号（由组委会评阅前进行编号）： 指导教师信息（有指导教师的队填写）：
宝鸡文理学院大学生数学建模竞赛 承诺书 我们仔细阅读了宝鸡文理学院大学生数学建模竞赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 所属学校（请填写完整的全名）： 参赛队员(打印并签名) ：1. 2. 3. 日期： 2010 年 06 月 06 日评阅编号：
宝鸡文理学院数学建模竞赛 阅卷使用页 ●阅卷编号：（阅卷组填写） ●阅卷组长： ●阅卷表格：
最优送货路线设计问题 摘要 当今社会，网购已成为一种常见的消费方式.随着物流行业的兴盛，如何用最短的时间，最节约成本的方案，完成送货任务显得尤为重要.针对本案例，我们采用了大量的科学分析方法，并进行了多次反复验证，得出如下结果： 1：根据所给问题及有关数据，我们将题目中给出的城市，及其之间的线路可看成一个赋权连通简单无向图，采用了求这个图最小生成树的办法，求出最优线路.在此基础上，我们通过观察分析计算对上述结果进行修正，得出最终结果. 2：根据所给问题，我们发现当货物不能一次送完时，中途需返回取货，而返回路径当然越短越好，可通过求途中两点最短路径的方法求出. 关键字：送货线路优化，赋权连通简单无向图，Excel，最小生成树.
送货路线设计问题 1、问题重述 现今社会网络越来越普及,网购已成为一种常见的消费方式,随之物流行业也渐渐兴盛,每个送货员需要以最快的速度及时将货物送达,而且她们往往一人送多个地方,请设计方案使其耗时最少。 现有一快递公司,库房在图1中的O点,一送货员需将货物送至城市内多处,请设计送货方案,使所用时间最少。该地形图的示意图见图1,各点连通信息见表3,假定送货员只能沿这些连通线路行走,而不能走其它任何路线。各件货物的相关信息见表1,50个位置点的坐标见表2。 假定送货员最大载重50公斤,所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟,为简化起见,同一地点有多件货物也简单按照每件3分钟交接计算。 现在送货员要将100件货物送到50个地点。请完成以下问题。 1、若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。 2、假定该送货员从早上8点上班开始送货,要将1~30号货物的送达时间不能超过指定时间,请设计最快完成路线与方式。要求标出送货线路。 3、若不需要考虑所有货物送达时间限制(包括前30件货物),现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路,给出送完所有快件的时间。由于受重量与体积限制,送货员可中途返回取货。可不考虑中午休息时间。 2、问题分析 送货路线问题可以理解为:已知起点与终点的图的遍历问题的合理优化的路线设计。 图的遍历问题的指标:路程与到达的时间,货物的质量与体积,以及最大可以负载的质量与体积。在路线的安排问题中,考虑所走的路程的最短即为最合理的优化指标。 对于问题二要考虑到所到的点的时间的要求就是否满足题意即采用多次分区域的假设模型从而找出最优的解 对于问题三则要考虑到体积与质量的双重影响,每次到达后找到达到最大的体积与质量的点然后返回,再依次分析各个步骤中可能存在的不合理因素达到模型的进一步合理优化得到最合理的解。 3、模型假设与符号说明 3、1、模型的假设 (1)、到同一地点的货物要一次拿上,即不考虑再以后又经过时再带些货物 (2)、要求达到不超过的时间不包括此次在该点交易的时间。 (3)、所用的距离数据都精确到米而时间则精确到0、0001h (4)、同一地点有多件货物也简单按照每件3分钟交接计算。
摘要 从九十年代起，物流配送开始受到广泛的关注和蓬勃的发展，许多城市纷纷建立起配送中心。随着物流业的持续发展，城市配送业也日益受到重视。伴随着国内汽车工业的崛起，近年来国内汽车物流行业也经历了快速的发展。然而，在车市增幅逐渐放缓回稳之际，汽车物流供应商也面临着新的挑战。如何降低物流成本为企业提供更大的成本节约空间成为当务之急。 配送是企业物流当中的一个必不可缺的内容，它的效率直接影响了企业的经营；然而当今众多中小型企业在这一环节还处于一种较为单一和原始的操作模式之下，导致物流成本居高不下，从而阻碍了企业的进一步发展。本课题以重庆A公司为研究对象，通过对该公司配送业务的梳理、分析，同时利用物流配送管理研究成果，拟为该公司设计更加高效、科学的配送路线并构建以配送成本最小和顾客满意度最大为最终目标的车辆优化配送模型。对车辆路线进行优化不仅可以帮助决策者迅速做出科学正确的决定，提高配送效率和客户满意度。本文利用EXCEL、节约里程法以及最短路线法为物流配送车辆运行路线和调度问题的求解提供一个切实可行的算法，得到一个较优的解决方法，为企业减少由于配送所带来的大量成本，提高企业经营效率。因此，对路线选择问题的研究具有重要意义。 关键词：汽车配送物流配送物流成本
目录 摘要 (1) 第1章EZBUY公司简介 (1) （1）企业简介 (1) （2）公司发展现状 (1) 第2章现阶段配送过程中存在问题 (2) （1）现阶段配送过程流程图 (2) （2）配送订单需求有效性分析不够 (2) （3）配送线路混乱 (3) （4）司机群体管理松散及监管机制 (3) 第3章物流配送问题解决方案设计 (4) （1）循环取货及路线优化问题 (4) （2）物流运输节约法的运用来实现循环取货的线路优化问题 . 6 第四章配送方法的优化后的实例对比 (8) （1）节约里程法的问题及局限性 (8) （2）节约里程法的简化 (8) （3）.实例 (10) 参考文献 (13) 致谢 (15)
摘要 摘要本文讨论了送货员送货路线的优化设计问题, 即在给定送货地点和给定设计规范的条件下，综合考虑最大载重范围、最大带货体积以及各货物送货时限，确定业务员的最佳运行路线策略.并总结出一些在这类图中求解近似最优回路的有效法则. 对于问题1，采用了两种方法进行了计算，第一种是通过Floyd算法做出各顶点间的最短路径矩阵，然后选出1~30号货物所送达的顶点间的最短路径及距离，用二边逐次修正法求解Hamilton圈；第二种是通过蚁群算法获得多条近似优解，选取最佳线路. 对于第二问，则采用改进的遗传算法，求解有时间约束条件的TSP问题，根据线路规划问题的特点，基于遗传算法（GA）建立了一个适用于带有时间约束的送货路线规划模型.实验证明了此算法的有效性和可行性. 对于第三问，利用分割求解法和蚁群算法的合成算法，运用共同链分割全图，对每一个分图进行最优求解，由此得到全图的最优解。 关键词送货问题；优化路线；TSP模型；蚁群算法
送货路线设计的数学模型 1 问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少. 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少.该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线.各件货物的相关信息见表1，50个位置点的坐标见表2. 假定送货员最大载重50公斤，所带货物最大体积1立方米.送货员的平均速度为24公里/小时.假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算. 现在送货员要将100件货物送到50个地点.请完成以下问题. 1. 若将1~30号货物送到指定地点并返回.设计最快完成路线与方式.给出结果.要求标出送货线路. 2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式.要求标出送货线路. 3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回.设计最快完成路线与方式.要求标出送货线路，给出送完所有快件的时间.由于受重量和体积限制，送货员可中途返回取货.可不考虑中午休息时间.. 2 模型的假设与符号说明
装订线 第九届西安电子科技大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目 A (B)题 剪切线 通信工程学院第队
送货路线设计问题 1、问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。 现在送货员要将100件货物送到50个地点。请完成以下问题。 1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。 2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。 3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可
不考虑中午休息时间。 2、问题分析 送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计。 图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。 对于问题二要考虑到所到的点的时间的要求是否满足题意即采用多次分区域的假设模型从而找出最优的解 对于问题三则要考虑到体积和质量的双重影响，每次到达后找到达到最大的体积和质量的点然后返回，再依次分析各个步骤中可能存在的不合理因素达到模型的进一步合理优化得到最合理的解。 3、模型假设与符号说明 、模型的假设 （1）、到同一地点的货物要一次拿上，即不考虑再以后又经过时再带些货物（2）、要求达到不超过的时间不包括此次在该点交易的时间。 （3）、所用的距离数据都精确到米而时间则精确到 （4）、同一地点有多件货物也简单按照每件3分钟交接计算。 、符号说明