基于遗传算法的服装连锁业车辆调度问题研究

来源:用户上传      作者: 王志远　缪顾贤

　　[摘 要] 结合服装业流行性强，顾客对产品个性化明显等特点，本文建立车辆调度模型，修改传统的仅考虑成本因素的决策指标；注重考虑配送服务水平；最后应用遗传算法求解。
　　[关键词] 服装 连锁经营 车辆调度问题 遗传算法
　　
　　一、模型描述和建立
　　服装业行业特点为：潮流性强，配送服务要求高。中国连锁经营协会对国内连锁零售业调查显示: 缺货是该行业配送的重要症结。故本文考虑缺货成本，多品种问题和车辆时间价值建立车辆调度模型，允许对实际配送量决策。研究范围：单配送中心、单周期、非满载、多品种、多车型、允许对配送量决策、允许租车、带软时间窗的车辆调度问题。连锁总部配送中心为N个门店配送W种服装，自有车辆数为nk，能租到车辆数mk, k为车辆型号，车型总数为K，车辆编号为1；门店i对第w种服装需求量为giw, 对门店i实际决策配送量为riw ；决策变量xijk1为1表示k型号编号为l的车辆从点i行驶到j,否则用0表示；ti表示从点i出发时间，t0=0表示从配送中心出发时间，tij表示从点i到点j的行驶时间, si表示对门店i的服务时间。 dij表示从点i到点j的行驶距离；qk表示k型车容量，由于货物是服装，故这里选容积，忽略重量影响；cw表示每单位第w种货物占用的容积；Vk表示k型车单位距离行驶成本；φw表示第w种货物的单位配送量成本；Fk表示自有的k型车出车固定成本; Ek示租用的k型车出车固定成本；[ei,li]表示点i的时间窗，其中[e0,10]=[0，∞];ai表示对配送点i配送时提前到达的单位时间成本bi表示对配送点i配送时单位迟到时间成本；αk表示k型车单位行驶时间的成本；βw表示第w种货物每一单位的缺货成本；Ri表示是否对配送点进行服务，为1表示配送，否则为0；pk1表示k型，编号为1的车是否参加配送，为1表示参加，否则为0。模型表达式：
　　
　　二、遗传算法求解
　　据文献[1]采用基于客户的编码方式以适应不确定车辆数要求。 采用传统适应函数易造成适应度选择集中或分散，本文[2]中以目标函数值作为适应度，并配以随机联赛选择策略可以规避此问题。本文采取最佳保留策略结合随机联赛选择策略作为选择策略，采用常见的两点交叉和扩展的单点变异：区别在变异时按照初始化中重新对染色体赋值方法进行赋值。由于所得解均为只有车辆容量约束不满足的半可行解，故采用惩罚法调整适应值。算例如下：设配送点数为8，车辆类型为2，每型号3辆车，其中1型3号，2型3号为可租车辆，货种为2，1型车容量为15，2型车容量为20。总目标中各成本系数为：出车固定成本系数，自有车辆为{100，120}，租用车辆为{180，200}；距离成本系数为{0.5，0.7}；时间成本系数为{10，15}；配送量成本系数为{2，4}；早到惩罚成本系数为{40，30，25，20，30，35，10，20}；迟到惩罚成本系数为{100，120，160，130，100，95，120，140}；缺货成本系数为{80，100}；超载惩罚系数为4000。将文献中数据进行调整加入如下配送点的品种需求：
　　由实验得本问题取种群规模100，交叉率为0.8，变异率为0.15,迭代500代为宜。进行独立实验50次得满意解：目标函数值为1039，对应的配送方案为出车3辆，1型1号车配送路线0～8～2～7～0，1型2号车配送路线0～6～4～0，2型2号车配送路线0～3～1～5～0。
　　参考文献:
　　[1]邹 彤:不确定车辆数有时间窗车辆路径问题的遗传算法[J].系统工程理论与实践，2004.6(6):134～138
　　[2]占书芳:并行遗传算法在带软时间窗车辆路径问题中的研究[D].武汉理工大学，2005

转载注明来源:https://www.xzbu.com/3/view-1489798.htm