遗传算法在物流配送中心选址.docx

遗传算法在物流配送中心选址
和车辆调度问题中的应用

物流是一个非常具有实际意义的问题，很长一段时间都是诸多学者研究的热点。对于物流中的诸多问题，特别配送中心选址和车辆调度问题，他们应用各种优化方法对其进行规划，做了多方面的研究。配送中心选址和车辆调度问题对一个企业来说是至关重要的，解决此问题主要包括有：启发式算法，虽然它规则简单，计算速度也很快，但它的不足在于解决问题的准确性较差，因此，它通常用于那些对于计算精度要求不高的方案；混合整数规划方法，它具有较好的收敛性和准确性。但由于这种算法在配置模型中存在太多的假设条件，以至于限制了它的应用范围；遗传算法，它具有整体优化的能力，同时适合于许多不同的模型，因此它是一种合适的选择。
本文就是运用遗传算法将选址和车辆调度两个方面的问题综合在一起讨论，在只知道需求点分布的时候，综合考虑各类费用以及配送便捷的基础上建立物流配送中心选址模型，用标准遗传算法对该模型求解，问题即可得到有效的解决，找出配送中心的最佳位置。然后再根据已确定的配送中心和需求点位置来制定车辆路径。在解决车辆优化调度问题时，本文综合考虑了各种成本费用，建立了适合物流配送模糊车辆调度问题的数学模型，同时采用期望值选择法，将爬山法与遗传算法相结合，从而构成混合遗传算法，使解决该问题快速地搜索到满意的结果。结合以上两种模型，同时解决这两方面的问题，使其更加具有完整性和适用性。
1物流配送中心选址和车辆调度问题阐述
物流配送中心选址主要因素及费用与物流配送[1，2]基本相同，主要包括：车辆费用，驾驶员工资（正常工作时间）和补助（加班费），车辆等待费用（提前到达客户，车辆需要等待），但对于选址，需要考虑配送中心建设费用和货物的存放费用。
限制条件：
1）所有路径均起始于配送中心，并要求返回配送中心；
2）每一个客户只由一辆车送货；
3）每个客户都有一个非负的货物需求量，并且经过该客户的配送路径货物总需求量不能大于配送车的载货量；
问题假设主要如下：
配送中心建设费用为W，坐标为，客户总数为，其坐标为…,，第个客户需求量为，卸货时间为，配送中心和客户的预约时间为，配送中心与客户或者客户与客户之间的最短距离为…,)，车辆的平均车速度为…,），每公里车辆的费用的为…,)，车辆种类为m，第p类卡车车辆数为，载货量为，车辆等待费用每小时为r，正常工作时间时司机的工资为每小时，加班时间时的补助为每小时，车辆需要返回配送中心，表示车辆总费用，另
，
2标准遗传算法解决配送中心选址问题
标准遗传算法的基本思想和基本步骤在上文中已经详细的论述，但在实际问题中，其具体操作却有着不同的地方，对于选址问题，主要方法和步骤[3-5]如下：
第一步：选址数学模型
根据题目我们有：
车辆行驶的费用为：（3.1）
驾驶员的费用（工资和补助）为：（3.2）
由此建立物流配送中心选址问题的数学模型：
（3.3）
（配送中心选址考虑的费用）
s.t.保证任一客户i只由一辆车来送货（3.4）
保证任一车辆送货量不大于载货量（3.5）
优化目标：找出配送中心选址所需费用最小时的

第二步：编码方案
若需要选定m个配送中心，则染色体需要由2m个浮点数排列组成：……,，其中表示第i个配送中心的地址坐标，一个染色体所包含的m个地址就是配送中心的选址的一个方案。如，对于本文，只需要一个配送中心，则染色体为。

第三步：初始种群
在配送区域随机产生一系列地址点，构成N个个体，构成初始种群，…,(其中……,),并作为遗传迭代的第一代。

第四步：适应度函数
遗传算法的一个特点是它可以使用所求问题的目标函数值即可得到下一步的有关收集信息，而对目标函数值的使用是通过评价个体的适应度来体现的。适应度是群体中个体生存机会选择的唯一确定性指标，所以适应度函数的形式直接决定了群体的进化行为。为了直接将适应函数与群体中的个体优劣质量相联系，在遗传算法中适应度规定为非负，并且在任何情况下总是越大越好。配送中心选址模型问题所建立的目标函数式（3）是求最小值，则适应度函数可采用2.4式，定义如下：
，（3.6）
可以取当前出现过的最大值。

第五步：选择算子
对于浮点数编码，我们宜根据个体的适应度大小从大到小排列个体，重排后的个体适应度最高，性能最优。根据排序决定每个个体复制到下一代的概率，用轮盘赌法复制L个个体，进入下一代，代数增加1。

第六步：交叉算子
采用与二进制相似的单点交叉。在二进制单点交叉中，只需要将交叉点对应的元素进行交换，浮点数编码的单点交叉与此相同。如
父代个体，
父代个体
交叉点为3，则交叉过后，子代个体为

。
在设定交叉概率后，从群体中随机选出个个体进行两两交叉，从而得出新的个体。

第七步：变异算子
变异操作以概率对染色体群中的某些染色体的某些位进行变异，产生新的个体染