安吉物流配送网点的选址和路线优化

安吉物流配送网点的选址和路线优化班级：学号：指导教师#/12表2各节点间节约里程(:12(:[1g17[)K122023F121S1&25F（；1214122126（；H51斗1923根据表2对上述中节约的里程进展从大到小进展排列，确定出最初的配送路线方案。再进展回路合并，并且要严格按照实际限制条件进展合并，不如货车的在中极限不能超载，货车最远运输距离不能超过等等现实意义的约束条件。逐层进展优化直至找到最优路线为止。这样就能很好的解决配送问题，安吉物流公司在进展配送网点的选址和配送路线的优化之后，使得服务水平不变的情况下公司的物流本钱有了很大的降低，反响速度得到很高的提升等。（二〕遗传算法所谓遗传算法是指：一类借鉴生物界的进化规律〔适者生存，优胜劣汰遗传机制〕演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进展操作，不存在求导和函数连续性的限定；具有在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规那么。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法的假定条件：〔5〕由底层供给商对客户进展配送2主要为零售性配送活动客户所订购的商品为一些高附加值的商品〔如汽车、电脑等忽略交货时的时间间隔一次出行可以解决服务于多个客户的配送问题基于以上假定，车辆为了满足费用最小化的目标就要寻找一条能历尽所有目标客户且每个客户仅访问一次，最后返回出发地的行驶路线，也就是寻求一条最短路径〔费用〕，这种配送问题是一个典型组合优化问题。1、问题的描述设有n个客户的集合user=（cl,c2,c3,…..，⑶）对于客户Ci,Cj属于user,从Ci到Cj的距离记为Dij属于R,假设Dij=Dji，该问题的解就是在集合user中找一个不重复的全排列C1i,C12,--.Cin使其距离E,当Cin+1=Ci1时，最短。2、遗传算法的设计1.编码方式由于在求解该问题时,个体表示的是一个可行解,即一条回路,因此它是城市序号的一组排列,所以传统的二进制编码方式与其根底上的遗传操作不适用于求解该问题的遗传算法。遗传算法中常用的编码方式有顺序表示法、路径表示法与矩阵表示法等。其中,顺序表示法是指将所有城市依次排列构成一个顺序表,在这个顺序表的根底上按照某条路径中城市的排列顺序后的个体编码。这种编码最大的问题在于不够直观,编码和解码算法较为复杂,容易出错,而矩阵表示法是用一个矩阵来表示一条路径,存在着存储消耗大的问题,于是本文采用路径表示法。路径表示法是表示路径对应的基因编码中最自然、最简单的表示方法,是一类整数编码方式,特别适合与表示本文具体问题中的个体。将染色体定义为一条解路线中的客户号序列，我们定义S*T大小的pop矩阵来表示群体，求16个客户的问题,T取17,矩阵每前16个客户的问题，T取17，矩阵每行前16个元素表示经过的客户编号，最后一个表示经过这些客户要走的距离。。设有n个客户C1,C2,C3・・・.，Cn,假定都是从起始配送中心出发，最后回到该配送中心，那么任意一条染色体可用公式〔1〕数串表示，其中，Ni=1,2,3,…，n。染色体中的单元称为节点1234567...N〔1〕在该问题求解中，染色体的适应值为：其中从Ci到Cj的距离记为那么从群体中选择优胜个体、淘汰劣质个体，它建立在群体中个体适应度评估的根底上，采用最优保存策略的方法。2.交叉算子设计传统的遗传算子不太适用于求解该问题，这是因为按问题要求，一条路径中必定经过且只经过每个客户一次，即个体编码串中每个客户序号都将出现且只出现1次，而基于二进制编码的单点和多点交叉算子极有可能造成城市序号重复或缺失而形成非法个体。解决这类问题通常有两种方法，一种为对已经产生的非法个体进展罚函数调整，但这种做法额外开销很大，另一种方法是设计专门的复合具体问题要求的交叉算子。遗传算法中常用的交叉算子有顺序交叉、循环交叉和边重组等，这些算子多具有可行性和有效性。本文根据具体问题的特征从易操作和实现角度设计一种新的交叉算组，对类顺序交叉进展简化。设母体中一个个体Ai为随即产生两个交叉位,设为i和i+j那么基因片段成为待交叉基因段，记为，考察待交叉基因片段中的各基因在另一个父体A2中的排列顺序，将A2个体所有满足K不属于〔I,i+j〕的基因删除Ak删除，那么得到基因段排列,将替换Ai中的得到新的个体A1,那么个体A1为父个体A1的子代个体。由于新生成的个体局部来自于父代个体，因此子代个体与从代个体间具有相似性，可将这种相似性模版看成为一个模式，于是高适应值的个体所具有的优良模式能够以高概率遗传到下一代并以指数增长，保持了算法的搜索速度。同时，交叉位置是基于均匀分布的随机取值，即待交叉基因段的长度是随机的，因此能够降低破坏优良模式的概率，同时保持了种群的多样性，使算法不易收敛于局部最优解。四、总结这里为了降低物流运输本钱，采用了节约里程法和遗传算法对配送中心的路线进展了优化。这样安吉物流在进展了配送中心的选址，运输路线的优化后，不但公司的物流本钱降低了，同时物流公司的快速响应也有了很大的提高。当然对于配送中心的选址不仅仅是上述的两种还有很多种方法比如综合因素分析法，类比法等。运输路线的优化也有其他的方法比如：蚁群算法、图解法等等。这里