基于遗传算法的物流配送车辆调度问题研究.pdfVIP

第 34 卷第 6 期 数学的实践与认识 V o l34　N o 6　 2004 年 6 月 M A TH EM A T IC S IN PRA CT ICE AN D TH EO R Y J un e, 2004　 基于遗传算法的物流配送车辆调度问题研究 1 2 1 1 龚延成 , 　郭晓汾 , 　尤晓铃 , 　赵　勇 ( 1. 汽车管理学院车管系, 安徽 蚌埠　2330 11) (2. 长安大学汽车学院, 陕西 西安　7 10064) 摘要: 　研究使用遗传算法求解物流配送组织过程中车辆调度问题. 通过把时间窗约束和车辆容量约束转 嫁到最小费用 目标函数中去, 建立适合于遗传算法的车辆调度模型. 阐述放回式随机复制算子和适应度函 数, 设计描述行驶线路的染色体结构、初始群体生成方法、独特的交叉算子和交换变异算子, 构造完整的遗传 算法. 并给出算例, 验证调度模型和遗传算法. 关键词: 　物流配送; 车辆调度; 遗传算法 车辆调度是物流组织关键环节, 直接影响客户服务水平和配送成本, 其任务是根据客户 需求分布和车辆相关数据, 以总费用最低为 目标, 选派车辆, 确定每辆车的服务对象和行驶 线路. 由于物流配送车辆调度问题属于异化的多重旅行商难题, 受到时间窗和车辆容量等 约束影响, 难以构造出精确算法, 国内外专家把主要精力集中在构造启发式算法上[ 1—2 ]. 遗 传算法具备极强的鲁棒性和内在并行运行机制, 本文通过约束转换, 建立车辆调度模型, 并 设计遗传操作方法, 构造完整的遗传算法. 1　物流配送车辆调度模型 [3 ] 配送费用由车辆费用、驾驶员补助、等待费用和延迟费用组成 . 车辆费用由燃料费、 折旧费和维修费等变动费用组成, 中心根据经营情况可核算出每车公里应摊的车辆费用. 驾驶员补助根据途中工作时间计算, 若工作时间超过 8 小时, 则超时部分应按加班补助计 算. 客户通常要求货物在一定时间窗范围内送达, 否则中心需支付惩罚费用. 若提前到达, 支付等待费用; 若延迟到达, 支付延迟费用. 设配送中心向 l 个客户送货, 第 i 个客户货运量为 g , 卸货时间为 u t , 时间窗为 [et , i i i l t ], 每小时延迟费用 r ; 中心与客户、客户与客户两两间的最短运距、平均车速和车辆费用 i i ( ) 分别为d ij 、v ij 和 rij i, j = 0, 1, 2, …, l; 0 表示配送中心 ; 可用m 类卡车送货, 第p 类卡车有 np 辆, 装载容量为vp (p = 1, 2, …,m ) ; 每小时等待费用为 r, 行