【《物流配送问题建模与算法分析案例》5100字】

物流配送问题建模与算法分析案例目录TOC\o"1-3"\h\u22464第一章物流配送问题建模与算法 247641.1配送优化模型建立 2324481.1.1问题描述 2148081.1.2低碳成本计算 2186791.1.3符号说明 3239571.1.4模型构建 441561.2蚁群算法分析 5172721.2.1蚁群算法 5128311.3改进算法优化 8202971.3.1转移概率改进 8301721.3.2蚁群算法参数设置 970721.4本章小结 1025295第二章优化结果分析 1153782.1配送路径优化结果分析 1150142.1.1优化前配送情况 1148622.1.2优化后配送情况 13131312.2优化结果评价 15物流配送问题建模与算法配送优化模型建立问题描述本文主要研究对象是某物流公司的配送路径问题，以车辆从T配送中心出发将货物运往南北两个二级配送中心和各网点这一过程为研究对象，在满足客户要求的前提下，建立的模型，求解出合理的配送路径，使得总配送成本最小。现对本文研究的问题做出以下界定:本文研究的主要内容为该物流公司的总配送中心T分别往位于南北部的两个二级配送中心和配送中心周边县镇网点运输货物的过程，因此，本路径优化问题只有一个总配送中心，为单配送中心问题。该物流公司的实际经营内容为接收由各地发往山西省内的货物，在太原进行分拣后再配送至山西其他县市客户点，同时从网点回收取货。因此本文研究的问题是同时取送货问题。（3）本文以综合成本最低为总目标函数，并考虑碳排放、时间窗和同时取送货等情况下配送路径的选择问题，将成本分为以下四类：车辆的固定成本、运输成本、碳排放成本和时间成本。基于以上内容，做出以下模型假设：假设1：货物有前向物流和逆向物流，该公司有取送货服务。假设2：每个网点具有确定的位置、时间窗需求假设3：每个客户的服务由且仅由一辆车一次完成假设4：配送车辆的车型统一，即车辆规格、单位油耗、最大载重量、最大行驶距离均相同且已知。假设5：配送中心只有一个，每辆车从配送中心出发，完成任务后，返回起点。假设6：在各网点规定的时间窗外到达都会产生一定的成本。低碳成本计算负载估计法应用更加广泛，也更贴合实际。除此之外本文研究的是同时取送货模型，车辆载重量非线性关系。该模型假设燃油消耗量与车辆载重呈线性关系。车辆空载时。燃油消耗量为ρ0，车辆满载时，燃油消耗量为ρρ=Q为车辆满载时的载重量，q为当前载重量。若点与点之间的距离为d时，那么，从点i出发到点j的燃油消耗量为ρ=符号说明为简便描述和构建模型，将引入以下符号参数：N={i｜i=1,2,…,n}：配送网点组成的集合；K={k｜k=1,2,…,m}：配送车辆数；Q：配送车辆的最大载重量；yijzijg0pijqijD：每配送车辆最大行驶距离；dijtij：配送车辆在两个网点之间行驶所需时间，与网点之间的距离dtisijETiLTiETic0c1α：车辆到达时间早于网点开始服务时间的惩罚指数；β：车辆到达时间晚于网点结束服务时间的惩罚指数；γ：单位碳排放价格；φ：单位燃油碳排放系数；ε(X):单位距离燃油消耗量；ε0εM定义决策变量：x模型构建根据问题描述，建立一个考虑低碳的总配送成本最小模型。其目标函数为： MinZ=C0s.t. i=0nk=1 j=0nk=1 i=0nx j=0nx i=0nx j=1nx i=0ny i=0nz yij+ i=0nj=0 sik+ ETi≤ ε=ε0 xijk∈式（4-1）为目标函数，表示综合成本最小，其中综合成本由车辆固定成本和行驶成本、时间惩罚成本和油耗/碳排放成本四项成本构成；式（4-2）和（4-3）表示每个网点仅由一辆车一次完成任务；式（4-4）和式（4-5）表示每辆车都是从配送中心出发，完成任务后必须回到配送中心，是封闭的车辆路径问题；式（4-6）表示到达和离开同一网点的车辆相同；式（4-7）表示车辆数约束；式（4-8）和（4-9）表示网点的取货量和送货量；式（4-10）表示每条路径网点间的容量约束；式（4-11）表示所有车辆行驶距离均不能超过车辆的最大行驶距离；式（4-12）表示车辆在离开网点i前往网点j的过程中，在sik+t蚁群算法分析蚁群算法蚁群算法是由学者M.Dorigo，V.Maniezzo和A.Colorni等人在二十世纪九十年代初期模拟自然界蚁群寻找路径行为提出的一种随机搜索算法。蚂蚁在寻找食物时会释放出一种信息素，随着时间推移这种信息素会挥发，之后寻找食物的蚂蚁选择走这条路径的概率与这条路径上的信息素浓度成正比。求解时，蚁群算法在随机搜索得到的解上留下信息，迭代过程中根据解的信息浓度选择较优路径，不断收敛得到最优解。如果蚂蚁从A点出发，速度相同为单位1，食物在D点，它可能随机选择路径A-B-D或A-C-D。若初始时每条路线分配一只蚂蚁。图4-1为经过6个时间后的情况：走A-B-D的蚂蚁走过B点，刚好为一半路程，而走A-C-D的蚂蚁正好到达终点。图4-16个时间单位时的情况图4-2表示从出发时算起，经过12个单位的情况：走路线A-B-D的蚂蚁刚好走到终点，而走A-C-D的蚂蚁到达D点后又返回A点。图4-212个时间单位时的情况假设蚂蚁走过一处留下1单位信息，则经过24个时间单位后，同时出发的所有蚂蚁都获得了食物，但走路线A-B-D的蚂蚁只往返了一趟，每一处的信息素为2个单位；走A-C-D的蚂蚁往返了两趟，每处信息素为4个单位，信息素比值为1:2。按信息素浓度分配蚂蚁，则A-B-D为一只蚂蚁，A-C-D为两只蚂蚁，再次经过24个时间单位后A-B-D和A-C-D上的信息素比为1：3。继续按照信息素分配蚂蚁，则最终所有蚂蚁都选择路线A-C-D。基本蚁群算法的步骤如下：参数初始化；蚂蚁的禁忌表索引号k=1。将m个蚂蚁放到n个城市。蚂蚁根据概率元素j并前进。更新禁忌表指针，将蚂蚁移动至新的元素，将该元素移动至该蚂蚁禁忌表中如果禁忌表中不包含所有元素，则跳转到（4），否则执行（8）。记录本次最优路径更新信息量满足结束条件则结束循环，输出程序结果，否则清空禁忌表并跳转至（2）。蚁群算法的流程如图4-3。图4-3蚁群算法运算流程改进算法优化转移概率改进基本蚁群算法中，蚂蚁个体按照路径上剩余信息量和启发式信息，独立选择下一元素。t时刻，PijP本文研究问题中，企业车辆具有载重约束，保证车辆满载率有利控制成本。因此在选择概率时加入满载率这一值，除此之外加入每个网点送货量和取货量的影响，改进之后，转移概率如下：P公式中Jki=1，2，⋯，n-tabuk为蚂蚁k未走过的城市集合；tabuk为禁忌表，记录蚂蚁k已经选择的城市，禁忌表中有n城市时表示蚂蚁走过了所有城市，蚂蚁k走过的路径可以看作一个可行解；ηij是一个启发式因子通常取城市i与城市j之间距离的倒数，表示蚂蚁k从城市i转移到城市j的期望值；蚁群算法参数设置信息素启发式因子信息素启发式因子α表示信息量对选择当前路径的影响，α的值与选择当前路径的概率成正比，值越大，搜索随机性越弱；α过小容易使蚁群算法过早陷入局部最解。信息素启发式因子取值范围一般在[1,2]求解性能较好，本文设置α=1.5。期望启发因子β期望启发式因子根据搜索过程中路径上的信息素指导蚂蚁选择路径。与α不同的是，β越大越容易陷入局部最优解。根据经验，期望启发因子一般选择[3,5],本文设置为5。信息素挥发系数ρ信息素挥发系数反映信息素挥发快慢。ρ的选择将影响到算法的全局搜索能力和收敛速度。ρ越小，算法的随机性和全局搜索能力越差；ρ越大会降低收敛速度。本文中ρ=0.6。蚂蚁数量m蚁群算法是一种随机搜索算法，是通过多个可行解组成的集合进行优化找到最优解，这个过程不仅需要个体的自适应能力，还需要群体的协作能力。蚂蚁数量多可以提高算法的全局搜索能力但收敛速度变慢；蚂蚁数量过少，但问题规模较大时，搜索的随机性减弱。m一般取10-50，本文选择m=50。信息素强度Q信息量Q表示蚂蚁周游一周时在路径上释放的信息素总量。在ant-cycle模型中，Q对蚁群算法的性能没有明显影响。故此，Q可随意选取，本文设Q=100为参数。本章小结本章根据该物流公司实际情况，构建了以综合成本最小为目标的模型，选择蚁群算法为本文的研究方法，之后设置了蚁群算法相关参数。优化结果分析配送路径优化结果分析优化前配送情况该物流公司制定配送方案时由T配送中心出发，一辆货车负责几个网点的配送服务，具体配送路径多按照司机个人经验。优化前具体配送路径如下表5.1所示。表5.1原配送方案路径配送顺序行驶距离送货量取货量11-24-25-15-16-2-4-5-8-6-7-20-1988.773233421-30-19-29-27-3-26-22-21-1987.546231231-18-9-10-14-12-13-11-1866.237817341-18-9-10-14-12-13-11-1750.217750路径1客户点124251516245867201到达载重/kg732732677606568538522475427398406374334离开载重/kg7326776065685385224754273984063743340到达时间/h00.88251.266253.113.76754.2855.356.4710.5210.70511.4762512.1637513.45875离开时间/h00.98251.366253.213.86754.3855.456.5710.6210.80511.5762512.2637513.45875行驶距离/km070.622.7139.544.633.477.281.63166.853.74795.6表5.2原配送方案具体信息路径2客户点13019292732622211到达载重/kg462462474407386441389337335312离开载重/kg4624744073864413893373353120到达时间/h01.12751.716252.703753.811254.615.6556.75257.8162513.14375离开时间/h01.22751.816252.803753.911254.715.7556.85257.9162513.14375行驶距离/km090.239.17180.655.975.679.877.1418.2路径3客户点118910141213111到达载重/kg378378320345334248202192173离开载重/kg3783203453342482021921730到达时间/h01.711252.21252.854.2254.888755.503758.3037511.5275离开时间/h01.811252.31252.954.3254.988755.603758.4037511.5275行驶距离/km0136.932.14310245.141.2216249.9路径4客户点12823171到达载重/kg1771771238350离开载重/k达时间/h02.465.7957.178759.6775离开时间/h02.565.8957.278759.6775行驶距离/km0196.8258.8102.7191.9综上车辆行驶距离为3592.6km优化后的成本为800+17307+55.60+73.74=18236.34元配送车辆为4辆优化后配送情况运用MATLAB软件使用改进后蚁群算法求解数学模型，将网点距离以及网点需求等导入程序后，运行程序，优化结果如下表表5.3优化结果路径配送顺序行驶距离送货量取货量11-7-8-6-20-28-1645.731316621-25-24-23-17-15-16-2-4-5-1979.559621831-30-29-27-3-26-21-22-1938.137729441-18-9-10-14-12-13-11-19-1867.4463191图5-1蚁群算法迭代图图5-2优化后配送路径示意图表5.4优化后配送信息路径1客户点178620281到达载重/kg313313281252260220166离开载重/kg3132812522602201660到达时间/h01.09251.656251.841252.518756.011258.57125离开时间/h01.19251.756251.941252.618756.111258.57125行驶距离/km087.437.16.846.2271.4196.8路径2客户点12524231715162451到达载重/kg596596525470430397359329313266218离开载重/kg5965254704303973593293132662180到达时间/h00.728751.11254.013755.39756.36257.027.53758.60259.722513.14375离开时间/h00.828751.21254.113755.49756.46257.127.63758.70259.822513.14375行驶距离/km058.322.7224.1102.769.244.633.477.281.6265.7路径3客户点130292732621221到达载重/kg377377389368423371319296294离开载重/kg3773893684233713192962940到达时间/h01.12752.228753.336254.1355.186.368757.432512.42625离开时间/h01.22752.328753.436254.2355.286.468757.