第二章 送货优化方案设计.ppt

1.旅行商问题背景 旅行商问题又被称为TSP问题，它的实质就是考察从某个物理节点出发，经过其他节点，最后再返回到出发点，这其中所经历的最短路径方案的问题。 2、泉州某快递公司背景 泉州某快递公司的快递需要每天派送大量快件，环绕大泉州各个区、县市等主要区域以及一些乡镇区。 四、数学模型 1.符号说明 2.模型建立 根据上述的符号定义，建立方案优化模型如下： 目标函数： 式（1）表示巡回的总距离最小。 约束条件： 式（2）表示路径连续性约束。 式（3）表示一条送货路线从公司总部出发，并返回 公司总部。 式（4）表示0-1决策变量。 注解： 其中，xi和yi为节点i的横、纵坐标 。 五、计算方法设计 步骤： （1）让网络节点随机排序m次； （2）计算m次排序的赋权距离； （3）取其中最小距离，若得满意解，算法结 束，否则转步骤（4）； （4）重复步骤（1）~（3），直至得满意解，算法结束。 根据设计的算法，采用MATLAB M语言编写程序如下： clear all; Tic PX=[]; … DX=[FX,PX]; DY=[FY,PY]; p=length(PX); f=length(FX); Dis=zeros(length(DX)); for v=1:length(DX) for vv=1:length(DX) Dis(v,vv)=round(sqrt((DX(v)-DX(vv))^2+(DY(v)-DY(vv))^2)); end end vrp0=zeros(2000*p,p); for i=1:2000*p vrpz=randperm(p); … … for v2=1:p+1 d1=vrp(v1,v2); d2=vrp(v1,v2+1); hD1(v1,v2)=Dis(d1,d2); end end zvrp0=sum(hD1,2); dm0=find(zvrp0(:,:)==min(zvrp0)); dm0p1=vrp0(dm0,:) [rj1,rj2]=size(dm0p1); for j=1:rj1 … … figure(j) x1=PX; y1=PY; plot(x1,y1,ko,markersize,5); grid on hold on x2=FX; y2=FY; plot(x2,y2,ks,markersize,11); grid on hold on … … xx=[x1(pkf(p+1)),x2]; yy=[y1(pkf(p+1)),y2]; plot(xx,yy,:r,LineWidth,1.2); grid on hold on end Z=min(zvrp0) toc t=toc 六、算例仿真与实际应用 1.数据分析 随机选取10个选取快递网点，其平面坐标是0到300的二维随机数，距离单位为km，有关数据由下表2.2给出，相对位置下如图2-1所示。 表2-2 节点坐标 图2-1 节点相对位置 2.计算结果分析 根据上述模型、计算方法和有关数据，得出最短的行驶路线距离为701km、程序运行时间为32.7s；其快递路线方案网络图如下2-2所示，路线方案： 0-9-10-6-7-1-2-4-8-5-3-0 。 七、评述 1.构建模型可以给泉州快递公司各个网点间路径优化方案设计提供决策支持。设计的计算方法能获取一个合适的的解，并具有较高运算效率。 2.在泉州市快递公司的运送过程中，应尽可能做到成本最低，时间最短。 3.据此设计送货路线方案，可以在满足一定的社会效益（如按时送达）和获得最大经济效益（如较少的人力物力、较短的时间）的前提下，可以给出较理想的送货方案与路线。 4.快递网点的坐标是随机给出的，与实际位置会有偏离。（实际中，可以通过调查和资料查询获得真实的数据） * 物流单回路运输问题 ——泉州市某快递公司节点运输路径分析 第二章 送货路线方案设计 一、问题提出（问题描述） 物流行业中，送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方。这就需要计算出合理的路径进行运输。 泉州市某通快递公司每天需要向泉州市内各个