多物流配送中心路径优化问题及其遗传算法

《多物流配送中心路径优化问题及其遗传算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、多物流配送中心路径优化问题及其遗传算法廖成林柳茂森(重庆大学经济与工商管理学院，重庆，400030)牙商要：论文建立了多物流配送中心路径优化问题的数学模型，并针对该问题的特点构造出求解该问题的遗传算法，把多物流配送中心路径优化问题综合起来用一个数学模型求解。本文提出了无效基因的概念，从而不局限于使得个体屮每个基因都必须表达出来,因此增强了编码的灵活性。仿真实验证明了该方法的有效性和可操作性。关键词：无效基因遗传算法物流配送1引言物流配送是物流管理中一个极其重要的环节，它是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货人的活动。物流配送主要研宄车辆调度及路径安排问题。

2、近年来，国内外学者对物流配送问题进行了大量的研宄，这些研宄主要集中在单物流配送中心的.午.辆调度及路径安排方面。由于配送路径优化问题是一个NP难题，因此，研宄者大都使用启发式算法和智能算法或者是在智能算法优化过程屮加入优化策略以构造混合智能算法来求解物流配送问题。但是，目前国内外对多个物流配送中心的物流配送问题的研宄成果很少，而且现有研宄成果大都是把多个配送中心问题通过任务分派转化为单物流配送屮心问题来研究使用这种方法把需求点预先划分给各个配送屮心，在求解过程屮再作适当的调整，这种方法其实只是单物流配送屮心优化的简单组合，通常只能求得近似最优配送方案。魏百鑫等［4］针对整车配送需求点分散特征

3、,解决了多仓库的整车配送问题，但并不是一个通用的解决多物流中心配送问题的方法。由于遗传算法具有良好的全局寻优性能，并且对不要求搜索空间具是连续的，这正符合该问题的特点和要求。因此本文亦采用遗传算法求解。本文基于整体路径最优由多个物流配送屮心同时服务多个需求点建立一个通用的多物流配送中心的配送模型，并给出求解算法。单物流配送中心路径优化问题可以事先确定需要派出的车次，但是多物流配送中心路径优化问题中，每个配送中心需要派出多少车次是不确定的，因此，无法用常规的方法确定染色体的讼度。为解决基因编码的问题,本文提出了无效基因的概念。所谓无效基因就是在一次基因表达的过程中不作表达的基因。但是，在交叉过

4、程屮无效基因处可以被选为交叉点，交叉后无效棊因可能转化为有效基因。因此，有些基因时而是有效基因时而是无效基因，因而无效基因在不清楚有些基因是否表达较好的时候起到缓冲作用。2模型的建立多物流配送路径优化问题可描述为：从多个配送屮心用多辆配送车向多个需求点送货，每个需求点的位置和需求量一定，要求安排合理的配送路线，使得目标函数最优或接近最优。为了研宄的方便且具有实际意义，做以下假设：(1)每条配送路径上各需求点的需求量之和不超过配送车的载重量；(2)每个需求点都必须满足，II只能由一辆配送车送货。本文的各种符号及其含义做如下说明：M配送中心的个数1配送中心的下标j配送车辆的卜标k需求点的下标N需

5、求点的个数Li……第i个配送中心的配送车的个数Qij第i个配送中心的第j辆车的载重量qk第k个需求点的需求量dk⑴dk(2)-----从需求点k⑴到k(2)的运距d()k……配送中心到需求点k的运距nij……第i个配送中心的第j辆车配送的需求点个数，njj=O表示未使用第j辆车Rij……第i个配送中心的第j辆车配送的路径njk——第i个配送屮心的第j辆车配送的第k个需求点，rii()表示配送屮心2=min込，z=l,2,…，=1，2，.，LZ.Nk=l其中，［i表示不大于括号内数字的最大整数若以配送路径最短为R标函数，则可以建立如下配送路径的优化模型：MLfk=lminZ=EE/=17=1n

6、ijqrijk-⑵k=l010其他上述模型中：(1)式为目标函数；(2)式保证每条路径上各客户的货物需求量之和不超过配送车辆的载重量;(3)式表明每条路径上的客户数不超过总客户数;(4)式表明每个客户都得到配送服务;(5)式表示每条路径的客户的组成;(6)式限制每个客户仅能由一台配送车辆送货;(7)式表示当第i个配送中心的第j辆车服务的客户数＞1时，说明该台车参加了配送，则取f(nij)=1，当第i个配送中心的第j辆车服务的客户数＜1时，表示未使用该台车辆，因此取f(nij)=0。3遗传算

7、法设计3.1编码方法的确定和初始种群的产生根据多物流配送中心路径优化问题的特点，作者提出了一种配送中心和需求点直接排列的编码方法。这种表示方法是直接生产N个1〜N间的互不重复的自然数给这N个需求点编码，再生产M个-M〜-1之间的互不重复的负整数给这M个配送中心编码。把这M个-M〜-1之间的互不重复的负整数各n个和这N个1〜N间的互不重复的自然数各一个组成一个长度为MM+N的数列，数列的第一个位置随机排上一个负